Spring 2015: Limits of Computation, CS:4340:0001 (22C:131:001)
Coordinates
The course meets 12:30--1:45 pm Tuesday and Thursday
at 110 MLH (MacLean Hall).
Instructor
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu. Office Hours: 3:00--4:30 Monday, 2:00--3:30 Wednesday.
Teaching Assistant
Ruoyu Zhang. Office hours will be held on Fridays, 8:00--9:30 am, in Room 101N,
MacLean 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 other interesting complexity classes are there besides P, NP,
and co-NP?
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 Tuesday, October 31, from 6:30 to 8:30 pm, in our usual classroom. The final will be during
finals week, on Friday, May 15, 3:00--5:00 pm, in 110 MLH, our usual classroom.
What We Covered Each Week
We will keep track of what we covered each week
here.
Handouts and Homeworks
- First Day Handout
- Homework 1, due Feb 5th in class.
- Homework 2, due Feb 19th in class.
- Homework 3, due Tuesday, March 10th in class.
- Homework 4, due Tuesday, April 7th, in class.
- Homework 5 (updated 4/13), due Tuesday, April 21, in class.
- Homework 6, the last homework, due Thursday, May 7, in class.