COMPSCI 611 - Advanced Algorithms
Welcome to the Fall 2025 course webpage for COMPSCI 611 - Advanced Algorithms.
- Instructor: Hedyeh Beyhaghi
- TAs: Fatemeh Ghaffari, Purna Dutta, Shuang Yang
- Class Time: Mondays and Wednesdays, 2:30 PM - 3:45 PM
- Location: Goessmann Laboratory room 20
- Slides: Slides will be posted on Canvas.
Textbooks
Primary Resource:
- Slides and lecture notes available on Canvas.
Additional References:
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
- Algorithm Design by Kleinberg and Tardos.
- Algorithms by Dasgupta, Papadimitriou, and Vazirani.
- Jeff Erickson’s Algorithms Textbook
Specific Topics in More Detail:
- Randomized Algorithms by Motwani and Raghavan.
- Probability and Computing by Mitzenmacher and Upfal.
- Approximation Algorithms by Vazirani.
Assessment
- Homework (25% of grade): Around 5 biweekly assignments.
- Quizzes (15% of grade): Weekly online quizzes.
- Exams (55% of grade):
- Midterm (25%)
- Final Exam (30%)
- Participation (5% of grade): Based on forum participation, i.e., asking good questions and helping other students on Piazza.
Late Policy:
- No late quizzes allowed, but the lowest quiz score will be dropped.
- Homework late days: Each student has up to 4 late days for the semester.
- You cannot use more than 2 late days per assignment.
- Late days must be used in integer increments (1 or 2 days).
- Beyond this policy, no late submissions will be accepted.
Honesty and Collaboration Policy
Violating any of the following rules risks an automatic F. Ask if you’re unsure about any of the policies.
- Homework: Collaborating with at most three other students on homework is allowed, and you must mention who you worked with. Each student must write their solutions independently. You are not allowed to use material from the web (or any material except that listed on the course page) or discuss the homework with anyone outside your collaboration group (aside from the instructor or TA).
- Quizzes: No collaboration is allowed! However, you can consult course material.
- Exams: Exams are closed-book and no collaboration is allowed.
- AI Tools: The use of AI tools (e.g., ChatGPT) is strictly prohibited for solving homework, quizzes, or exams.
Schedule
Here’s an approximate schedule for the course. Note that this will be updated as we go along depending on our progress.
| Date |
Topic |
Events |
| Sep 3 (Wed) |
Preliminaries, Mergesort, Master Theorem |
- |
| Sep 8 (Mon) |
Matrix Multiplication, Closest Pairs |
- |
| Sep 10 (Wed) |
Fast Fourier Transform |
HW1 Release |
| Sep 15 (Mon) |
Minimum Spanning Trees |
- |
| Sep 17 (Wed) |
Subset Systems, Matroids |
- |
| Sep 22 (Mon) |
Cardinality Theorem and Examples |
- |
| Sep 24 (Wed) |
Bipartite Matchings, The Union-Find Problem |
HW1 Due, HW2 Release |
| Sep 29 (Mon) |
Dynamic Programming: Knapsack, Floyd-Warshall |
- |
| Oct 1 (Wed) |
Dijkstra’s Algorithm |
- |
| Oct 6 (Mon) |
Seidel’s Algorithm |
- |
| Oct 8 (Wed) |
Network Flow Part 1 |
HW2 Due |
| Oct 13 (Mon) |
- |
- |
| Oct 15 (Wed) |
- |
Midterm (7-9 PM) |
| Oct 20 (Mon) |
Network Flow Part 2 |
- |
| Oct 22 (Wed) |
Quicksort |
HW3 Release |
| Oct 27 (Mon) |
Karger’s Algorithm |
- |
| Oct 29 (Wed) |
Tail Inequalities and Lazy Select |
- |
| Nov 3 (Mon) |
Chernoff Bounds and Balls & Bins |
- |
| Nov 5 (Wed) |
More Balls & Bins, Polynomial Multiplication |
HW3 Due, HW4 Release |
| Nov 10 (Mon) |
Approximation Algorithms |
- |
| Nov 12 (Wed) |
More Approximation: TSP & Weighted Set Cover |
- |
| Nov 17 (Mon) |
P vs. NP, Approximations, Independent Set |
- |
| Nov 19 (Wed) |
NP Completeness |
HW4 Due, HW5 Release |
| Nov 24 (Mon) |
More NP Completeness and Approximation Algorithms |
- |
| Nov 26 (Wed) |
- |
- |
| Dec 1 (Mon) |
Linear Programming, Simplex Method |
- |
| Dec 3 (Wed) |
Analysis of the Simplex Method |
HW5 Due |
| Dec 8 (Mon) |
Review |
- |
| Dec 17 (Wed) |
- |
Final Exam (3:30-5:30 PM) |
This site is powered by Just the Docs.