CSC445 - Models of Computation

Spring 2012

Instructor:

Dr. Lutz Hamel
Tyler, Rm 251
Office Hours: Monday 2-3pm, Thursday 11-noon
email: hamel@cs.uri.edu

TA:

Cora Ly Maffioli
Tyler, Rm 136
Office Hours: WF 11:30PM-12:30PM
Office Phone Number: 401-874-4223
Email Address: coraly_maffioli@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.

Final Exam: Thursday 5/10 @ 3-6pm, Tyler Rm 049 -- comprehensive, open book open notes

Announcements:

[5/11/12] Posted the solutions to the final.
[5/4/12] Posted solutions to assignments #7 and #8
[4/25/12] Posted assignment #8
[4/15/12] Posted assignment #7
[4/9/12] posted solutions for assignment #5 and #6
[3/28/12] posted assignment #6
[3/21/12 posted assignment #5
[3/18/12] Posted midterm solutions in the solutions area.
[3/5/12] NOTE: the midterm will be held in Tyler rm 49 @ 3pm on 3/7.
[3/5/12] ** Midterm, Wednesday, March 7th ** covers chapters 1 through 9. Open Book/Open Notes
[2/29/12] posted assignment #4
[2/15/12] added another problem to assignment #3
[2/15/12] solutions page now active, go to the sakai course website (discussion board) for the username and password
[2/15/12] Posted assignment #3
[2/15/12] the Online Grade Book is ready, email me for your access code [2/8/12] Posted assignment #2
[1/30/12] Posted assignment #1
[1/23/12] Sakai page now up and running ...you can now use the forum to communicate with other students in the class.
[1/18/12] 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 Mon. Feb 6th. 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 Wed. Feb 15th. Do the following: Chapter 3: exercise 1 parts c,d; exercise 4 parts a,b (Note: in part b the first language is [not L1]); exercise 7; Chapter 4: exercise 3 (hand in your source code and a printout of an example run; source code for the Mod3 example from the chapter is available here).
Assignment #3: Due in class Mon. Feb 27th. 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 Mon. March 5th. Do the following: Chapter 7: exercise 1 parts b,l,t; exercise 2 part e; exercise 8 part f.
Assignment #5: Due in class Mon. March 26th. 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 Mon. April 2nd Do the following: Chapter 11: exercise 3; exercise 7; exercise 10.
Assignment #7: Due in class Mon. April 23rd 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 Mon. April 30th 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.