• Lectures: Tu/Th 12:00-1:20, Wean 7500
  • Instructors: Carl Kingsford (carlk@cs, GHC 7719), Danny Sleator (sleator@cs, GHC 8113)
  • TAs: Abhik Mondal, Andy Liu, Raymond Kang, Sidhanth Mohanty, Tewei Luo, William Xiao

  • Recitations (all on Friday)
    • A: 9:30 (GHC 4211): William
    • B: 10:30 (GHC 4211): Raymond
    • C: 11:30 (GHC 4211): Andy
    • D: 12:30 (PH 125C): Abhik
    • E: 3:30 (GHC 4211): Sidhanth

  • Other Information:
    • Office hours will be listed in the calender at the bottom of this page.
    • Ask/answer questions on Piazza
    • Use gradescope to submit homework solutions (and autolab to check grades).
    • Course Policies


Overview

This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. We will also discuss a bit of Complexity Theory (which looks at the intrinsic difficulty of computational problems) as well as some String Algorithms, Computational Geometry, and Machine Learning.

By the end of this course, you should be able to:

  • Use and explain algorithm design tools discussed including Divide-and-Conquer, Balanced Search Trees, Hashing, Randomization, Dynamic Programming, Network Flows, Linear Programming, Suffix Trees and Suffix Arrays, Backward Analysis, Sweep-line algorithms, as well as basic data structure and algorithm design principles.
  • Use and explain analytical tools and frameworks discussed including Recurrences, Probabilistic Analysis, Minimax Optimality, Amortized Analysis, analysis within different Concrete Models, and Potential Functions.
  • Identify and critique incorrect analyses, finding counterexamples to faulty claims and "proofs" of correctness.


Schedule

Please keep in mind that this is preliminary and will change. The chapter numbers are from [CLRS/DPV].


Day Date Inst Topics Covered Notes and Readings HWs
Tue Aug 30 (D) Lec 1: Intro & Linear-time Selection (randomized and deterministic); recursion trees. (notes) (recurrences appendix) [Ch 9/Ch 2.4]
Thu Sep 1 (C) Lec 2: Concrete Models, Upper/Lower Bounds (notes) [Ch 8.1/Ch 2.3]
Fri Sep 2 Reci 1: Lower and Upper Bounds (worksheet) [Ch 3-4/Ch 0,2.2] HW1 Out
Tue Sep 6 (D) Lec 3: Amortized Analysis I: Bankers, Physicists, and Data Structures (notes) [Ch 17/-]
Thu Sep 8 (D) Lec 4: Amortized Analysis II: Splay trees (notes)
Fri Sep 9 Reci 2: Amortized analysis (wksheet) (solutions) [Ch 5/] HW1 Due
Sat Sep 10 HW2 Out
Tue Sep 13 (C) Lec 5: Union-find (with appendix on MSTs) (notes) HW1 Soln
Thu Sep 15 (C) Lec 6: Hashing: Universal and Perfect Hashing (notes)
Fri Sep 16 Reci 3: Hashing and Basic Probability (wksheet) (solutions)
Tue Sep 20 (C) Lec 7: Streaming Algorithms I: Heavy Hitters (notes)
Thu Sep 22 (C) Lec 8: Streaming algorithms II: locality sensitive hashing, Bloom filters (notes)
Fri Sep 23 Reci 4: Streaming + hashing (wksheet) [Ch 5/Ch 1.5]
Tue Sep 27 (D) Lec 9: Dynamic Programming I (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6] HW2 Soln
Thu Sep 29 Midterm 1 Solutions
Fri Sep 30 Reci 5: Dynamic Programming (wksheet) HW3 
Tue Oct 4 (D) Lec 10: Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall) (notes)
Thu Oct 6 (C) Lec 11: Fingerprinting and Substring Searches (notes) [Ch. 32]
Fri Oct 7 Reci 6: More DP/shortest paths (wksheet)
Tue Oct 11 (C) Lec 12: Suffix trees and arrays I: applications (notes) [??] HW3 Due (Solutions)
Thu Oct 13 (C) Lec 13: Suffix trees and arrays II: constructing (notes suffix array code)
Fri Oct 14 Reci 7: Suffix trees and arrays (wksheet) HW4 
Tue Oct 18 (D) Lec 14: Network Flows I (notes) [Ch 26/7.2-7.3]
Thu Oct 20 (D) Lec 15: Network Flows II: Edmonds-Karp 1/2, blocking flows, min-cost flows (notes) HW4 Due
Fri Oct 21 No Recitation ()
Mon Oct 24 HW5 
Tue Oct 25 (D) Lec 16: Linear Programming I: basics (notes) [Ch 29/Ch 7.1,7.6]
Thu Oct 27 (D) Lec 17: Linear Programming II: A 2D LP Algorithm (notes) [Ch 29/Ch 7.4]
Fri Oct 28 Reci 8: Flows (worksheet)
Mon Oct 31
Tue Nov 1 (D) Lec 18: Linear Programming III: Duality (notes) HW5 Due; HW5 Solns
Thu Nov 3 Midterm 2
Fri Nov 4 Reci 9: LP (worksheet)
Tue Nov 8 (C) Lec 19: NP Completeness I (definition; Independent Set, Hamiltonian Path) (notes) [Ch 34/Ch 8] HW6 
Thu Nov 10 (C) Lec 20: Approximation algorithms I: (VC, makespan, traveling salesperson) (notes) [Ch 35/Ch 9]
Fri Nov 11 Reci 10: NP-completeness and Approximations (worksheet)
Tue Nov 15 (C) Lect 21: Approximation algorithms II (LP and randomized rounding) (notes)
Thu Nov 17 (D) Lec 22: Experts and Weighted Majority Algorithms (notes)
Fri Nov 18 Reci 11: Approximation algorithms (worksheet)
Tue Nov 22 (D) Lec 23: Powerful Arrays: SegTrees and Fenwick Trees (notes) HW6 Due; HW6 Solns
Thu Nov 24 Happy Thanksgiving! HW7 
Tue Nov 29 (D) Lec 24: Online Algorithms (notes)
Thu Dec 1 (D) Lec 25: Computational Geometry I: Intro and Convex Hull (notes) [Ch 33/-]
Fri Dec 2 Reci 12: Online algorithms + comp geo (worksheet)
Tue Dec 6 (CD) Lec 26: Computational Geometry II: Sweep-Line and Segment Intersections (notes) [Ch 33/-] HW7 Due; HW7 Solns
Thu Dec 8 (D) Lec 27: Point Location Data Structures (notes)
Fri Dec 9 Reci 13: No Recitation ()
Fri Dec 16 5:30 Final Exam: CUC McConomy

Course Calendar