Fall 2015: Limits of Computation, CS:4340:0001 (22C:131:001)
Coordinates
The course meets 12:30--1:45 pm Tuesday and Thursday
at 221 MLH (MacLean Hall).
Instructor
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu. Office Hours: 3:00--4:30 Monday, 3:30--5:00 Thursday.
Teaching Assistant
Ruoyu Zhang. Office hours: 10:00 am to 11:30 am on Tuesdays, in 101N MLH. Ruoyu's email: firstname-lastname@uiowa.edu.
What this Course is About
This course addresses questions such as
- Are there computational problems for which there are no algorithms? What
are some examples? How do we go about showing that a particular problem admits
no algorithms?
- What happens when we restrict resources such as time or space? How can
we prove that with more time, we will be able to solve problems that we
couldn't otherwise.
- What happens to these questions when randomized algorithms are allowed?
- Precisely how do we define the classes P, NP, and co-NP?
- How can the NP-Completeness of SAT (the first NP-complete problem)
actually be demonstrated? In the algorithms course, we only hint at this.
- What about space complexity and other models of computation?
To answer these and other questions, we'll learn about simple models of computations such as Turing machines and circuits.
A previous edition of the course can be found here.
Textbook
Our text is Computational Complexity, by Arora and Barak.
Prerequisites
Undergraduate Algorithms (At the UI this is CS:3330 (22C:031)).
Grading
The grading will be based on 5 to 6 homeworks (40 percent of the grade),
a midterm (25 percent), and a final (35 percent).
The policy on late homeworks is that you have a quota of three days
for the entire semester that you may use for late submissions. So
for example, there will be no penalty if you submit the third homework
a day late, the fifth two days late, and the rest of the homeworks
on time. Once you use up your quota of three days, any homework submitted
late will not be accepted and you will get 0 points for that homework.
When you submit a homework X days late, your quota gets decreased by X
irrevocably. You can only be late by an integer number of days, obtained by
rounding up -- if you
submit 10 hours after the deadline, for example, your quota is depleted
by one day.
Exam Dates
The midterm will be held October 29, from 6:30 to 8:30 pm, in 22 SH (Schaeffer Hall). The final will be held Monday, December 14, from 7:30 to 9:30 am,
as scheduled by the Registrar's office.
What We Covered Each Week
We will keep track of what we covered each week
here.
Handouts and Homeworks