Princeton University

Computer Science 341

Fall

Numbers in brackets under "reading" refer to chapters or sections of Lehman and Leighton. Material and readings for lectures that have not yet taken place are tentative and subject to change.
# 
Date 
Topic 
Reading 
1  Th 9/14  Introduction, methods of proof  [12] 
2  Tu 9/19  Proof by induction  [3] 
3 4 
Th 9/21 Tu 9/26 
Sums, approximations and asymptotics  [1011] 
5 6 
Th 9/28 Tu 10/3 
Recurrences  [1213] 
7  Th 10/5  finish recurrences; begin counting  [14, through section 14.2.2] 
8 9 
Tu 10/10 Th 10/12 
Counting  [rest of 14] [15] [16 through section 16.3] 
10  Tu 10/17  Combinatorial proof Generating functions 
[16.5] [17 through section 17.3] 
11  Th 10/19  Generating functions for counting; begin probability theory 
[rest of 17] [18 through section 18.1.2] 
12 13 
Tu 10/24 Th 10/26 
Probability; conditional probability; begin independence  [rest of 18] [19] [20 through section 20.1.3] 
14  Tu 11/7  Independence  [rest of 20] 
15  Th 11/9  Random variables  [21] 
16 17 
Tu 11/14 Th 11/16 
Expectation  [2223] 
18  Tu 11/21  Deviation from the mean  [24 through section 24.2] also: pages 1524 of these notes (minor errata: Theorem 1.13 (not included in reading) is incorrect) 
19  Tu 11/28  Chernoff bounds; random walks 
[rest of 24] [25] 
20 21 22 
Th 11/30 Tu 12/5 Th 12/7 
Number theory  [45] (Suggested reading order: [4] through section 4.2.2, but skipping 4.2.1; then [5] through section 5.2; then all the rest of [4]; then all the rest of [5].) 
23 24 
Tu 12/12 Th 12/14 
Graph theory  these notes and these notes 