### Course Details

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

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

Office Location: CDS 1339, 665 Comm Ave.

**Teaching Fellow:** Freddy Reiber (freddyr@).

Office Hours: CDS 1338.

OH Location: Wednesday 3–5pm.

**Lectures and Discussion Sections:**

Tuesday/Thursday 3:30–4:45pm, CDS 164.

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

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

**Important Links:**

- Course Policies: Syllabus
- For communication: Piazza (access code: algs)
- For submitting homework: Gradescope (entry code: V5PJW4)
- 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 the night of Wed. March 29, due 11:59pm Mon. April 3.

Final: Out the night of Wed. May 3, due 3pm Wed. May 10 (during assigned slot).

#### Lecture Schedule (Tentative)

The following resources may also be helpful for those who need refreshers on proof concepts:

**Building Blocks for Theoretical Computer Science**by Fleck.-
**Mathematics for Computer Science**by Lehman, Leighton, and Meyer.

**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:

**KTx**= Kleinberg and Tardos chapter x.-
**CLRSx**= Cormen, Leiserson, Rivest, and Stein chapter x. -
**Ex**= Erickson chapter x.

Date | Topic | Resources |
---|---|---|

Jan 19 | Overview and Policies, Runtime and Asymptotics | Worksheet, Notes, Slides, KT2.1-2,4, CLRS3.1-2 |

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

Jan 26 | Abstract Data Types and Graphs | Worksheet, Notes, CLRS10.1-2, 22.1, KT3.1, E5.1-4 |

Jan 31 | Depth-First Search | Worksheet, Notes, CLRS22.3, KT3.2-3 (skip BFS for now!), KT3.6, E6.1-3 |

Feb 2 | Breadth-First Search and Testing Bipartiteness | No Worksheet, Notes, KT3.2,4, CLRS22.2 |

Feb 7 | Topological Sort and Greedy Algorithms I: Dijkstra's Algorithm | Worksheet, Notes, KT4.4, CLRS24.3 |

Feb 9 | Greedy Algorithms II: Finishing Dijkstra and Interval Scheduling | Worksheet, Notes, Greedy-Stays-Ahead Guide, KT4.1 |

Feb 14 | Greedy Algorithms III: Optimal Caching | Worksheet, Notes, Greedy-Exchange Guide, KT4.3 |

Feb 16 | Greedy Algorithms IV: Scheduling to Minimize Lateness | Worksheet, Notes, KT4.2, similar to CLRS16.5 |

Feb 21 | NO CLASS (Monday schedule) | |

Feb 23 | Midterm—NO CLASS | |

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

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

Mar 7 | NO CLASS (Spring break) | |

Mar 9 | NO CLASS (Spring break) | |

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

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

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

Mar 23 | Dynamic Programming III: Knapsack | Worksheet, Notes, KT6.4 |

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

Mar 30 | Midterm—NO CLASS | |

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

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

Apr 11 | Linear Programming II: Algorithms and Problems | Worksheet, Notes, Blog Post on Simplex |

Apr 13 | Linear Programming III: Duality | Worksheet, Notes |

Apr 18 | Linear Programming IV: More Duality and Zero-Sum Games | Worksheet, Notes |

Apr 20 | The Minimax Theorem and Online Learning | Worksheet, Notes |

Apr 25 | Multiplicative Weight Update | Worksheet, Notes, Multiplicative Weights Guide |

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

May 2 | Final Exam Review | Worksheet, Notes |

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.