CPS 102: Discrete Mathematics for Computer Science, Fall 2007

[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: Urmi Majumder

Lectures Time: Monday and Wednesday, 2:50 pm -4:05 pm
Lectures Location: LSRC D 243
Recitation Time: Friday, 2:50 pm -4:05 pm
Recitation Location: LSRC D 243

Office Hours:
Bruce Maggs: Monday and Wednesday after class in LSRC D336
Urmi Majumder: Tuesday, 11:00-12:00 noon in LSRC D 104

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 27 Pancakes with a problem Lecture 1    
Aug 29 Deterministic Finite Automata Lecture 2 10.2-10.4  
Sept 5 Solving problems and writing proofs Lecture 3   Homework 1
Sept 7 Recitation      
Sept 10 Inductive Reasoning Lecture 4 3.1-3.2  
Sept 12 Ancient Wisdom: Unary and Binary Lecture 5 2.4 starting with "Representations of Integers"  
Sept 14 Recitation      
Sept 17 Counting I: Correspondences and Choice Trees Lecture 6 4.1-4.3  
Sept 19 Counting II: Recurring Problems and Correspondences Lecture 7 4.1-4.3 Homework 2
Sept 21 Counting III Lecture 8 4.6  
Sept 24 Recitation      
Sept 26 The Mathematics of 1950's Dating Lecture 9    
Sept 28 QUIZ 1      
Oct 1 Probability Theory: Counting in Terms of Proportions Lecture 10 4.4-4.5  
Oct 3 Probability Theory: Great Expectations Lecture 11 4.4-4.5 Homework 3
Oct 5 Recitation      
Oct 8 NO CLASSES, Fall break      
Oct 10 Random Walks Lecture 12    
Oct 12 Recitation ; Mid-semester grades due      
Oct 15 Ancient Wisdom: On Raising A Number to a Power Lecture 13    
Oct 17 Euclid's Algorithm and Continued Fractions Lecture 14 2.3-2.4 Homework 4
Oct 22 Fibonacci Numbers, Polynomial Coefficients, Vector Programs Lecture 15    
Oct 24 Randomness and Computation Lecture 16    
Oct 26 Recitation      
Oct 29 Modular Arithmetic and the RSA Cryptosystem Lecture 17    
Oct 31 Group Theory Lecture 18    
Nov 2 QUIZ 2      
Nov 5 Graphs Lecture 19      
Nov 7 Graphs II Lecture20     Homework 5  
Nov 9 Recitation      
Nov 12 The Big Oh Lecture21      
Nov 14 Grade School Revisited: How to Multiply Two Numbers Lecture22, Lecture22b      
Nov 16 Recitation      
Nov 19 Cantor's Legacy: Infinity and Diagonalization Lecture23     
Nov 21 NO CLASSES, Thanksgiving recess      
Nov 23 NO CLASSES, Thanksgiving recess      
Nov 26 Turing's Legacy: The Limits of Computation Lecture24    Homework 6  
Nov 28 Godel's Legacy: What is a Proof? Lecture25       
Nov 30 Recitation      
Dec 3 Complexity Theory: Reductions Between Computational Problems Lecture26      
Dec 5 Complexity Theory: The P vs. NP Question Lecture27     
Dec 7 Recitation      
Dec 11 FINAL EXAM 9:00am-noon      

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