Course Details
Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 5–6pm and by appointment.
Office Location: 111 Cummington Mall, 138P.
Teaching Fellow: Habeen Chang (ahc98@).
Office Hours: Monday 11:30am–12:30pm.
OH Location: 111 Cummington Mall, Room 103.
Lectures and Discussion Sections:
Tuesday/Thursday 3:30–4:45pm, BRB 121.
Discussion Section A2: Monday 9:05-9:55am, CGS 111A.
Discussion Section A3: Monday 10:10-11:00am, IEC B06.
Important Links:
- Course Policies: Syllabus
- To ask questions: Piazza
- For submitting homework: Gradescope entry code GERZ2Z
- What to expect from this course: FAQ
Homework: Homeworks will be posted on Piazza when they become available. Homework must be typed up using LaTeX; here is a quick resource on LaTeX and here is a LaTeX template you may use for the homework. Here is another short guide to LaTeX. You may find it easier to use Overleaf.
Important Dates
Midterm I: Out the night of Wed. Feb 23, due 11:59pm Mon. Feb 28.
Midterm II: Out first thing Thurs. March 31, due 2:59pm Tues. April 5.
Final: May 11, 3-5pm, BRB 121.
Lecture Schedule
Below is a table with that will reflect what we cover in each lecture and will point to corresponding reading material. There is no required textbook for this course, as all materials are available online for free and we will switch between materials. Some shorthand for the reading material:
Date | Topic | Resources |
---|---|---|
Jan 20 | Overview and Policies, Runtime and Asymptotics | Slides, Notes, KT2.1-2,4, CLRS3.1-2 |
Jan 25 | Insertion Sort, Induction, and the Comparison-Based Lower Bound | Notes, Induction Guide, CLRS2.1 |
Jan 27 | Abstract Data Types and Depth-First Search | Notes, KT3.1-3 (skip BFS for now!) |
Feb 1 | More DFS, Topological Sort | Mitzenmacher's notes, KT3.6 |
Feb 3 | Breadth-First Search and Testing Bipartiteness | KT3.2,4 |
Feb 8 | Greedy Algorithms I: Dijkstra's Algorithm | Greedy-Stays-Ahead Guide, KT4.4, CLRS24.3 |
Feb 10 | Greedy Algorithms II: Optimal Caching | Notes, Greedy-Exchange Guide, KT4.3 |
Feb 15 | Greedy Algorithms III: Scheduling to Minimize Lateness | KT4.2, similar to CLRS16.5 |
Feb 17 | Greedy Algorithms IV: Huffman Codes | KT4.8, CLRS16.3 |
Feb 22 | NO CLASS (Monday schedule) | |
Feb 24 | Midterm—NO CLASS | |
Mar 1 | Divide & Conquer I: Mergesort, Solving Recurrences | Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
Mar 3 | Divide & Conquer II: Closest Pair of Points | Worksheet, Notes, KT5.4 |
Mar 8 | NO CLASS (Spring break) | |
Mar 10 | NO CLASS (Spring break) | |
Mar 15 | Divide & Conquer III: Integer and Matrix Multiplication | Worksheet, Notes, KT5.5, CLRS4.2, Mitzenmacher's notes |
Mar 17 | Dynamic Programming I: Weighted Interval Scheduling | Dynamic Programming Guide, KT6.1-6.2 |
Mar 22 | Dynamic Programming II: Segmented Least Squares | Worksheet, Notes, KT6.3 |
Mar 24 | Dynamic Programming III: Knapsack | KT6.4 |
Mar 29 | Dynamic Programming IV: Bellman-Ford | Worksheet, Notes, KT6.8 |
Mar 31 | Midterm—NO CLASS | |
Apr 5 | NP Completeness | Worksheet, Notes, KT8.2-3, KT8/CLRS34 for addtl reading |
Apr 7 | Linear Programming I: Introduction | Worksheet, Notes, KT8.1, KT11.6 |
Apr 12 | Linear Programming II: Examples and Duality | Worksheet, Notes |
Apr 14 | Linear Programming III: More Duality | Worksheet, Notes |
Apr 19 | Zero Sum Games and the Minimax Theorem | Worksheet, Notes |
Apr 21 | Multiplicative Weight Update | Worksheet, Notes |
Apr 26 | Stable Matching | Worksheet, Notes, KT1.1, KT2.3 |
Apr 28 | Approximation Algorithms: Random and Online | Worksheet, Notes |
May 3 | Final Exam Review | Worksheet, Notes, Linear Programming Guide, Complexity Guide, Multiplicative Weights Guide |
Huge gratitude to Justin Thaler, Adam Smith, Sam Taggart, Alexa Sharp, Tom Wexler, Michael Mitzenmacher, Tim Roughgarden, and Aaron Roth for their materials and/or for their publicly available lecture notes which have made the development of this course possible.