# Fall 2018: Theory of Computation, CS:4330

## Coordinates

The course meets 9:30--10:45 am Tuesday and Thursday
at 66 SH (Schaeffer Hall).

## Instructor

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

Linh Pham. Email: linh-t-pham@uiowa.edu

Office hours: Tuesday 3:00--4:30 pm, Wednesday 3:30--5:00 pm; 101N MLH.

## 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.

## Prerequisites

Undergraduate Algorithms (CS:3330)

## Grading

The grading will be based on 8--10 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 4 and November 8 in class. The final will be from 8:00--10:00 pm, on Wednesday December 12 (finals week), in room 105 MLH. Note that the room is different from our 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 in class Thursday, August 30.
- Homework 2, due in class Tuesday, September 11.
- Homework 3, due in class Thursday, September 20.
- Homework 4, due in class Tuesday, October 2.
- Homework 5, due in class Thursday, October 18.
- Homework 6, due in class Thursday, November 1.
- Homework 7, due in class Tuesday, November 27.
- Homework 8, due in class Thursday, December 6.

## 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. Please visit this page for CLAS teaching policies and resources.