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,
a class project
and class participation.
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
Shenkar 105.
Course Information Handout
More details on syllabus, grading, etc. (pdf)
(see also "useful pointers" below)
Announcements
Turn in HW 6 to box 370 in Schreiber
Go
here
to sign up for PROJECT PRESENTATIONS. Prepare at most 5 minutes --
slides are fine. I'd also like a short writeup (about a paragraph)
containing what you did, what you found, and possibly
what you would have liked to have
done, some good open questions,... If your project involved
code or a proof, include the code/proof as an appendix.
January 5 lecture cancelled! Instead, lectures will be moved
back a week, and project presentations
will be done at a different time. Stay tuned for a sign up sheet
for project presentations.
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".
Lecture notes and VERY tentative plan
Lecture 1
(10/27):
Introductory remarks.
Property testing. Diameter. Monotonicity. Element distinctness.
Quick probability review.
scribe notes
Lecture 2
(11/3):
Property testing of element distinctness.
Testing properties of distributions. Uniformity.
scribe notes
Lecture 4 (11/17):
Estimating the number of connected components, minimum spanning tree. Distributed
computing vs. sublinear time: a reduction.
scribe notes
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.