An introduction to proof techniques, covering proof by contradiction and induction, with an emphasis on the inductive techniques used in proof by induction.

1. Introduction and Proofs
2. Mathematical Induction
3. Strong Induction
4. Number Theory I
5. Number Theory II
6. Graph Theory and Coloring
7. Matching Problems
8. Graph Theory II: Minimum Spanning Trees
9. Communication Networks
10. Graph Theory III
11. Relations, Partial Orders, and Scheduling
12. Sums
13. Sums and Asymptotics
14. Divide and Conquer Recurrences
15. Linear Recurrences
16. Counting Rules I
17. Counting Rules II
18. Probability Introduction
19. Conditional Probability
20. Independence: Independent and Dependent Events
21. Random Variables
22. Expectation I
23. Expectation II
24. Large Deviations
25. Random Walks

This course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.