CS670: Advanced Analysis of Algorithms (Fall 2022)

Most recent message posted: 11/29/2022

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

Messages, Notices, Handouts