### 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.