Fall 2024, Senior Year
Professor Paul Valiant
Link Hub
- Analyzing Code
- Divide and Conquer Algorithms
- Dynamic Programming
- Greedy Algorithms
- Information Compression
- NP-Completeness
- Max Flow and Min Cut
- Data Structures and Online Algorithms
- Advanced Topics
Course Description
This course is an introduction to the design and analysis of algorithms, emphasizing the creative
process of designing a new algorithm, and the formal tools needed to rigorously understand why
an algorithm works. This course strongly emphasizes communication skills—including reading,
listening, writing, and speaking—which are needed both to understand and to convince others of
the subtle and counterintuitive algorithms we will develop in this course. This course aims to
give students a toolbox of sophisticated algorithmic design principles that will be useful both in
industry, and as a basis for future academic progress in CS.
Algorithmic topics include selections from textbook chapters 2 (divide and conquer), 5 (greedy
algorithms), 6 (dynamic programming), 7.2-7.3 (flows in graphs) and 8 (NP-completeness), as well
as additional material on data structures, information compression, and some additional advanced
topics chosen by the class.
Overall
General Class Info
- Textbook: Algorithms. Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani. 2006 (∼$40 but can be found online).
- 2 Midterms
- PSO’s are collab hours
- You can choose to go to any PSO
- TA’s will be there to help everyone through homework and understanding material
- Can come at any stage in homework process
- Brightspace, Gradescope, Ed Discussion
- Final grade is 35% homework, 20% midterm 1, 20% midterm 2, 25% final exam
- POTENTIALLY 5% extra credit for participation in collab hour and other related study things. TBD
- Each homework submitted at least 3 days early will receive a 5% bonus.
- Any homework after the due date will receive 20% deduction up until 2 days after due date, after that its not accepted.
- These two above points apply per question on the homework, so submit what you can do early to get bonus on it
- You can collaborate on homework if needed, but no directly sharing words/phrasing/code/notation etc.
- Use Overleaf/LaTeX for homework but draw diagrams by hand
- “Good pseudocode should be at most 10 lines long”
- Lectures might be recorded but no guarantees