Mathematics for Computer Scien
Readings
The course notes below form the "textbook" for the course. Each week, students are required to read the relevant notes, answer questions about these notes assigned on an Online Tutor, and email to the instructor comments on a passage from the reading that was difficult, surprising, or should be more thoroughly explained. Prof. Albert Meyer attempts to adapt lectures in response to student email on the reading.
Week 1 - Proofs (PDF)
Week 2 - Predicates and Sets (PDF)
Week 3 - Induction (PDF)
Week 4 - Binary Relations (PDF)
Week 5 - Graphs (PDF)
Week 6 - Introduction to Number Theory (PDF)
Week 7 - State Machines: Invariants and Termination (PDF); Fallacies with Infinity (PDF)
Week 8 - Sums, Products and Asymptotics (PDF)
Week 9 - Counting I (PDF)
Week 10 - Counting II (PDF)
Week 11 - Generating Functions (PDF)
Week 12 - Introduction to Probability (PDF)
Week 13 - Random Variables, Distributions and Expectation (PDF)
Week 14 - Missed Expectations? (PDF)
Lecture Notes
Powerpoint and LaTeX source files and LaTeX macros are available to instructors by request: email Prof. Albert Meyer at meyer at csail dot mit dot edu.
|
SES # |
TOPICS |
SLIDES |
IN-CLASS PROBLEMS |
IN-CLASS PROBLEM SOLUTIONS |
|
Week 1 |
||||
|
1 |
Good and Bad Proofs |
(PDF) |
(PDF) |
(PDF) |
|
2 |
Propositions and Proofs |
(PDF) |
(PDF) |
(PDF) |
|
Week 2 |
||||
|
3 |
Proofs by Contradiction and Cases |
(PDF) |
(PDF) |
(PDF) |
|
4 |
Predicate Logic |
(PDF) |
(PDF) |
(PDF) |
|
5 |
Sets and Functions |
(PDF) |
(PDF) |
(PDF) |
|
Week 3 |
||||
|
6 |
Induction I |
(PDF) |
(PDF) |
(PDF) |
|
7 |
Induction II |
(PDF) |
(PDF) |
(PDF) |
|
Week 4 |
||||
|
8 |
Relations I |
(PDF) |
(PDF) |
(PDF) |
|
9 |
Relations II |
(PDF) |
(PDF) |
(PDF) |
|
10 |
Graph Theory I |
(PDF) |
(PDF) |
(PDF) |
|
Week 5 |
||||
|
11 |
Graph Theory II |
(PDF) |
(PDF) |
(PDF) |
|
12 |
Graph Theory III |
(PDF) |
(PDF) |
(PDF) |
|
13 |
Graph Theory IV |
(PDF) |
(PDF) |
|
|
Week 6 |
||||
|
14 |
Number Theory I |
(PDF) |
(PDF) |
(PDF) |
|
15 |
Number Theory II |
|
(PDF) |
(PDF) |
|
Week 7 |
||||
|
16 |
Quiz 1 and Solution |
|
|
|
|
17 |
Number Theory III |
(PDF) |
(PDF) |
(PDF) |
|
18 |
State Machines I: Invariants |
(PDF) |
(PDF) |
(PDF) |
|
Week 8 |
||||
|
19 |
State Machines II: Derived Variables, Stable Marriage Problem |
(PDF) |
(PDF) |
|
|
20 |
Sums and Series I |
(PDF) |
(PDF) |
(PDF) |
|
21 |
Sums and Series II |
(PDF) |
(PDF) |
(PDF) |
|
Week 9 |
||||
|
22 |
Asymptotics |
(PDF) |
(PDF) |
(PDF) |
|
23 |
Counting I |
|
(PDF) |
(PDF) |
|
24 |
Counting II |
|
(PDF) |
(PDF) |
|
Week 10 |
||||
|
25 |
Counting III (with Magic Trick Solution) |
|
(PDF) |
(PDF) |
|
26 |
Counting IV |
|
(PDF) |
(PDF) |
|
Week 11 |
||||
|
27 |
Quiz 2 and Solution |
|
|
|
|
28 |
Generating Functions I |
|
(PDF) |
(PDF) |
|
29 |
Generating Functions II |
|
(PDF) |
(PDF) |
|
Week 12 |
||||
|
30 |
Introduction to Probability |
|
(PDF) |
(PDF) |
|
31 |
Conditional Probability and Independence |
|
(PDF) |
(PDF) |
|
Week 13 |
||||
|
32 |
Random Variables |
|
(PDF) |
(PDF) |
|
33 |
Distribution and Density, Binomial Distribution |
|
(PDF) |
(PDF) |
|
34 |
Expectation |
|
(PDF) |
(PDF) |
|
Week 14 |
||||
|
35 |
Linearity of Expectation |
|
(PDF) |
(PDF) |
|
36 |
Variance |
|
(PDF) |
(PDF) |
|
37 |
Sampling and Confidence |
|
(PDF) |
(PDF) |
|
Week 15 |
||||
|
38 |
Law of Large Numbers |
(PDF) |
(PDF) |
(PDF) |
|
39 |
Random Walks |
(PDF) |
(PDF) |
(PDF) |
Assignments
The assignments are given out in the sessions noted in the table.
|
SES # |
TOPICS |
ASSIGNMENTS |
SOLUTIONS |
|
2 |
Propositions and Proofs |
Problem Set 1 (PDF) |
(PDF) |
|
6 |
Induction I |
Problem Set 2 (PDF) |
(PDF) |
|
8 |
Relations I |
Problem Set 3 (PDF) |
(PDF) |
|
11 |
Graph Theory II |
Problem Set 4 (PDF) |
(PDF) |
|
14 |
Number Theory I |
Problem Set 5 (PDF) |
(PDF) |
|
18 |
State Machines I: Invariants |
Problem Set 6 (PDF) |
(PDF) |
|
23 |
Counting I |
Problem Set 7 (PDF) |
(PDF) |
|
29 |
Generating Functions I |
Problem Set 8 (PDF) |
(PDF) |
|
31 |
Introduction to Probability |
Problem Set 9 (PDF) |
(PDF) |
|
35 |
Expectation |
Problem Set 10 (PDF) |
(PDF) |
Exams
This section provides the 2-hour quizzes and 3-hour final exam for the course. For more practice exams, see theSpring 2005 edition of this course on OpenCourseWare.
|
EXAMS |
SOLUTIONS |
|
Practice Quiz 1 (Spring 2002) (PDF) |
(PDF) |
|
Quiz 1 (PDF) |
(PDF) |
|
Quiz 2 (PDF) |
(PDF) |
|
Final Exam (PDF) |
(PDF) |