This course will focus on the design of algorithms that are restricted
to run in sublinear time, and thus can view only a very
small portion of the data. The study of sublinear time
algorithms has been applied to problems from a wide range
of areas, including algebra, graph theory, geometry, string
and set operations, optimization and probability theory.
This course will introduce many of the various techniques
that have been applied to analyzing such algorithms.
Grading
Will be based on the solutions to homework exercises
and class participation. Undergraduates will also have a final exam.
Prerequisites
Algorithms. Exposure to computational complexity is helpful but not
required.
Time and location
The course will take place on Mondays, 13:00-16:00, in
Physics-Shenkar 204.
Course Information Handout
More details on syllabus, grading, etc. (pdf)
(see also "useful pointers" below)
Announcements
Jan 4: I am cancelling problem 2 of HW 3, but try to
do it anyhow.
Jan 2: Homework 4 is posted!
Dec 27: Homework 3 is posted! There are only two
problems. The due date is two weeks
from tomorrow's lecture, but I will hand out more problems in
each of the next lectures.
On December 14, we will start a few minutes late
because of
this talk
by Laszlo Lovasz.
If you are not familiar with
Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about
them in one or more of the descriptions given below in "useful pointers".
November 2.
Distributed computing vs. sublinear time: A reduction
and a distributed algorithm. Approximating
vertex cover and maximal matching in sublinear time.
(latex source)
For future scribes, here is a
sample file and
the preamble.tex file that
it uses.
Please get a first draft to me by the Thursday following the
lecture.
See
here
for a few tips.