CS G359: Network Algorithms, aka

Algorithmic Power Tools II

Spring 2008

 
Instructors:  Rajmohan Rajaraman and Ravi Sundaram

Class meeting times/location:     TuF 11:45-1:25 PM, 433 Ryder

Office Hours:    TBD

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, in particular networks.  The course will have a special emphasis on the use of techniques from other areas such as topology, harmonic analysis, high dimensional geometry and probability. 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 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 was started in the Fall.  Prof Sundaram is the person in charge of the Spring 08
course and you can approach him regarding any administration related issues.  Prof. Rajaraman was in charge of the Fall 07 course.
(The Fall 07 course is not a prerequisite for the Spring 08 course.)

A brief outline of the topics that will be covered in Spring 2008 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 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 second week of March).  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