Algorithmic Excursions: Topics in Computer Science II, CS:4980:0002 (22C:196:002)


The course meets 11:00 AM-- 12:15 pm Tuesday and Thursday at 27 MH (MacBride Hall).


Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, Office Hours: 1:30--3:00 Wednesday, 3:30--5:00 Thursday.

What this Course is About

In this course, we explore some advanced topics in algorithm design and analysis that are of broad interest. We study (1) approximation algorithms, that output approximately optimal solutions, focusing on geometric examples; (2) randomized schemes such as sampling and sketching; (3) algorithms in the data stream model, where the space allowed to the algorithm is typically sublinear and only a few passes through the input are allowed; (4) the multiplicative weights update method and some of its applications.

We also study topics beyond typical worst-case analysis. We examine parameterized complexity, where the input is characterized by one or more parameters in addition to the usual input size. We consider input models where the input is an `easy' instance corrupted by random noise, and review algorithm design in this setting.


We expect to use material drawn from a few different sources.


A strong background in an undergraduate level algorithms course, together with an understanding of the basic methodology of analyzing randomized algorithms is expected. The latter translates to an understanding of random variables, expectation, linearity of expectation, Markov and Chebyshev inequalities, Chernoff bounds, and their typical uses in analyzing randomized algorithms.


Each student will be responsible for a week's worth of lecture notes (slightly more if needed). This will account for 20 percent of the grade. Homeworks will account for 40 percent of the grade -- I expect there will be three to four homeworks. Class participation will account for 10 percent of the grade. And a review or survey paper will account for the remaining 30 percent. There will be no exams.

Scribed lecture notes are due within the next week after the week the student is responsible for.

The policy on late homeworks is that you have a quota of six days for the entire semester that you may use for late submissions. A maximum of three late days can be applied to any one homework. Once you use up your quota of six days, any homework submitted late will not be accepted.

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days, obtained by rounding up.

Handouts and Homeworks

Lecture Notes

All scribed notes are subject to revision -- if you spot errors do let me know.