Computer Science 49/149
Where: Sudikoff 115
When: 2A hour: TTh 14:25-16:15, X-hr W 16:35-17:25
Who: Instructor: Amit Chakrabarti,
Sudikoff 107, Office hours: Fri 15:00-16:00
What: Computer science is all about using limited resources efficiently. An course in Algorithms course teaches you several techniques to design resource-efficient solutions to computational problems. In this course, we ask the companion question: what can a computer not do when we limit a crucial resource? Equivalently, what lower bounds can we prove on the amount of resources required to solve a problem?
Proving lower bounds is the ultimate challenge of theoretical computer science. Here is a relevant cartoon, which should give you some flavor of the course and leave you intrigued.
Prerequisites: An undergraduate-level course
in Algorithms (such as our CS 31)
Syllabus: The following is a rough outline. Some more detail will be added at the start of term, and an approximate day-by-day plan will be announced shortly after.
Textbooks: There is no set textbook for this course, but we have some evolving in-house course notes, thanks to the scribing efforts of students from the previous offering of the course. A good fraction of the material we shall study only resides in research papers.
Homework: We will have about 20 homework problems divided into six or seven homework sets. We will mostly stick to the following schedule: homework will be given out on a Tuesday and it will be due by 11:59 pm the following Monday.
Class Presentation: In lieu of a final exam, students are required to read up on a paper/topic in the general area of lower bound theory, and give a short, 30-minute presentation on its main ideas. Below is a list of suggested papers for such a presentation.