CPS 102: Discrete Mathematics for Computer Science, Fall 2007

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.

Announcements:

12/06/07: Review for final exam in recitation 12/7/07.
11/30/07: Final exam in on Tuesday, 12/11/07, 9 am to noon
11/30/07: The recitation on 12/7/07 will be a review class.
11/26/07: Homework 6 has been posted. It's due on 12/5/07/.
11/8/07: Homework 5 has been posted. Its due on 11/19/07.
10/31/07: Quiz 2 is on Friday 11/02/07.
10/17/07: Homework 4 has been posted and it is due on 10/30/07.
10/03/07: Homework 3 has been posted and it is due on 10/15/07.
09/27/07: Quiz 1 is on Friday 08/28/07.
09/27/07: Homework 2 is due on Friday 09/28/07.
09/08/07: Homework 1 is due on Monday 09/17/07.
09/10/07: Bruce's office hours this week are after class until 5 pm.

Administration:

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

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 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).