Massachusetts Institute of Technology Handout 2 6.042J/18.062J: Mathematics for Computer Science September 7, 2000 Professors Nancy Lynch and Shlomi Dolev

Course Calendar

Monday  Tuesday  Wednesday  Thursday  Friday

Sept 4Labor Day 5

Registration Day 6 7 Lecture 1:

Course overview. Basic data types. Basic proof methods.

PS1 out.

8 Tutorial 1

{Sept \atop 11} 12

Lecture 2:

Predicates and quantifiers. Induction.

PS1 due. PS2 out.

13 14 Lecture 3:

Inductive proofs. Strong Induction.

15 Tutorial 2

{Sept \atop 18} 19

Lecture 4:

Structural induction. Set theory.

PS2 due. PS3 out.

20 21 Lecture 5:_{Relations.}

22 Tutorial 3

{Sept \atop 25} 26

Lecture 6:

Digraphs, graphs, and trees.

PS3 due. PS4 out.

27 28 Lecture 7:

Digraphs, graphs, and trees.

29 Tutorial 4

2 Handout 2: Course Calendar

{Oct \atop 2} 3

Lecture 8:

Computational processes. Proofs about processes: Invariants.

PS4 due. PS5 out.

4 5 Lecture 9:

Proofs about processes: Termination, step bounds. Process behavior.

6Tutorial 5 Add date

Oct 9 Columbus Day holiday 10 Columbus Day holiday 11 12 Lecture 10:

Process structure. Abstraction. Composition.

PS4 due.

13 Tutorial 6

{Oct \atop 16} 17

Lecture 11:

Series. Summations. Products.

PS5 out.

18 QUIZ 1: Lectures 1-10 19 Lecture 12:

Estimation. Asymptotics. Stirling’s formula. Recurrences.

20 Tutorial 7

{Oct \atop 23} 24

Lecture 13:

Recurrences.

PS5 due. PS6 out.

25 26 Lecture 14:

Cardinality. Bijections. Pigeonhole Principle.

27 Tutorial 8

{Oct-Nov \atop 30} 31

Lecture 15:

Basic counting. Sum and product rules. Inclusion/ exclusion.

PS6 due. PS7 out.

1 2 Lecture 16:

Permutations. Combinations. Binomial coefficients.

3 Tutorial 9

{Nov \atop 6} 7

Lecture 17:

Permutations and combinations with repetition.

PS7 due.

8 9 Lecture 18:

Countable and uncountable sets.

10

Veteran’s Day holiday

{Nov \atop 13} 14

Lecture 19:

Introduction to probability. Sample points and spaces.

PS8 out 15 QUIZ 2: Lectures 11-18 16 Lecture 20:

Probability

laws.

Conditional

probability.

17 Tutorial 10

{Nov \atop 20} 21

Lecture 21:

Independence. Failure analysis.

PS8 due. PS9 out.

22 Drop date 23

Thanksgiving holiday 24

Thanksgiving holiday

{Nov-Dec \atop 27} 28

Lecture 22:

Random variables. Binomial distribution.

PS9 due. PS10 out.

29 30 Lecture 23:

Expectation.

1 Tutorial 11

{Dec \atop 4} 5

Lecture 24:

Computing expectations. Wald’s theorem

6 7 Lecture 25:

Variance.

Bounding tails of distributions.

PS10 due.

Shlomi 8Tutorial 12

{Dec \atop 11} 12

Lecture 26:

Random Walks.

13 14 FINAL, Date and time TBA