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

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

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

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

Noga Alon, Joel Spencer, and Paul Erdos,

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.

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

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\%).

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.