Lec.  Date  Syllabus  Reading  Handouts/Homework


1 
Jan 12 
Introduction. Propositional logic. (Slides). 
BN0,BN1, Hammack § 2.6. (Optional: Hammack § 12.5). 
General Course Information,
Collaboration and Honesty Policy,
HW0 out

2 
Jan 14 
Propositional logic. (Slides). 
BN1. (Optional: Hammack § 2.72.12.) 
HW0 due, HW 1 out.

3 
Jan 16 
Propositional logic, start proofs (Slides). 
BN2 


Jan 19 
No class: MLK Day 
4 
Jan 21 
Proofs. (Slides). 
BN2. (Also recommended: Hammack § 46.) 
HW1 due, HW2 out.

5 
Jan 23 
Proofs. (Slides). 
BN2. (Also recommended: Hammack § 79.) 

6 
Jan 26 
Induction. (Slides). 
BN3. (Also recommended: Hammack § 10.) 

7 
Jan 28 
Induction. (Slides). 
BN3. (Also recommended: Hammack § 10.) 
HW 2 due, HW 3 out 
8 
Jan 30 
Strong induction. (Slides). 
BN3. (Also recommended: Hammack § 10.) 

9 
Feb 2 
Stable marriage. (Slides). 
BN4 

10 
Feb 4 
Stable marriage. (Slides). 
BN4 
HW 3 due, HW 4 out 
11 
Feb 6 
Stabel marriage. Modular arithmetic. (Slides). 
BN4, BN5 

12 
Feb 9 
GCD, inverses and extended GCD. (Slides). 
BN5 

13 
Feb 11 
Chinese Remainder Theorem. (Slides). 
BN5 
HW 4 due, practice midterm out 
14 
Feb 13 
Publickey cryptography. RSA. (Slides by Dr. Wang; Dr. Raskhodnikova was at AAAS Annual Meeting, giving a talk on privacy). 
BN6 

15 
Feb 16 
Polynomials. (Slides). 
BN7 

16 
Feb 18 
Review. (Slides). 
BN7 
HW5 out 

Feb 18 
Exam 8:1510:15pm in 119 Osmond 
17 
Feb 20 
Polynomials. Secret sharing. (Slides). 
BN7 

18 
Feb 23 
Secret sharing. (Slides). 
BN7 

19 
Feb 25 
Errorcorrecting codes: erasures. (Slides). 
BN8 
HW5 due, HW6 out 
20 
Feb 27 
Errorcorrecting codes: general errors. (Slides). 
BN8 

21 
March 2 
Errorcorrecting codes. (Slides). 
BN8 

22 
March 4 
Graphs. (PSU classes canceled for the day.) 
BN on graphs 
HW6 due, HW7 out 
23 
March 6 
Graphs. (Slides). 
BN on graphs 


March 913 
No class: Spring Break 
24 
March 16 
Graphs. (Slides). 
BN on graphs 

25 
March 18 
Graphs. (Slides). 
BN on graphs 
HW7 due, HW8 out 
26 
March 20 
Counting. (Slides). 
BN12. (Also recommended: Hammack § 3.13.4.) 

27 
March 23 
Counting. Combinatorial proofs. (Slides). 
BN13 

28 
March 25 
Counting. InclusionExclusion Principle. (Slides). 
Hammack § 3.5 
HW8 due, practice midterm 2 out 
29 
March 27 
Basic probability. (Slides). 
BN13 
30 
March 30 
Basic probability. (Slides). 
BN13 

31 
Apr 1 
Review. (Slides). 

HW9 out 

Apr 1 
Exam 8:1510:15pm in 119 Osmond 
32 
Apr 3 
Combining events. Conditional probability. (Slides). 
BN14 

33 
Apr 6 
Conditional probability. Bayes' rule. (Slides). 
BN14 

34 
Apr 8 
Bayes' rule. Total probability rule. (Slides). 
BN14 
HW9 due, HW10 out 
35 
Apr 10 
Independence. Mutual and pairwise independence. Product rule. (Slides). 
BN14 

36 
Apr 13 
Applications: hashing and load balancing. (Slides). 
BN15 

37 
Apr 15 
Applications: hashing and load balancing. (Slides). 
BN15 
HW10 due, HW 11 out 
38 
Apr 17, 
Random variables. Distribution of a random variable. Binomial distribution. (Slides). 
BN16 

39 
Apr 20 
Expectation. Linearity of expectation. (Slides). 
BN16 

40 
Apr 22 
Review of random variables and expectations. (Slides). 
BN16 
HW11 due, HW12 out 
41 
Apr 24 
Variance. (Slides). 
BN17 

42 
Apr 27 
Variance. Independent random variables. (Slides). 
BN17 
Practice final exam out. 
43 
Apr 29 
Infinity and countability, diagonalization, existence of undecidable problems, Halting problem. (Slides). 
BN10, BN11 (from Spring 2015) 
HW12 due (not graded). 
44 
May 1 
Review. (Slides). 



May 4 
Final Exam 10:10am12:00pm in 010 SPARKS 