Lectures: Mondays 4-6
Lecturer: Dana Ron, danar at eng.tau.ac.il.
Office hours: Can be coordinated by email.
Brief Course Description:
for a wide range of areas, including algebra, graph theory, geometry, string and set operations, optimization and probability theory. The course will introduce many of the various techniques that have been applied to analyzing such algorithms.
The course will include topics from the following list.
graphs: Bipartitness, r-Clique, first order graphs properties
(using the regularity lemma).
v Bounded-degree and sparse graphs: Connectivity, Diameter.
v Directed graphs: Acyclicity.
The course is based on several papers that have been published in the
last few years. The course web-site will include pointers to all these papers.
Most of these papers can be downloaded by clicking here.
Homework will be assigned
about every two weeks.
Cooperation is allowed but each student must write his/her own solution.
There will be a final project that will involve reading, summarizing, and presenting
research papers on sublinear algorithms.
Disclaimer: these notes were not carefully proof-read (please let me know if you find typos/errors)
A list of papers (roughly a subset of the large Princeton bibliography) from which you can select your project.
Pointers to papers on which the lectures were based
(some pointers may need to be updated since have newer versions)