Computer Science Dartmouth College 
Computer Science 49/149 
Winter 2017 
Where: Sudikoff 115 When: 2A hour: TTh 14:2516:15, Xhr W 16:3517:25 Who: Instructor: Amit Chakrabarti,
Sudikoff 107, Office hours: Fri 15:0016:00 What: Computer science is all about using limited resources efficiently. An course in Algorithms course teaches you several techniques to design resourceefficient 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 undergraduatelevel 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 daybyday plan will be announced shortly after.
Textbooks: There is no set textbook for this course, but we have some evolving inhouse 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, 30minute presentation on its main ideas. Below is a list of suggested papers for such a presentation.
