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 104.
Course Information Handout
More details on syllabus, grading, etc. (pdf)
(see also "useful pointers" below)
HW5 is out!
Please submit directly to Edo Cohen's cell in Schreiber 316
on the due date.
For projects: (1) I'd like to get a written 1-2 page "executive summary"
of what the project was about (what you hoped to do, what you found/did
what progress you made, what roadblocks you found....), followed
by any necessary supporting materials.
(2) A 5-10 minute presentation on the project.
All students in the course are invited to attend all presentations.
There will be a sign up sheet posted soon. The presentations will be held
during the week of January 24-27.
We have a grader! He is Edo Cohen. Please write your solutions
as clearly as possible, as he is already going to suffer a lot from our big class.
His email is sublinear2015@gmail.com
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
(19/10):
Introductory remarks.
Property testing. Diameter. Monotonicity. Element distinctness.
Quick probability review.
scribe notes (25/10)
Lecture 2
(26/10):
Property testing of element distinctness.
Testing properties of distributions. Uniformity.
scribe notes
Lecture 6
(23/11):
Sublinear time algorithms via simulating the greedy algorithm:
Approximating vertex cover (thru maximal matching).
Approximating the average degree.
scribe notes.
Lecture 13
(11/1):
No class -- will have project presentations instead on the
week of January 24. See announcement for project requirements.
Homework
Homework 0
Handed out 19/10 (updated 23/10 19:00).
Don't turn in, but do by 26/10.
Homework 1
Handed out 26/10 (updated 4/11 22:20).
Due on 9/11 in class.
All problems will be easier after lecture 3, but ok to start doing problem 1,2,3ab,4a.
It might even help you follow the lecture.
Homework 2
Partially Handed out 9/11, more problems added on 13/11 (updated 22/11 15:40).
Due on 23/11 in class.
NOTE NEW DUE DATE AND EXTRA PROBLEMS.
Note that the scanned notes from lecture 3 may help with problem 1.
Homework 3
Handed out 30/11 (updated 7/12 13:00).
Due on 14/12 in class.
Homework 4
Handed out 14/12. (updated 27/12 22:00).
Due 28/12 in class.
Homework 5
Handed out 28/12.
Due 11/1.
Please submit directly to Edo Cohen's cell in Schreiber 316
on the due date.
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.