Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Rob Schapire

Fall 2006

 
Directory
General Information | Schedule & Readings | Assignments & Exams | Precepts

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 [1-2]
2 Tu 9/19 Proof by induction [3]
3
4		 Th 9/21
Tu 9/26		 Sums, approximations and asymptotics [10-11]
5
6		 Th 9/28
Tu 10/3		 Recurrences [12-13]
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 [22-23]
18 Tu 11/21 Deviation from the mean [24 through section 24.2]
also: pages 15-24 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 [4-5]
(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