CSCI 670, Spring 2012
Advanced Analysis of Algorithms

Course descriptions and objectives

The course is intended as a first Ph.D. course in the design and analysis of algorithms. While the main focus is on known and well-established results in the literature, we will also cover topics of potential research interests.

The course will give an overview of common techniques, and applications of these techniques in different settings.

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.

Instructor

Professor Shang-Hua Teng
Office hours: Monday 4:00 -- 5:00pm or by appointment;
Email : shanghua[]usc.edu

TA

Anand Narayanan  

Email: aknaraya[]usc.edu

Textbook

Algorithm Design
Jon Kleinberg and Eva Tardos

The class will also cover additional material drawn from research papers as well as other books in Theoretical Computer Science.

Lectures

2:00-3:20pm Tuesdays and Thursdays, in room KAP 158.  

Grades

45% - 15% each - Quizzes on homeworks (closed book & notes), Midterm 25% (open book), Final 30% (open book)

Exams

3 quizzes, midterm and final

Homeworks

Integrity

Plagiarism and other anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University.