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, Misra-Gries, count-min sketch, bloom filter) | http://www.cs.utah.edu/~jeffp/DMBook/L11-Heavy-Hitters.pdf http://www.cs.utah.edu/~jeffp/DMBook/L12-Count-Min+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; NP-Completeness | CLRS: Chapter 11.3.3; CLRS: Chapter 34 | |
March 8 | M. Kleindessner | NP-Completeness 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; Branch-and-bound | 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 Knuth-Morris-Pratt 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 Rabin-Karp 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 Gale-Shapley 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). |