Spring 2015: Limits of Computation, CS:4340:0001 (22C:131:001)
The course meets 12:30--1:45 pm Tuesday and Thursday
at 110 MLH (MacLean Hall).
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname.lastname@example.org. Office Hours: 3:00--4:30 Monday, 2:00--3:30 Wednesday.
Ruoyu Zhang. Office hours will be held on Fridays, 8:00--9:30 am, in Room 101N,
MacLean Ruoyu's email: email@example.com.
What this Course is About
This course addresses questions such as
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.
- 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
- 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
- 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,
Our text is Computational Complexity, by Arora and Barak.
Undergraduate Algorithms (At the UI this is CS:3330 (22C:031)).
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.
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
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.