The course meets 9:30--10:45 am Tuesday and Thursday at 66 SH (Schaeffer Hall).
Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:email@example.com
Office hours: Monday 3:00--4:30 pm, Wednesday 1:30--3:00 pm; 101D MLH.
Linh Pham. Email: firstname.lastname@example.org
Office hours: Tuesday 3:00--4:30 pm, Wednesday 3:30--5:00 pm; 101N MLH.
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--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.
We will keep track of what we covered each week here.