CS G399: Topics in Theories of Computer Science

Algorithmic Power Tools I

Fall 2007

 
Instructors:  Rajmohan Rajaraman and Ravi Sundaram

Class meeting times/location:     TuF 9:50-11:30 AM, 270 WVF

Office Hours:    Tu 3:30-4:30 PM, Th 10:00-11:00 AM

Course Description       Textbook        Prerequisites        Grading

Class Participation      Project  Tentative Class Schedule (Will include all handouts)

Course Description

This course will cover some of the major techniques developed for solving hard algorithmic problems in Computer Science and related
domains.  We will present these techniques along with case studies drawn from real-world motivations and diverse applications.  The
prerequisite for the course is that the students already have an intermediate background in algorithms, i.e. big-Oh notation, divide-and-conquer, greedy algorithms, dynamic programming, NP-hardness, and basic probability theory.  The course is primarily
targeted for PhD students; interested MS students who have the required background are also welcome and should consult the instructor.

The course will be co-taught by Profs. Rajmohan Rajaraman and Ravi Sundaram.  There will be no exams.  The main deliverables of the
course will be

(a) 2-3 problem sets

(b) A term project that involves research to be conducted in teams of up to two and requires a final paper and presentation, and

(c) Class participation, including scribing one week's worth of lectures.

The course is part of a two-course series that will be continued in the Spring.  Prof Rajaraman is the person in charge of the Fall 07
course and you can approach him regarding any administration related issues.  Prof. Sundaram will be in charge of the Spring 08 course.
(The Fall 07 course will not be a prerequisite for the Spring 08 course.)

A brief outline of the topics that will be covered in Fall 2007 is given in the schedule

Reference Textbooks

There is no required textbook for the course.  We will draw material from research papers and a collection of books, four of which are listed below.

Vijay Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.   

Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995.

Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2006

Bernard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, 3rd edition, Springer, 2005.

Prerequisites

The prerequisite for this course is a graduate course in algorithms (CSG 713, CSG 113, or equivalent).  The student must be familiar with asymptotic notation, greedy algorithms, dynamic programming, graph algorithms (e.g., minimum spanning trees, shortest paths), NP-completeness.  It is strongly recommended that the student review the material on NP-completeness given in Chapter 36 of Introdution to Algorithms, Cormen, Leiserson, and Rivest, MIT Press, 1990.

If you are interested in taking the course and are not sure whether you satisfy the prerequisites, please contact the instructor.

Grading

Since this is an advanced course, we will generally avoid stress-inducing activities such as tests. The course grade will be based on 2-3 problem sets (worth 30\%), class participation (20\%), and a project (50\%).

Class Participation

Since this is expected to be a small class, I am hoping that the lectures are interactive, with discussions leading toward improved understanding of technical material, and identification of research directions. Every student is expected to scribe one week's worth of lectures. The grade for class participation will be determined by the extent and impact of the student's participation in class discussions and their contributions to the scribe notes.

Project

Students will be required to do a research project in the second half of the course.  You can work alone or in a pair. The research project should focus on an algorithmic problem, either a fundamental theoretical problem or one well-motivated by an application.  If the student is already working on a research problem relevant to the course, then a well-defined piece of the problem with specific goals can be chosen as a research project. 

Students pursuing research (or interested in pursuing research) in algorithmic application areas are strongly encouraged to formulate problems on their own for the research project.  Problem and model formulation is as important a component of research as problem-solving and will be emphasized throughout the course.  The research project could also involve a substantial implementation component.

Suggested topics for the research project will be provided by the instructor at the beginning of the course.

The project topics will be decided by the halfway point of the semester (by the third week of October).  The completion of the project will have two deliverables -- a paper and a presentation in the last 2-3 weeks of the semester.
Sample projects