COS597D: Thinking like a Theorist

Fall 2007 Computer Science, Princeton University

Sanjeev Arora

HOMEWORKS

- HW1: The first two lectures discussed the effect of introducing noise/error in the familiar setting of binary search.Take some other algorithmic problem from your ugrad course and study the effect of introducing error/noise in it. Be sure to check prior work on google scholar!
- HW 2: The algorithm for circuit switching takes O(log N) steps per level, and therefore O(log^2 N) steps total. Show how to do the circuit switching in O(log N) steps. Your algorithm should only use local control. (You can find the solution in a published paper but please try to do it by yourself first.)
- HW 3.
- HW 4 (for Fall Break): Make a short list of topics that you would
like to (a) hear about in a course called "Thinking like a theorist."
(b) that you would like to do research in.

Then read a research paper on one of those topics and write a brief (1-2 page) report on it. Hand it in together with the above two lists.