### Course Details

**Instructor:** Professor Kira Goldner (goldner@).

Office Hours: Tuesday 5–6pm and by appointment.

Office Location: 111 Cummington Mall, 138P.

**Teaching Fellow:** TBD.

Office Hours: TBD.

OH Location: TBD.

**Lectures and Discussion Sections:**

Tuesday/Thursday 3:30–4:45pm.

Discussion Section A2: Monday 3:30-4:25pm.

Discussion Section A3: Monday 4:40-5:30pm.

**Important Links:**

- Course Policies: Syllabus
- For communication: Piazza
- For submitting homework: Gradescope
- 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 (Tentative)

Midterm I: Out the night of Wed. Feb 22, due 11:59pm Mon. Feb 27.

Midterm II: Out first thing Thurs. March 30, due 2:59pm Tues. April 4.

Final: TBD.

#### Lecture Schedule (Tentative)

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 19 | Overview and Policies, Runtime and Asymptotics | KT2.1-2,4, CLRS3.1-2 |

Jan 24 | Insertion Sort, Induction, and the Comparison-Based Lower Bound | Induction Guide, CLRS2.1 |

Jan 26 | Abstract Data Types and Depth-First Search | KT3.1-3 (skip BFS for now!) |

Jan 31 | More DFS, Topological Sort | Mitzenmacher's notes, KT3.6 |

Feb 2 | Breadth-First Search and Testing Bipartiteness | KT3.2,4 |

Feb 7 | Greedy Algorithms I: Dijkstra's Algorithm | Greedy-Stays-Ahead Guide, KT4.4, CLRS24.3 |

Feb 9 | Greedy Algorithms II: Optimal Caching | Greedy-Exchange Guide, KT4.3 |

Feb 14 | Greedy Algorithms III: Scheduling to Minimize Lateness | KT4.2, similar to CLRS16.5 |

Feb 16 | Greedy Algorithms IV: Huffman Codes | KT4.8, CLRS16.3 |

Feb 21 | NO CLASS (Monday schedule) | |

Feb 23 | Midterm—NO CLASS | |

Feb 28 | Divide & Conquer I: Mergesort, Solving Recurrences | Divide & Conquer Guide, KT5.1, CLRS4.3-5 |

Mar 2 | Divide & Conquer II: Closest Pair of Points | Worksheet, KT5.4 |

Mar 7 | NO CLASS (Spring break) | |

Mar 9 | NO CLASS (Spring break) | |

Mar 14 | Divide & Conquer III: Integer and Matrix Multiplication | Worksheet, KT5.5, CLRS4.2, Mitzenmacher's notes |

Mar 16 | Dynamic Programming I: Weighted Interval Scheduling | Dynamic Programming Guide, KT6.1-6.2 |

Mar 21 | Dynamic Programming II: Segmented Least Squares | Worksheet, KT6.3 |

Mar 23 | Dynamic Programming III: Knapsack | KT6.4 |

Mar 28 | Dynamic Programming IV: Bellman-Ford | Worksheet, KT6.8 |

Mar 30 | Midterm—NO CLASS | |

Apr 4 | NP Completeness | Worksheet, KT8.2-3, KT8/CLRS34 for addtl reading |

Apr 6 | Linear Programming I: Introduction | Worksheet, KT8.1, KT11.6 |

Apr 11 | Linear Programming II: Examples and Duality | Worksheet |

Apr 13 | Linear Programming III: More Duality | Worksheet |

Apr 18 | Zero Sum Games and the Minimax Theorem | Worksheet |

Apr 20 | Multiplicative Weight Update | Worksheet |

Apr 25 | Stable Matching | Worksheet , KT1.1, KT2.3 |

Apr 27 | Approximation Algorithms: Random and Online | Worksheet |

May 2 | Final Exam Review | Worksheet , 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.