CSC445 - Models of Computation
Spring 2016
Instructor:
Dr. Lutz Hamel
Tyler, Rm 251
Office Hours: Tuesday 12:30-1:30pm and Thursday 2-3pm
email: hamel@cs.uri.edu
TA:
Adam Jilling
Tyler, Rm 136
Office Hours: Mon 1-2:00 Tues 1-2:30
Email Address: ajilling@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:
[5/16/16] posted the solutions to the final
[5/2/16] posted solutions #8
[4/25/16] Posted assignment #8
[4/18/16] posted solutions to #7
[4/7/16] posted assignment #7
[3/31/16] posted solutions to #6
[3/16/16] posted assignment #6
[3/16/16] posted solutions to #5
[3/9/16] posted solutions to #4
[3/9/16] posted assignment #5
[3/2/16] posted assignment #4
[3/2/16] posted solutions to #3
[2/22/16] posted assignment #3
[2/17/16] posted solutions to #2
[2/8/16] posted assignment #2
[2/5/16] new due date for assignment #1 -- see below
[2/1/16] posted assignment #1 (see below)
[1/26/16] 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 Sakai Monday Feb 8th. 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 Sakai Monday 15th. 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 Sakai Friday Feb 26th. 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 Sakai Monday March 7th. Do the following: Chapter 7: exercise 1 parts b,l,t;
exercise 2 part e.
-
Assignment #5: Due in Sakai Friday March 11th. 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 Sakai Wednesday March 30th Do the following: Chapter 11: exercise 3;
exercise 8; exercise 10.
-
Assignment #7: Due in Sakai Thursday April 14th 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 Sakai Sun. May 1st 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.