Design and
Analysis of Algorithms
0510.6401
Administrative Information.
Course site (this page): http://www.eng.tau.ac.il/algs
Lectures: Mondays 4-7, kitot
103.
Final exam: February 13, 2pm (in-class exam)
Lecturer: Boaz Patt-Shamir, boaz@eng.tau.ac.il.
Course mailing list (see instructions):
http://listserv.tau.ac.il/archives/0510-6401-01.html
Objective
of the Course.
This
course aims at three targets. First, to cover some basic algorithmic techniques
most engineering students did not study in their undergraduate courses. Another
is to get the students acquainted with a selection of the advanced techniques
in algorithmic theory. Finally, we try 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 intention is to equip students with some tools that will help them in more
advanced courses, be it in algorithms or another area of study. The topics are
selected in light of these guidelines.
Topics. The course will include
topics from the following list.
· Classical
optimization: graph algorithms, dynamic programming, flows, linear programming.
· Approximation
algorithms: NP Hardness, approximation ratio and approximation schemes, load
balancing, vertex and set cover, traveling salesman.
· Randomized
algorithms: Basic analyses, coupon collector, median; randomized rounding;
random sampling.
· Online
problems: ski rental, self-organizing lists, best-expert and bandit, paging,
load balancing, call admission and routing in communication networks.
· Distributed
and parallel computation: models and algorithms. Algorithms include
Bellman-Ford, maximal matching and maximal independent set, coloring,
minimum-weight spanning tree.
Requirements.
1.
Homework will assigned every week or two.
The final grade will consist of 10% homework grades and 90% final exam. Every
student may skip one homework submission.
2.
Each lecture, one of the students will be
assigned as a scribe. This means that the student will be responsible to
taking careful notes and publishing them in electronic form. The idea is to help
all students to have a “standard” notebook for the course.
Bibliography.
1.
Introduction
to Algorithms, 3rd ed. Cormen, Leiserson, Rivest and Stein
(CLRS). MIT Press, 2009. Comprehensive. A
Hebrew version of the first edition was published by the Open University in
two
parts.
2.
Algorithm Design.
Modern approach. Kleinberg and Tardos (KT).
Addison-Wesley, 2005. Half of the book was translated into Hebrew and adapted
to an Open University course.
3.
Online Algorithms and
Competitive Analysis. Borodin and El-Yaniv (BE).
4.
Distributed Computing: A
Locality-Sensitive Approach. Best source on network algorithms. D. Peleg
(P).
5.
Probability
and Computing: Randomized Algorithms and Probabilistic Analysis. Mitznmacher
and Upfal (MU).
Additional bibliography
may be provided during the course.
Lecture notes
1. Lecture 1 (load balancing, subset sum).
2. Lecture 2 (P, NP, NP-hardness)
3. Lecture 3 (Approximation algorithms)
4. Old notes for the material in Lecture 4 (Set Cover,
weighted Vertex Cover)
5. Lecture 5 (k centers, dynamic programming)
6. Old notes for the material in Lecture 6 (secretary
problem, coupon collector, birthday paradox)
7. Lecture 7 (conflict resolution, median, Chernoff bound,
parameter estimation)
8. Lecture 8 (balls and bins)
9. Lecture 9 (online algorithms: ski rental, related
machines, restricted assignment)
10. Old notes for lecture 10 and more (self-organizing lists,
cache replacement)
11. Lecture 11 (Randomized online algorithms: ski rental,
repeated doubling, cache replacement)
12. Lecture 12 (Randomized lower bounds on the competitive
ratio, and the Best Expert algorithm).
13. Lecture 13 (Distributed algorithms 1: coloring, leader
election on a ring)
14. Lecture 14 (Distributed algorithm 2: lower bounds for leader
election and 3-coloring on rings)
Homework assignments and solutions.
1. Problem set 1 (due November 7). Solutions
2. Problem set 2 (due November 14). Solutions
3. Problem set 3 (due December 12 19). Solutions.
4. Problem set 4 (due December 19 26). Solutions.
5. Problem set 5 (due January 2). Solutions
6. Problem set 6 (due January 9). Solutions
7. Problem set 7 (due January 23). Solutions.
Grades
·
summary
1. PS1
2. PS2
3. PS3
4. PS4
5. PS5
6. PS6
7. PS7
Past Exams
Miscellaneous
references
2.
Bounds
on the binomial coefficients (including proofs).
3.
A Compendium
of NP-Complete Problems.
4.
A variety of
Chernoff bounds.
5.
Solving
first-order ordinary differential equations.
6.
Daniel Sleator’s
Splay Trees demo