COS597D: Thinking like a Theorist
Fall 2007 Computer Science, Princeton University
Sanjeev Arora

 
HOMEWORKS

1. 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!
2. 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.)
3. HW 3.
4. 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.