Discrete Mathematics CSC 2110

This slides are copyrighted by  Chinese University of Hong Kong.

Lecture 0: about the course [ppt] [pdf] Logic and Proofs Propositional logic, first order logic. Proof by cases, proof by contradiction. Induction, invariant method.

Lecture 1: propositional logic [ppt] [pdf]

Lecture 2: first order logic [ppt] [pdf]

Lecture 3: methods of proofs [ppt] [pdf]

Lecture 4: mathematical induction 1 [ppt] [pdf]

Lecture 5: mathematical induction 2 [ppt] [pdf] Graph Theory Degree sequence, Eulerian graphs, isomorphism. Trees. Stable matching, bipartite matching. Graph coloring, planar graphs.

Lecture 6: introduction to graphs [ppt] [pdf]

Lecture 7: stable matching [ppt] [pdf]

Lecture 8: bipartite matching [ppt] [pdf]

Lecture 9: graph coloring [ppt] [pdf]

Lecture 10: planar graph [ppt] [pdf]

Lecture 11: sets [ppt] [pdf] Counting Sets, functions, number sequences Combinations, permutations, binomial theorem. Counting by mapping, pigeonhole principle, inclusion-exclusion principle Recursion, generating functions

Lecture 12: basic counting [ppt] [pdf]

Lecture 13: binomial coefficient, inclusion-exclusion [ppt] [pdf]

Lecture 14: functions, pigeonhole principle [ppt] [pdf]

Lecture 15: counting by mapping [ppt] [pdf]

Lecture 16: more counting by mapping [ppt] [pdf]

Lecture 17: number sequences [ppt] [pdf]

Lecture 18: recursion [ppt] [pdf]

Lecture 19: solving recurrence [ppt] [pdf]