CPS 102: Discrete Mathematics for Computer Science, Fall 2010

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

Announcements:

11/22/10: Homework 6 has been posted. It's due on Dec. 8th.
10/25/10: Homework 4 has been posted to the blackboard. It's due on Nov. 3rd. Please submit it to the BLACKBOARD.
10/04/10: Homework 3 has been posted. It's due on Oct. 18th. Please submit it to the BLACKBOARD.
10/04/10: Quiz 1 grades have been posted on blackboard.
09/20/10: Homework 2 has been posted. It's due on Sept. 29th.
09/19/10: Please bring your homework 1 to tomorrow's class.
09/09/10: Homework 1 has been posted. It's due on Sept. 20th.

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:

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

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