CSC544 - Theory of Computation
Spring 2007
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.
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 goal of the course is that you are exposed to the terminology of the
theory of computing and are familiar with some of the major results in
computability and complexity theory. This course will allow you to
understand current research in algorithmics, especially in the area of
bioinformatics where computability and complexity are major concerns.
The hope is that studying algorithms, computation, and complexity at
this abstract level will provide you with some insights into your
programming tasks and will provide perhaps a different vantage point of
computing itself.
Final Exam: Thursday May 3rd, 3-6pm, Washburn Rm 220.
Talk Schedule
4/17
Akhila -- D. Goldin and P. Wegner,The Church-Turing Thesis: Breaking the Myth
Lewis -- D. Deutsch, A. Ekert and R. Luppachini, Machines, Logic and Quantum Physics
4/24
Rajesh -- R. Milner, Elements of Interaction
Sidra & Steve -- C. Timpson, Quantum Computers: The Church-Turing Hypothesis versus the Turing Principle
4/26
Lara -- M. Stannett, Hypercomputational Models
James -- M. Davis, The Myth of Hypercomputation
Announcements:
[4/25/07] Posted all the outstanding problem solutions.
[4/25/07] An interesting paper of recursion theory and effectively
computable functions, I particularly like the graph at the bottom of the page (summary).
[4/12/07] Don't forget the typewritten questions for Tuesday for the first set of presentations.
[4/12/07] Posted assignment #9
[4/10/07] Hints for assignment #8:
- problem 1. should follow straight from the definition of NP-completeness
- problem 2. (a) show that a polynomial deterministic time algorithm exists that decides this langauge...think
about eliminating variables that do not contribute to the overall solution. (b) Construct a
reduction from 3SAT to CNF3. Look at the reduction done in class.
- problem 3. reduction from 3COLOR (problem 7.27 new edition) to the scheduling language.
[4/4/07] Posted assignment #8.
[4/4/07] Posted the papers for extra credit, see 'papers' below. Email me for the password.
[3/29/07] Posted assignment #7.
[3/25/07] Posted midterm solutions.
[3/10/07] Posted solutions to Assignment #6.
[3/5/07] Posted solutions to Assignment #5.
[3/1/07] Posted solutions to Assignment #4.
[3/1/07] Posted assignment #6
[2/23/07] Posted assignment #5
[2/23/07] Posted solutions to Assignment #3.
[2/23/07] Posted solutions to Assignment #2.
[2/15/07] Posted assignment #4
[2/13/07] Posted assignment #3
[2/8/07] class cancelled today
[2/5/07] Posted solutions to Assignment #1.
[2/1/07] IMPORTANT: Posted updated Assignment #2 (added an additional problem)
[1/22/07] Homework Assignment #1
[1/18/07] 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: Reading: Chap 0, Problems: 0.12 due Tuesday 1/29 at the beginning of class.
- Assignment#2: Reading: Chaps 1,2; problemsheet, due Tuesday 2/6 in class.
- Assignment#3: Reading: Chap 3; problemsheet, due Thursday 2/15 in class.
- Assignment#4: Reading: Chap 4; problemsheet, due Thursday 2/22 in class.
- Assignment#5: Reading: Chap 4; problemsheet, due Tuesday 2/27 in class.
- Assignment#6: Reading: Chap 4 & handout; problemsheet, due Tuesday 3/6 in class.
- Assignment#7: Reading: Chap 7; problemsheet, due Tuesday 4/3 in class.
- Assignment#8: Reading: Chap 7,8; problemsheet, due Tuesday 4/10 in class.
- Assignment#9: Reading: Chap 8; problemsheet, due Tuesday 4/24 in class.
Instructor:
Dr. Lutz Hamel
Tyler, Rm 251
Office Hours:TBA
email: lutz at inductive dash reasoning dot com