Time and Venue:
Day, Date  Topic(s) covered  Reading(s) from Rosen 
Monday 01/24  course overview  
Wednesday 01/26  logical statements, logical connectives, and circuits  Rosen 1.11.3 
Friday 01/28  logical statements using $ and "  Rosen 3.1 
Monday 01/31  negating statements, and who has a winning strategy in games  
Wednesday 02/02  styles of proofs: contradiction, induction  Rosen 3.2 
Friday 02/04 
growth of functions using induction: Harmonic function. 

Monday 02/07  Fibonacci numbers  
Wednesday 02/09  strong induction  
Friday 02/11  induction for other structures: ordering references  
Monday 02/14  Algorithms for numbers  Rosen 2.12.3 
Wednesday 02/16  greatest common divisor  
Friday 02/18  Euclid's Algorithm  Rosen 2.5 
Monday 02/21  modular arithmetic  Rosen 2.4 +2.6 
Wednesday 02/23  RSA crypto system  Rosen 2.6 
Friday 02/25  The pigeon hole principle  Rosen 4.2 
Monday 02/28  other uses of RSA, and finding primes.  
Wednesday 03/02  combinatorics and counting  Rosen 4.1 
Friday 03/04  Permutations and Combinations  Rosen 4.34.4 
Monday 03/07  Identities using Binomial coefficients  Rosen 4.4 
Tuesday 03/08  Evening prelim 7:309pm  covering Rosen 1.11.5 and 2.12.6 and 3.13.5 
Wednesday 03/09  InclusionExplusion principle  Rosen 6.5 
Friday 03/11  Counting subsets with replacement  Rosen 4.5 
Monday 03/14  Market basket data  see also optional reading 
Wednesday 03/16  Probability  Rosen 5.15.2 (or 4.54.6 in 4th edition) 
Friday 03/18  Conditional probability, independence, Bayes rule,  Rosen 5.15.2 (or 4.54.6 in 4th edition) 
03/2125  SPRING BREAK  
Monday 03/28  contention resolution  KThandout section 13.1 
Wednesday 03/30  Expectations  
Friday 04/01  Union Bound  KT section 13.12 
Monday 04/04  coupon collector in expectation and with high probability  KT sections 13.1 and 13.3 
Wednesday 04/06  Max3SAT, the probabilistic method  KT section 13.4 
Friday 04/08  Hashing  KT section 13.6 
Monday 04/11  In class prelim review  
Tuesday 04/12  Evening prelim 7:309pm  
Wednesday 04/13  Bounding deviation from expectation  Section 5.3 
Friday 04/15  Variance  Section 5.3 
Monday 04/18  Law of large numbers, Binomial distributions  Section 5.3 
Wednesday 04/20  Other distributions, geometric, Poisson  
Friday 04/22  Graphs  Section 8.12,4 
Monday 04/25  Trees in graphs  Section 9.1 
Wednesday 04/27  BFS, and DFS  Section 9.4 
Friday 04/29  graph coloring  Section 8.8 
Monday 05/02  Directed graphs, directed acyclic graphs  Section 8.4 
Wednesday 05/04  components, and properties of the Web graph  Section 8.4 
Friday 05/06  Random graphs models and the Web  
Friday 05/13  Final 911:30am in Phillips 101 