CS670: Advanced Analysis of Algorithms (Spring 2025)

Most recent message posted: 04/21/2025

Administrativa

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

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:

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:

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.

Homework, (Re-)Grades, late homework

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.

Messages, Notices, Handouts