Fall 2019: Theory of Computation, CS:4330


The course meets 9:30--10:45 am Tuesday and Thursday at 110 MLH (MacLean Hall Hall).


Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu

Office hours: Monday 3:00--4:30 pm, Wednesday 1:30--3:00 pm; 101D MLH.

Teaching Assistant

Osama Khalid, email: firstname-lastname@uiowa.edu

Office hours: Tuesday 2:30--4:00 pm, Friday 12:00--1:30 pm, in 201N MLH (Maclean)

What this Course is About

In this course, we will explore the fundamental capabilities and limitations of computers. More precisely, the goal is to understand functions that can and cannot be computed. We will pursue this first in restricted computational models, such as finite automata, and then examine more general models, culminating in the Turing Machine.

Our textbook is Introduction to the Theory of Computation (Third Edition) by Michael Sipser. We will cover material from the first five to six chapters of this text.


Undergraduate Algorithms (CS:3330)


The grading will be based on 8--9 homework assignments (25 percent), two midterms (20 percent each), and a final (35 percent). The emphasis will be on developing and understanding algorithmic constructions and showing the impossibility of algorithms for certain problems. Thus, all the homeworks will involve problem solving with pen and paper.

The policy on late homework 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 homework assignments 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 -- if you submit 10 hours after the deadline, for example, your quota is depleted by one day.

Exam Dates

The midterms will be on October 10 and November 14 in class. The finals will be on Tuesday, December 17, from 3:00-5:00 pm in 110 MLH.


No collaboration is allowed on the exams. For homework problems, collaboration is alright, assuming each of you has first spent some time (about 30 minutes) working on each problem yourself. However, no written transcript (electronic or otherwise) of the collaborative discussion should be taken from the discussion by any participant. It will be assumed that each of you is capable of orally explaining the solution that you turn in, so do not turn in something you don't understand.

What We Covered Each Week

We will keep track of what we covered each week here.

Handouts and Homeworks

Departmental Information

Department of Computer Science, 14 MacLean Hall. The office of the DEO, Prof. Alberto Segre, is located here.

Administrative Home

The College of Liberal Arts and Sciences (CLAS) is the administrative home of this course, and we will follow CLAS teaching policies. Please visit this page for CLAS teaching policies and resources.