Date  Instructor  Content  Material  Assignment 

January 16  M. Ghashami  growth of functions (asymptotic notation), recursive relations (recursion tree, master theorem), merge sort and selection sort algorithms  CLRS: Chapters 2, 3, 4  Assignment 1 (this assignment is only provided as an exercise and will not be collected) 
January 18  M. Ghashami  divide and conquer (lower bound on number of comparision on sorting, median of median, linear time select)  DPV: Chapter 3  
January 23  M. Ghashami  Dynamic programming  CLRS: Chapter 15  
January 25  M. Ghashami  Dynamic programming (Matrix chain multiplication), Greedy algorithms (Activity selection), Majority algorithm  CLRS: Chapters 15, 16  Assignment 2 (due February 2, 11:59pm) 
January 30  M. Ghashami  Streaming (Majority, MisraGries, countmin sketch, bloom filter)  http://www.cs.utah.edu/~jeffp/DMBook/L11HeavyHitters.pdf http://www.cs.utah.edu/~jeffp/DMBook/L12CountMin+Apriori.pdf  
February 1  M. Ghashami  Probabilistic Analysis and Randomized Algorithms  CLRS: Chapter 5  Assignment 3 (due February 9, 11:59pm) 
February 6  M. Ghashami  Probabilistic Analysis  CLRS: Chapter 5 (coupon collector, balls and bins, longest streak of heads in coin flips)  
February 8  M. Ghashami  Probabilistic Analysis: online hiring problem, Markov and Chebyshev's inequalities  CLRS: Chapter 5  Assignment 4 (due February 16, 11:59pm) 
February 13  M. Kleindessner  Fast Fourier transform for multiplying polynomials  CLRS: Chapter 30; DPV: Chapter 2.6  
February 15  M. Kleindessner  Fast Fourier transform continued  CLRS: Chapter 30; DPV: Chapter 2.6  Assignment 5 (due February 23, 11:59pm) 
February 20  M. Kleindessner  RSA  DPV: Chapters 1.2  1.4; CLRS: Chapter 31  
February 22  M. Kleindessner  RSA continued (primality testing)  DPV: Chapters 1.2  1.4; CLRS: Chapter 31  Assignment 6 (due March 2, 11:59pm) 
February 27  M. Kleindessner  Midterm  Questions will be about the content of the lectures from January 16 to February 20. You are allowed to bring a handwritten "cheat sheet" (one piece of ordinary paper). 

March 1  M. Kleindessner  Hashing  CLRS: Chapters 11.1  11.2  Assignment 7 (due March 9, 11:59pm) 
March 6  M. Kleindessner  Universal hashing; NPCompleteness  CLRS: Chapter 11.3.3; CLRS: Chapter 34  
March 8  M. Kleindessner  NPCompleteness continued  CLRS: Chapter 34; DPV: p. 249/250  Assignment 8 (due March 23, 11:59pm) 
March 20  M. Kleindessner  Approximation Algorithms  CLRS: Chapter 35 (35.1 and 35.3)  
March 22  M. Kleindessner  Approximation Algorithms continued; Branchandbound  CLRS: Chapter 34.5.4; DPV: Chapter 9.1.2  Assignment 9 (due March 30, 11:59pm), SetCoverInstance.txt 
March 27  J. Kong  Linear Algebra review  CLRS: Appendix D, V: Chapter 21.3.2, 26.2  
March 29  J. Kong  String Matching: Naive Algorithm and The KnuthMorrisPratt Algorithm  CLRS: 32.1, 32.4  Assignment 10 (due April 06, 11:59pm) 
April 3  J. Kong  String Matching: The String Matching with finite automata  CLRS: 32.3  
April 5  J. Kong  String Matching: The RabinKarp algorithm; Van Emde Boas Trees: Preliminary approaches.  CLRS: 32.2 and 20.1  Assignment 11 (due April 13, 11:59pm) 
April 10  J. Kong  Van Emde Boas Trees  CLRS: 20.2 and 20.3  
April 12  J. Kong  Matrix Operations  CLRS: 28.1  Assignment 12 (due April 20, 11:59pm) 
April 17  M. Kleindessner  Markov Chains and PageRank  https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf (Sections 11.1, 11.3, 11.4) 

April 19  M. Kleindessner  Markov Chains and PageRank continued  Assignment 13 (due April 27, 11:59pm)  
April 24  M. Kleindessner  Markov Chains and PageRank continued  https://disco.ethz.ch/courses/fs16/ti2/lecture/chapter11.pdf (Section 11.3)  
April 26  M. Kleindessner  Stable marriage problem and GaleShapley algorithm  Lecture notes  
May 4  Final  Questions will be about the content of the lectures from February 22 to April 26. You are allowed to bring a handwritten "cheat sheet" (one piece of ordinary paper). 