CS670: Advanced Analysis of Algorithms (Spring 2025)
Most recent message posted:
03/04/2025
- Class meets Mondays and Wednesdays from 10:00-11:50, in room MHP 101.
- Instructor and Teaching Assistants:
| Instructor |
Teaching Assistant |
Name |
David Kempe |
Yusuf Kalayci |
Office |
GCS 502L |
GCS 503E Office hours in 4th floor open space |
Office Hours |
Tuesday, 13:00-14:00 (starting 01/21) or by appointment |
Thursday, 10:00-11:00 or by appointment |
e-mail |
 |
 |
- There will be a quiz on the prerequisites on
Monday, 01/20 Wednesday, 01/22, in class.
- There will be one in-class midterm, on
Monday, 03/03Wednesday, March 05.
- The final exam will be given on
Friday, May 09, from 11:00-13:00Monday, May 12, from 8:00-10:00 in the morning. (Sorry about that! That's the time according to the USC course calendar.) Barring other information, it will be in our classroom, MHP 101.
- This is the advanced version of the graduate algorithms class.
The advanced class is required of Ph.D. students in computer science.
All other students can choose between CSCI 570 and CSCI 670.
If you are trying to decide on one of the two, consider your background
and interest in the subject. CSCI 670 will strictly assume solid
undergraduate backgroung in algorithms and discrete math, whereas CSCI 570
spends more time on reviewing that material. The homeworks and exams in
CSCI 670 are significantly more challenging.
- The instructor office hours per default will be in GHC 502L. If you do not have access to the fifth floor of GHC (because you are an undergraduate or MS student), please reach out by e-mail before coming to office hours, and we can arrange to meet on the first floor, either staying there, or I can let you into the fifth floor.
Course Overview, Syllabus, Textbook, Prerequisites
The course is intended as a first graduate course in the design and
analysis of algorithms. While the main focus is on known and
well-established results in the literature, there will be many
times when the course will touch on uncharted territory, or
suggest directions for research. The course will give an overview
of common techniques, and applications of these techniques in
different settings. Look also at the more detailed
syllabus.
The textbook is
- Jon Kleinberg/Éva Tardos: Algorithm Design.
The book will be available at the campus store.
The class will be relying mostly on the textbook, but additional
material will occasionally be drawn from the following books:
- Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms (2nd edition)
- Dasgupta/Papadimitriou/Vazirani: Algorithms
- Garey/Johnson: Computers and Intractability
- Motwani/Raghavan: Randomized Algorithms
- Vazirani: Approximation Algorithms
- Borodin/El-Yaniv: Online Algorithms
Students in the class are expected to have a reasonable degree of
mathematical sophistication, and to be familiar with the basic
notions of algorithms and data structures, discrete mathematics,
and probability. Specifically, the following will be assumed:
- Mathematical Proofs, in particular induction and contradiction.
- Big-Oh notation (Big-O, Omega, Theta), how to apply them.
- Basic data structures: arrays, linked lists, trees, balanced
trees, heaps (priority queues), graphs.
- Basic graph algorithms: connected components, BFS, DFS.
- Other algorithms: binary search, sorting.
- Discrete mathematics: evaluating sums and simple recurrences.
Undergraduate classes in these subjects should
be sufficient. If you have doubts about meeting these
prerequisites, please contact the instructor. Notice that these
prerequisites will actually be verified with a quiz during the
first week of classes.
Information about Homework and Grading
is on a separate page.
Academic Integrity, Collaboration
All students are expected to maintain the utmost level of academic integrity. Passing off anyone else's (whether it be a fellow student, someone outside the university, or an LLM model or other software solution) work as your own is a serious infraction, and will lead to appropriate sanctions.
Similarly, any collaboration during exams is prohibited.
Please consult the USC
Student Conduct Code for details on what is and is not appropriate, and for the possible consequences of infractions.
My default policy in Ph.D. level classes is that any kind of cheating will lead to an 'F' grade in the class, a report to the university, and to notification of your Ph.D. advisor.
However, as research is usually a joint effort, students are encouraged to collaborate with other students in the class on general solution strategies for homework.
The writeup, however, must be your own - you may not copy someone else's solution. Here is the rule of thumb to follow to avoid overstepping appropriate collaborations: if you discuss ideas or algorithms with your classmates, before you leave the meeting, you destroy all written notes, and write your own solutions from scratch afterwards, with a delay of at least an hour between the discussion and the time when you write your solution.
Also, your homework should list all the fellow students with whom you discussed the solutions. Collaboration is restricted to fellow students inside the class; collaboration with students outside the class or others (such as discussion groups on the WWW) are not appropriate, and will lead to appropriate sanctions.
In days of increasingly more sophisticated AI solutions (LLMs and any related technology), the class policy is that their use is prohibited in all instances, except when explicitly allowed. The rationale is that when interacting with classmates, you are presumably engaging your brain in struggling with and learning material, whereas an AI will just give you a solution (which may be correct or wrong), but not engage your own reasoning.
On takehome exams (which as of current plans, we will not have this semester), any collaboration with classmates is strictly prohibited. The only acceptable behaviors are solving the exam yourself (using your class notes and the textbook), or asking the TA and instructor for help.
You should behave exactly as if you were sitting in a proctored exam.
- 03/04/2025: Here are some lecture notes on the Edmonds-Karp Algorithm.
- 03/04/2025: Here are some lecture notes on Fibonacci Heaps.
- 03/04/2025: The third homework assignment has been posted. It is due by Wednesday, 03/12/2025.
- 02/19/2025: The second homework assignment has been posted. It is due by Wednesday, 02/26/2025.
- 01/28/2025: The first homework assignment has been posted. It is due by Monday, 02/10/2025.
- 01/28/2025: The date for the final exam has been corrected.
- 01/12/2025: We have a
Class Piazza page
for asking/answering questions (in addition to office hours and e-mail).
- 01/12/2025: There will be a quiz on the prerequisite material
on
Monday, January 20Wednesday, January 22.
- 01/12/2025: There is a Brightspace Site for this class. This is where your grades will be posted.
We will not use Brightspace for any other purpose - please do not try to post in the discussion forum, since we will not monitor it.
- 01/12/2025: This is the place where you will find all of your
important updates about class. Check back frequently.