**Most recent message posted:
11/29/2022**

- Class meets Mondays and Wednesdays from 10:00-11:50pm, in room THH 118.
- Instructor and Teaching Assistants:

Instructor Teaching Assistant Name David Kempe Yusuf Kalayci Office SAL 232 SAL 246 "Theoroom" Office Hours Monday, 13:00-14:00

or by appointmentThursday, 10:00-11:00

or by appointmente-mail - There will be a quiz on the prerequisites on
~~Wednesday, 08/24~~Monday, 08/29, in class. - There will be one take-home midterm.
~~The final exam will be given on Monday, December 12, from 8:00-10:00am, in THH 118 (our classroom). It will be cumulative. (Sorry about the time! That was determined by the university.)~~- There will be one take-home final.
- 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 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.

- 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.

Information about Homework and Grading is on a separate page.

All students are expected to maintain the utmost level of academic integrity. Passing off anyone else's (whether it be a fellow student or someone outside the university) 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 (general overview) 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.

On takehome exams, 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.

- 11/29/2022: The course final is now posted. It is due by noon on Wednesday, December 07, in David's office. As with the midterm, it must be solved individually, and cannot be submitted late.
- 11/29/2022: The last 2 lectures cover the Multiplicative Weights Update Algorithm. You can use this excellent survey as notes for reading/studying.
- 11/29/2022: I posted some notes on game theory.
- 11/29/2022: The notes on the Randomized LP Rounding algorithm of Raghavan and Thompson are now posted.
- 11/08/2022: Homework 5 is posted. It is due in class by Wednesday, November 16.
- 11/08/2022: A basic writeup on online algorithms is available.
- 11/08/2022: The final exam will be takehome instead of in-person.
- 10/28/2022: Homework 4 is posted. It is due in class by Monday, November 07.
- 10/16/2022: The takehome midterm exam is posted. It is due in class by Monday, October 24. It must be solved individually, and cannotbe submitted late.
- 09/30/2022: Homework 3 is posted. It is due in class by Wednesday, October 12.
- 09/23/2022: The analysis of the Edmonds-Karp implementatin of the Ford-Fulkerson algorithm is not in the textbook, but you can read the material in my Edmonds-Karp handout.
- 09/19/2022: Homework 2 is posted. It is due in class by Wednesday, September 28.
- 09/02/2022: Homework 1 is posted. It is due in class by Monday, September 12.
- 08/30/2022: Fibonacci Heaps are not in the textbook, so here is a Fibonacci heaps handout.
- 08/30/2022: The quiz grades are now posted on Blackboard. Quizzes will be returned in class.
- 08/28/2022: Because I forgot to make/bring the quiz on Wednesday, we will have it in class on Monday, 08/29.
- 08/19/2022: We have a Class Piazza page for asking/answering questions (in addition to office hours and e-mail).
- 08/19/2022:
~~There will be a quiz on the prerequisite material on Wednesday, August 24.~~ - 08/19/2022: There is a Blackboard Site for this class. This is where your grades will be posted. We will not use Blackboard for any other purpose - please do not try to post in the discussion forum, since we will not monitor it.
- 08/19/2022: This is the place where you will find all of your important updates about class. Check back frequently.