CS 7880: Topics in Theories of Computer Science

Algorithmic Power Tools

Fall 2009

 
Instructor:  Rajmohan Rajaraman

Class meeting times/location:     TuF 11:45 AM-1:25 PM, 9 Snell

Office Hours:    MTh 4:00-5:00 PM

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.

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.


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

Reference Textbooks

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

Noga Alon, Joel Spencer, and Paul Erdos, The Probabilistic Method, Wiley, 1992.

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.