CSC445  Models of Computation
Spring 2014
Instructor:
Dr. Lutz Hamel
Tyler, Rm 251
Office Hours: Tuesday 12:151:15pm, Wed 23pm
email: hamel@cs.uri.edu
TA:
Younghun Chae
Tyler, Rm 134
Office Hours: TBA
Email Address: iplusu@my.uri.edu
Description
Computation and algorithms seem to occur naturally in our daily lives. Consider counting change or following a recipe to make your favorite dish. The art of programming takes this to the limit by formally encoding computations and algorithms for a machine to follow. What are the limits of this algorithmic approach? Are there mathematical objects that cannot be computed by a machine via an algorithm? If we can express a computation via an algorithm how long would it take to compute? How much space would the computation consume?
In this course we will investigate many of these interesting questions. We start with simple models of computations such as the finite state machine and the push down automaton. As our main tool we will use an idealized general purpose computer invented by Alan Turing: the Turing Machine. This idealized machine allows us to study the limits of computability and the complexity of computations without having to worry too much about actual hardware.
The goals of the course are:
 To be exposed to the terminology of the theory of computing.
 Familiarity with some of the major results in computability and complexity theory.
 A basic understanding of the major models of computations.
Announcements:
** Final Exam: Tuesday May 6, 811am in Crawford 223. Comprehensive, open book/open notes **
[4/17/14] posted assignment #8 so you can get started  we will cover chap 18 next week.
[4/3/14] Posted assignment #7
[3/26/14] Posted assignment #6
[3/24/14] Posted assignment #5
[3/12/14] posted all solutions on the web
[2/26/14] No class Tuesday 3/4
[2/26/14] posted assignment 4.
[2/18/14] posted assignment 3.
[2/6/14] Posted assignment 2.
[1/28/14] Posted assignment 1.
[1/17/14] Welcome!
Documents of Interest:
Assignments:
In order to receive full credit
for your assignments they have to be typewritten.
Hand drawn diagrams are acceptable. Email submissions are not
acceptable.

Assignment #1: Due in class Tuesday Feb 4th. Do the following: Chapter 1: exercise 1 parts a,c,d;
Chapter 2: exercise 2 parts a through e; exercise 3 parts a,c; exercise 4 parts a,c; exercise 5 part a; exercise 6 part c.

Assignment #2: Due in class Tues Feb 12th. Do the following: Chapter 3: exercise 1 parts c,d; exercise 4 parts a,b
(Note: in part b the first language is the complement of L1, the typo omits the subscript);

Assignment #3: Due in class Tues. Feb 25th. Do the following: Chapter 5: exercise 1 parts c,d; exercise 2 parts b,e;
exercise 4 part a; exercise 5 part g; exercise 7 part b; exercise 10 parts b,c; exercise 16;
Chapter 6 exercise 4.

Assignment #4: Due in class Thurs. March 6th. Do the following: Chapter 7: exercise 1 parts b,l,t;
exercise 2 part e.

Assignment #5: Due in class Thurs. March 27th. Do the following: Chapter 10: exercise 1 all parts; exercise 2;
exercise 4 parts a,b; exercise 5 parts c,d.

Assignment #6: Due in class Thursday April 3rd Do the following: Chapter 11: exercise 3;
exercise 8; exercise 10.

Assignment #7: Due in class Tues. April 15th Do the following:
Chapter 12: exercise 1 parts a and g, exercise 4 part a;
Chapter 13: exercise 1, exercise 5;
Chapter 14: exercise 1, exercise 6, exercise 15, exercise 16.

Assignment #8: Due in class Tues. April 39th Do the following:
Chapter 16: exercise 1, exercise 14 (read the instructions for all of the exercises for this chapter
carefully);
Chapter 17: exercise 5;
Chapter 18: exercise 2 parts a,b; exercise 3 parts a,d; exercise 9 parts a,e,g.