CS 7880: Topics in Theories of Computer Science
Algorithmic Power Tools
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
A brief outline of the topics that will be covered in the course is
given in the schedule
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,
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,
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,
graph algorithms (e.g., minimum spanning trees, shortest paths),
NP-completeness. It is strongly recommended that the student
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.
Since this is an advanced course, we will generally avoid
stress-inducing activities such as tests. The course grade will be
on 2-3 problem sets (worth 30\%), class participation (20\%), and a
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.
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
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.