0510.6401
|
Administrative
Information. Lectures: Mondays 4-7 Lecturer: Dana Ron, Course URL (this page): |
|
|
|
|
Objectives of the Course.
This
course aims at two targets. One is to get the students acquainted with a
selection of the advanced techniques in algorithmic theory, and the other is to
let the students experience what is the spirit in contemporary algorithmic
research. Namely, what problems are considered interesting, and how to evaluate
possible solutions. The topics are selected in light
of these guidelines.
Topics.
The course
will include topics from the following list.
· Approximation
background: Decision and optimization problems, NP Hardness, approximation
algorithm, approximation scheme.
· Basic
approximation algorithms: load balancing, vertex and set cover, traveling
salesman, subset sum, knapsack.
· Randomized
algorithms: the probabilistic method with applications to max-cut and max-SAT;
randomized rounding; random sampling.
· Online
problems: ski rentals, self-organizing lists, best-expert and bandit, paging,
load balancing, call admission in communication networks.
· Distributed
and parallel computation: models and algorithms. Algorithms include
Bellman-Ford, maximal independent set, prefix sums, minimum spanning tree.
Requirements.
Homework
will be assigned about every two weeks. The final grade will consist of 10%
homework grades and 90% final exam. Every student may skip one homework
submission.
Bibliography. Since we will be looking into diverse areas, no single book
covers all the material. The most comprehensive book is the classical [CLRS]
below. Specialized texts for approximation and randomized algorithms are [V]
and [MR], respectively. For an introduction to computational learning theory,
see [KV]. For on-line algorithms, see [BE]. [P] is an
excellent introduction to distributed network algorithms.
1.
Introduction to Algorithms.. Cormen, Leiserson, Rivest and Stein
(CLRS). MIT Press, 2001.
A Hebrew version of the first edition was published by the Open University in
two parts: Part
I, Part
II.
2.
Randomized
Algorithms, Motwani and Raghavan (MR). Cambridge University Press, 1995.
3. Approximation Algorithms, Vazirani (V). Springer-Verlag, Berlin, 2001.
4.
An
Introduction to Computational Learning Theory,
5.
Online Algorithms and
Competitive Analysis, Borodin and El-Yaniv (BE). Cambridge University
Press, 1998.
6.
Distributed Computing: A
Locality-Sensitive Approach, D. Peleg (P). SIAM, 2000.
Additional
bibliography may be provided during the course.
Class
Notes
(If
you see any typos/errors, please let me know)
Homework
assignments and solutions.
Homeworks
will be posted on this site about every two weeks (each with its submission
date).
As noted above, you may skip one homework.
If you cannot submit an assignment on time due to “Miluim” or illness, you
should contact me in advance.
Otherwise, every day in which there is a delay comes at a “cost” of 10% in the
grade of that homework.
Miscellaneous.
1.
Further reading on P
vs. NP and other questions in Complexity
(you can read just the first few pages of the survey).
2.
A Compendium
of NP Optimization Problems.
3.
Some notes on Dynamic
Programming (from the undergraduate course I give).
4.
A paper (by G. Woeginger) on problems that have an FPTAS.
7.
Bounds
on the binomial coefficients (including proofs). The bound on the sum of
binomial coefficients (used in the analysis or random linear codes)
