COS597D: Thinking like a Theorist
Fall 2007 Computer Science, Princeton University
- 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
- 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.