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@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

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.


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.

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