Covers conditional probability and its applications to examples including medical testing, gambling, and court cases.

Speaker: Tom Leighton

Instructor's Note: The actual details of the Berkeley sex discrimination case may have been different than what was stated in the lecture, so it is best to consider the description given in lecture as fictional but illustrative of the mathematical point being made.

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.