Combinatorial
Algorithms
|
Lectures: MWF
2:00-3:10PM, Baskin Engineering 169
Instructor: Dimitris Achlioptas
Phone: x9-1081
Office: BE2-343A
Office Hours: MW
1:00-2:00PM and by appointment.
|
|
The aim of the course is to explore the
breadth of ideas underlying combinatorial algorithms. The core of the
course is a subset of the recent book by Kleinberg and Tardos titled Algorithm Design
(required text).
Homework: 60%
Midterm: 20%. The midterm will be
on Friday February 10.
Final Exam: 20%
Syllabus (tentative)
- Stable Matchings (Chapter 1 of text)
- Divide-and-Conquer
algorithms and their running time (Chapter 2 of upcoming
book by Dasgupta,
Papadimitriou, Vazirani)
- Greedy
Algorithms (Chapter 4 of text)
- Dynamic
Programming (Chapter 6 of text)
- Network Flow
(Chapter 7 of text)
- Linear
Programming (Chapter 7 of DPV book)
- Fixed-parameter
tractability and tree decompositions (Chapter 10 of text)
- Approximation
Algorithms (Chapter 11 of text)
- Local Search
(Chapter 12 of text)
Per
available time and interest, the course will also include a
subset of the following topics (not covered by the text):
- Matchings in general graphs, the matching polytope, and matroid
theory
- Prices
in Markets via Network Flow (Lectures 14&15
from David Williamson’s course notes)
- The ellipsoid algorithm, separation
oracles, interior point methods and LPs with exponentially many
constraints
- A glimpse of the PCP theorem and inapproximability
- Semidefinite
programming and its use in approximation algorithms
- Markov
chain Monte Carlo algorithms
- Belief
Propagation
|
