Massachusetts Institute of Technology Handout 2 6.042J/18.062J: Mathematics for Computer Science September 10, 1998 Professors Nancy Lynch and Srinivas Devadas

Tentative Course Outline

{Sep \atop 7} 8

Registration Day 9 10 Lecture 1:

Administrivia. Logical notation and basic proof techniques.

PSet 1 out.

11 Tutorial 1

{Sep \atop 14} 15

Lecture 2: Induction. PSet 1 due. PSet 2 out.

16 17 Lecture 3:

Strong

induction and well-ordering.

18 Tutorial 2

{Sep \atop 21} 22

Lecture 4:

Proof

techniques for networks.

PSet 2 due. PSet 3 out.

23 24 Lecture 5:

Formal

Methods: state machines and invariants.

25 Tutorial 3

{Sep-Oct \atop 28} 29

Lecture 6:

Formal Methods: derived variables.

PSet 3 due. PSet 4 out.

30 1 Lecture 7:

Analysis Tools: evaluating sums.

2 Tutorial 4 2 Handout 2: Tentative Course Outline

{Oct \atop 5} 6

Lecture 8:

Analysis Tools: products and asymptotic notation.

PSet 4 due. PSet 5 out.

7 8 Lecture 9:

Analysis Tools: Recurrences.

9 Tutorial 5

Oct 12 MIT HOLIDAY 13 Monday Classes 14 15 Lecture 10:

Analysis Tools: Linear Recurrences.

PSet 5 due. PSet 6 out.

16 Tutorial 6

{Oct \atop 19} 20

Lecture 11:

Counting Arguments: Cardinality, Bijections, Pigeonhole Principle, Lower Bd Args.

PSet 6 due PSet 7 out.

21 22 Lecture 12:

Counting Arguments: Countability. Infinities. Diagonalization.

23 Tutorial 7

{Oct \atop 26} 27

Lecture 13:

More Counting: Permutations and Combinations.

PSet 7 due. FakePSet 7.5 out.

28 29 Lecture 14:

More Counting: Permutations and Combinations.

30 Tutorial 8 Handout 2: Tentative Course Outline 3

Nov 2

Optional Review: 7:00–9:00pm

4-270 and 4-370

3 Lecture 15:

Permutations and combinations of multisets.

PSet 8 out.

4

Quiz:

7:00–9:00pm

4-270 and 4-370

5

Lecture 16:

Generating functions.

6 Tutorial 9

{Nov \atop 9} 10

Lecture 17:

Introduction to probability. Sample points and spaces.

PSet 8 due. PSet 9 out 11 MIT HOLIDAY 12 Lecture 18:

Probability laws. Events. Conditional probability.

13 Tutorial 10

{Nov \atop 16} 17

Lecture 19:

Independence. Birthday paradox. Failure analysis.

Pset 9 due. PSet 10 out.

18 Drop Date 19 Lecture 20:

Random Variables. Binomial distributions.

20 Tutorial 11

{Nov \atop 23} 24

Lecture 21:

Functions of random variables. Expectation.

PSet 10 due. PSet 11 out.

25 26

THANKSGIVING

27

THANKSGIVING

{Nov \atop 30} 1

Lecture 22:_{Expectation} 2 3 Lecture 23:

Markov’s

Theorem, Laws for expectation.

4Tutorial 12 PSet 11 due.

{Dec \atop 7} 8

Lecture 24:

Variance, Moments, Chebyshev’s Theorem.

9 10 Lecture 25:

Gambler’s ruin. Random walks.

11

Optional review session during tutorial slot.

Dec 14 FINALS Week 15 16 17

18

(Lecture topics are subject to change.)