CPS 102: Discrete Mathematics for Computer Science, Fall 2010

[Test image]

This is a self-contained course. The lectures for this course are primarily developed by Professor Steven Rudich.



Announcements:

Administration:

Instructor: Bruce Maggs (bmm@cs.duke.edu)
Teaching Assistant: Yin Lin (linyin@cs.duke.edu)

Lectures Time: Monday and Wednesday, 1:15 pm -2:30 pm
Lectures Location: LSRC D106
Recitation Time: Friday, 1:15 pm -2:30 pm
Recitation Location: LSRC D106

Office Hours:
Bruce Maggs: Monday and Wednesday after class in LSRC D324
Yin Lin: Friday 2:30 pm-3:30 noon in LSRC D311


Grading:
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.

Schedule:

DateLecture TopicSlidesReadingAssignment
Aug 30 Pancakes with a problem Lecture 1  
Sept 1 Deterministic Finite Automata Lecture 212.2-12.4 
Sept 3 NO CLASSES   
Sept 6 Solving problems and writing proofs Lecture 3  
Sept 8Inductive ReasoningLecture 44.1-4.2 
Sept 10 Recitation: DFA   Homework 1
Sept 13 Ancient Wisdom: Unary and BinaryLecture 53.6 starting with "Representations of Integers" 
Sept 15 Counting I: Correspondences and Choice TreesLecture 65.1-5.3 
Sept 17 Recitation: Proofs   
Sept 20 Counting II: Recurring Problems and CorrespondencesLecture 75.1-5.3Homework 2
Sept 22Counting IIILecture 85.4 
Sept 24Recitation : Counting   
Sept 27Probability I: Counting in Terms of ProportionsLecture 94.4-4.5 
Sept 29Probability II: Great ExpectationsLecture 104.4-4.5 
Oct 1Recitation: Quiz Preperation   
Oct 4QUIZ 1   
Oct 6 Random WalksLecture 11 Homework 3
Oct 8Recitation    
Oct 11NO CLASSES, Fall break   
Oct 13Ancient Wisdom: On Raising A Number to a PowerLecture 12  
Oct 15NO CLASSES   
Oct 18Euclid's Algorithm and Continued FractionsLecture 132.3-2.4 
Oct 20Fibonacci Numbers, Polynomial Coefficients, Vector ProgramsLecture 14  
Oct 22Recitation    
Oct 25Randomness and ComputationLecture 15 Homework 4
Oct 27Modular Arithmetic and the RSA CryptosystemLecture 16  
Oct 29Recitation    
Nov 1Group TheoryLecture 17  
Nov 3GraphsLecture 18  
Nov 5Recitation   
Nov 8Graphs IILecture 19  
Nov 10QUIZ 2   
Nov 12No Classes   
Nov 15The Big OhLecture 20 Homework 5
Nov 17How Computers Really Do ArithmeticLecture 21  
Nov 19No Classes   
Nov 22Cantor's Legacy: Infinity and DiagonalizationLecture 22 Homework 6
Nov 24NO CLASSES, Thanksgiving recess   
Nov 26NO CLASSES, Thanksgiving recess   
Nov 29Turing's Legacy: The Limits of ComputationLecture 23  
Dec 1Godel's Legacy: What is a Proof?Lecture 24  
Dec 3NO Classes   
Dec 6Complexity Theory: Reductions Between Computational Problems, The P vs. NP QuestionLecture 25  
Dec 8Recitation   
Dec 14FINAL EXAM 9:00am-NOONLoc: LSRC D106  

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