Mathematics for Computer Science
Readings
This section contains the course notes, Mathematics for Computer Science. Chapter 8 is not available on MIT OpenCourseWare.
These notes are courtesy of Eric Lehman, Tom Leighton, and Albert Meyer, and are used with permission.
|
CHAPTERS |
FILES |
|
Complete course notes |
|
|
Part I: Proofs |
|
|
Chapter 1: Propositions |
(PDF) |
|
Chapter 2: Patterns of proof |
(PDF) |
|
Chapter 3: Induction |
(PDF) |
|
Chapter 4: Number theory |
(PDF) |
|
Part II: Structures |
|
|
Chapter 5: Graph theory |
|
|
Chapter 6: Directed graphs |
(PDF) |
|
Chapter 7: Relations and partial orders |
(PDF) |
|
Chapter 8: State machines |
|
|
Part III: Counting |
|
|
Chapter 9: Sums and asymptotics |
(PDF) |
|
Chapter 10: Recurrences |
(PDF) |
|
Chapter 11: Cardinality rules |
(PDF) |
|
Chapter 12: Generating functions |
(PDF) |
|
Chapter 13: Infinite sets |
(PDF) |
|
Part IV: Probability |
|
|
Chapter 14: Events and probability spaces |
(PDF) |
|
Chapter 15: Conditional probability |
(PDF) |
|
Chapter 16: Independence |
(PDF) |
|
Chapter 17: Random variables and distributions |
(PDF) |
|
Chapter 18: Expectation |
(PDF) |
|
Chapter 19: Deviations |
(PDF) |
|
Chapter 20: Random walks |
(PDF) |
Recitations
This section contains recitation problems and notes, which include solutions.
|
REC # |
TOPICS |
PROBLEMS |
NOTES |
|
1 |
Logic, proving an implication |
(PDF) |
(PDF) |
|
2 |
Induction |
(PDF) |
(PDF) |
|
3 |
State machines |
(PDF) |
(PDF) |
|
4 |
Greatest common divisor |
(PDF) |
(PDF) |
|
5 |
Exponentiation, modular arithmetic, RSA |
(PDF) |
(PDF) |
|
6 |
Graph basics |
(PDF) |
(PDF) |
|
7 |
Stable marriage problem |
(PDF) |
(PDF) |
|
8 |
Build-up error, the grow algorithm |
(PDF) |
(PDF) |
|
9 |
Traveling salesperson problem |
(PDF) |
(PDF) |
|
10 |
Analysis of two networks, routing in a Beneš network |
(PDF) |
(PDF) |
|
11 |
Equivalence relations, chains, topological sort |
(PDF) |
(PDF) |
|
12 |
The L-tower problem, double sums |
(PDF) |
(PDF) |
|
13 |
Asymptotic notation, asymptotic equivalence |
(PDF) |
(PDF) |
|
14 |
Guessing a particular solution, linear recurrences |
(PDF) |
(PDF) |
|
15 |
Counting problems, pigeonhole principle |
(PDF) |
(PDF) |
|
16 |
Combinatorial proof, more counting |
(PDF) |
(PDF) |
|
17 |
Probability, Monty Hall problem |
(PDF) |
(PDF) |
|
18 |
Total probability law |
(PDF) |
(PDF) |
|
19 |
Bayes' rule |
(PDF) |
(PDF) |
|
20 |
Philosophy of probability |
(PDF) |
(PDF) |
|
21 |
Conditional expectation and total expectation |
(PDF) |
(PDF) |
|
22 |
Expected value rule for functions of random variables, properties of variance |
(PDF) |
(PDF) |
|
23 |
Probability theorems |
(PDF) |
(PDF) |
Assignments
|
PROBLEM SETS |
|
Problem set 1 (PDF) |
|
Problem set 2 (PDF) |
|
Problem set 3 (PDF) |
|
Problem set 4 (PDF) |
|
Problem set 5 (PDF) |
|
Problem set 6 (PDF) |
|
Problem set 7 (PDF) |
|
Problem set 8 (PDF) |
|
Problem set 9 (PDF) |
|
Problem set 10 (PDF) |
|
Problem set 11 (PDF) |
|
Problem set 12 (PDF) |
Exams
All exams and solutions are courtesy of the instructors named on the first page, and are used with permission. Solutions to the final exam are not available.
|
EXAMS |
SOLUTIONS |
|
Midterm practice problems (PDF) |
(PDF) |
|
Midterm (PDF) |
(PDF) |
|
2004 final exam (PDF) |
(PDF) |
|
2006 final exam (PDF) |
(PDF) |
|
2008 final exam (PDF) |
(PDF) |
|
Final exam (PDF) |
|