COMPSCI 611 - Advanced Algorithms
Welcome to the Spring 2025 course webpage for COMPSCI 611 - Advanced Algorithms.
- Instructor: Hedyeh Beyhaghi
- TAs: Vinayak, Vignesh Viswanathan
- Class Time: Tuesdays and Thursdays, 2:30 PM - 3:45 PM
- Location: Hasbrouck Lab Room 124
- Slides: Slides will be posted on Canvas.
Textbooks
Recommended Resources:
Additional References:
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
- Algorithm Design by Kleinberg and Tardos.
- Algorithms by Dasgupta, Papadimitriou, and Vazirani.
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%) - March 11, 7-9 PM
- Final Exam (30%) - May 12
- 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. 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 |
| Jan 30 (Thu) |
Preliminaries, Mergesort, Master Theorem |
- |
| Feb 4 (Tue) |
Matrix Multiplication, Closest Pairs |
HW1 Release |
| Feb 6 (Thu) |
Fast Fourier Transform |
- |
| Feb 11 (Tue) |
Minimum Spanning Trees |
- |
| Feb 13 (Thu) |
Subset Systems, Matroids |
- |
| Feb 18 (Tue) |
Cardinality Theorem and Examples |
HW1 Due, HW2 Release |
| Feb 20 (Thu) |
- |
- |
| Feb 25 (Tue) |
Bipartite Matchings, The Union-Find Problem |
- |
| Feb 27 (Thu) |
Dynamic Programming: Knapsack, Floyd-Warshall |
- |
| Mar 4 (Tue) |
Dijkstra’s Algorithm |
HW2 Due |
| Mar 6 (Thu) |
Seidel’s Algorithm |
- |
| Mar 11 (Tue) |
- |
Midterm (7-9 PM) |
| Mar 13 (Thu) |
Network Flow Part 1 |
- |
| Mar 16–23 |
Spring Break |
- |
| Mar 25 (Tue) |
Network Flow Part 2 |
HW3 Release |
| Mar 27 (Thu) |
Quicksort |
- |
| Apr 1 (Tue) |
Karger’s Algorithm |
- |
| Apr 3 (Thu) |
Tail Inequalities and Lazy Select |
- |
| Apr 8 (Tue) |
Chernoff Bounds and Balls & Bins |
HW3 Due, HW4 Release |
| Apr 10 (Thu) |
More Balls & Bins, Polynomial Multiplication |
- |
| Apr 15 (Tue) |
Approximation Algorithms |
- |
| Apr 17 (Thu) |
More Approximation: TSP & Weighted Set Cover |
- |
| Apr 22 (Tue) |
P vs. NP, Approximations, Independent Set |
HW4 Due, HW5 Release |
| Apr 24 (Thu) |
NP Completeness |
- |
| Apr 29 (Tue) |
More NP Completeness and Approximation Algorithms |
- |
| May 1 (Thu) |
Linear Programming, Simplex Method |
- |
| May 6 (Tue) |
Analysis of the Simplex Method |
HW5 Due |
| May 8 (Thu) |
Review |
- |
| May 12 (Mon) |
- |
Final Exam |
This site is powered by Just the Docs.