Computer Science 2800: Discrete Structures
Spring, 2010

Final: Thu, May 20 7:00 PM URHG01: Uris Hall G01

Text: Discrete Mathematics and Its Applications, Kenneth H. Rosen, McGraw-Hill (6th edition).

Syllabus:

Week 1: Sets, functions, relations (Rosen 2.1, 2.2, 2.3, 8.1, 8.5)
Week 2: Relations, Functions, Proof Techniques (Rosen 8.1, 8.4, 8.5, 2.3, 1.6, 4.1)
Week 3: Induction, Strong induction, Primes (Rosen 4.1, 4.2, 3.5)
Week 4: Number theory, Primes, Gcd, Modular arithmetic (Rosen 3.4, 3.5)
Week 5, Monday: Fermat's little theorem and RSA (Rosen 3.7)
Week 5: Propositional logic, tautologies (Rosen 1.1, 1.2)
Week 6: Axiom systems, formal proofs, first-order logic (Rosen 1.5, 1.3, 1.4)
Week 7, 8: Counting, Bijections, Binomial coefficients (Rosen 5.1, 5.3, 5.4)
Week 9: Pigeon-hole, Inclusion/exclusion, Probability (Rosen 7.5, 5.2, 6.1)
Week 10: Probability, Graph theory (Rosen 9.1, 9.2, 6.2, 6.4)
Week 11: Graph theory (Rosen 9.7, 9.8, 9.5)
Week 12: Finite Automata (Rosen 12.2, 12.3)
Week 13: Finite Automata and Regular Languages (Rosen 12.4)
Week 14: Markov Chains