CPS 102: Discrete Mathematics for Computer Science, Fall 2009

[Test image]
This is a self-contained course and we will use Discrete Mathematics and its Applications by Kenneth H. Rosen, published by McGraw-Hill as the text book for this class. The lectures for this course are primarily developed by Professor Steven Rudich.


Instructor: Bruce Maggs
Teaching Assistant: Souvik Sen

Lectures Time: Monday and Wednesday, 2:50 pm -4:05 pm
Lectures Location: Languages 211
Recitation Time: Friday, 2:50 pm -4:05 pm
Recitation Location: Sociology-Psycology 127

Office Hours:
Bruce Maggs: Monday and Wednesday after class in LSRC D324
Souvik Sen: Friday 11:30-12:30 noon in Hudson 214

Homeworks (40%), Quizzes (30%) and Final (30%)

Please turn in your homeworks at the beginning of the class on the day it is due. There is a penalty of seven points a day late on the homework. Regarding collaboration/cheating policy, you may NOT share written work.
We reuse homework problems.


Date Lecture Topic Slides Reading Assignment
Aug 24 Pancakes with a problem Lecture 1    
Aug 26 Deterministic Finite Automata Lecture 2 12.2-12.4 Homework 1
Aug 28 Recitation      
Aug 31 Solving problems and writing proofs Lecture 3  
Sept 2 Inductive Reasoning Lecture 4 4.1-4.2  
Sept 4 Recitation      
Sept 7 Ancient Wisdom: Unary and Binary Lecture 5 3.6 starting with "Representations of Integers"  
Sept 9 Counting I: Correspondences and Choice Trees Lecture 6 5.1-5.3  
Sept 11 Recitation      
Sept 14 Counting II: Recurring Problems and Correspondences Lecture 7 5.1-5.3 Homework 2
Sept 16 Counting III Lecture 8 5.4  
Sept 18 Recitation      
Sept 23 The Mathematics of 1950's Dating Lecture 9    
Sept 25 Probability Theory: Counting in Terms of Proportions Lecture 10 4.4-4.5  
Sept 28 QUIZ 1      
Sept 30 Probability Theory: Great Expectations Lecture 11 4.4-4.5 Homework 3
Oct 2 Recitation      
Oct 5 NO CLASSES, Fall break      
Oct 7 Random Walks Lecture 12    
Oct 9 Recitation ; Mid-semester grades due      
Oct 12 Ancient Wisdom: On Raising A Number to a Power Lecture 13    
Oct 14 Euclid's Algorithm and Continued Fractions Lecture 14 2.3-2.4
Oct 16 Recitation      
Oct 19 Fibonacci Numbers, Polynomial Coefficients, Vector Programs Lecture 15    
Oct 21 Randomness and Computation Lecture 16   Homework 4
Oct 26 Modular Arithmetic and the RSA Cryptosystem Lecture 17    
Oct 28 Group Theory Lecture 18    
Oct 30 QUIZ 2      
Nov 2 Graphs Lecture 19    
Nov 4 Graphs II Lecture 20   Homework 5  
Nov 6 Recitation      
Nov 9 The Big Oh Lecture 21    
Nov 11 How Computers Really Do Arithmetic Lecture 22    
Nov 16 Grade School Revisited: How to Multiply Two Numbers Lecture 22    
Nov 18 Cantor's Legacy: Infinity and Diagonalization Lecture 23    
Nov 20 Recitation      
Nov 23 Turing's Legacy: The Limits of Computation Lecture 24   Homework 6
Nov 25 NO CLASSES, Thanksgiving recess      
Nov 30 Godel's Legacy: What is a Proof? Lecture 24    
Dec 2 Complexity Theory: Reductions Between Computational Problems
Complexity Theory: The P vs. NP Question
Lecture 25    
Nov 20 Recitation      
Dec 10 FINAL EXAM 2:00pm-5:00pm Languages 211    

Note: All readings are from Discrete Mathematics and its Applications by Kenneth H. Rosen, published by McGraw-Hill (6th edition).