. Schedule
.Table Date
.Item Meet'g
.Item $Study(2 pts)
.Item Bring(5 pts)
.Item $Topic(5 pts)
.Item Notes
.Row Mon Apr 3
.Item 1
.Item -
.Item -
.Item Survival
.Row Wed Apr 5
.Item 2
.Item Chapter 1+$math
.Item $Ex1
.Item Methods
.Row Mon Apr 10
.Item 3
.Item Preface+$Web1
.Item $URL
.Item History
.Item Exam on $math(50 pts)
.Row Wed Apr 12
.Item 4
.Item Chapter 2+Chapter 6 section 6.1
.Item $Ex
.Item Automata
.Row Mon Apr 17
.Item 5
.Item Chapter 8 sections 8.1, 8.2
.Item $Ex
.Item Turing Machines
.Row Wed Apr 19
.Item 6
.Item Chapter 8 sections 8.3, 8.4
.Item $Ex
.Item Programming $TM
.Row Fri Apr 21
.Item -
.Item -
.Item -
.Item Last day to drop
.Row Mon Apr 24
.Item 7
.Item Chapter 8 sections 8.5, 8.6
.Item $Ex
.Item Restricted $TM
.Row Wed Apr 26
.Item 8
.Item Chapter 8 section 8.7+$Minsky
.Item $Ex 
.Item The Halting Problem
.Item Start $Project
.Row Mon May 1
.Item 9
.Item $Web2
.Item $URL
.Item Recursive Functions
.Item $Acker(10 pts Bonus)
.Row Wed May 3
.Item 10
.Item  Chapter 9 sections 9.1, 9.2
.Item $Ex
.Item Undecidability & RE
.Item $Project1 (10 pts)
.Row Mon May 8
.Item 11
.Item $Project2  (20 pts)
.Item - 
.Item Turing Machines
.Row Wed May 10
.Item 12
.Item Chapter 9 section 9.3
.Item $Ex
.Item Undecidability & $TM
.Row Mon May 15
.Item 13
.Item Chapter 9 sections 9.4, 9.5.1, 9.6
.Item $Ex
.Item Post Correspondence+ Programs
.Row Wed May 17
.Item 14
.Item Chapter 10 sections 10.1
.Item $Ex
.Item Intractable Problems P & NP
.Row Mon May 22
.Item 15
.Item Chapter 10 sections 10.2, 10.3
.Item $Ex
.Item NP-Complete
.Row Wed May 24
.Item 16
.Item Chapter 10 sections 10.4, 10.5
.Item $Ex
.Item Graph Problems & TSP
.Row Mon May 29
.Item -
.Item -
.Item -
.Item HOLIDAY
.Row Wed May 31
.Item 17
.Item Chapter 11 sections 11.1, 11.2, 11.3
.Item $Ex
.Item Co-NP & PSPACE
.Row Mon Jun 5
.Item 18
.Item Chapter 11 sections 11.4
.Item $Ex
.Item Randomization RP ZPP
.Row Wed Jun 7
.Item 19
.Item Chapter 11 sections 11.5, 11.6
.Item $Ex
.Item Primality
.Row Mon Jun 12
.Item 20
.Item  Chapters 8, 9, 10, 11
.Item $Ex
.Item Review
.Row Fri Jun 16
.Item Final
.Item Chapters 1, 2, 8, 9, 10, 11
.Item -
.Item Comprehensive (200 pts)
.Row Tue Jun 20
.Item -
.Item -
.Item -
.Item Grades Due in
.Close.Table
(Web1): Search the WWW for pages on the theory of computability,
Alan Turing,
Turing Machines, tractability, Stephen Cook, Michael Rabin, etc. Submit one $URL.

(math): Chapter 1 + notes on the `big-O` notation
.See http://www.nist.gov/dads/HTML/bigOnotation.html
.See http://en.wikipedia.org/wiki/Big_O_notation
.See ./time1.cpp
(Down load and run some tests on UNIX system)
+  notes on directed graphs.
.See http://en.wikipedia.org/wiki/Graph_theory
.See http://www.math.fau.edu/locke/GRAPHTHE.HTM

(Acker): Study the Ackermann function on page 381 -- Exercise 9.2.2.
Write the simplest possible program that could possibly compute this
function for small x & y. Use recursion and long ints(at least).  Demo
results to class. Earn a bonus of 10 points. Note: your program
does not have to run fast (halt within 10 minutes) on large numbers (y>2).

(Web2): Search the web for pages on recursive functions, partial
recursive functions, primitive recursive functions,
recursively enumerable, recursive languages, and recursion
in general.  Submit one $URL.

(Minsky): Study my six page handout from Minsky's 1964 "Computation: Finite and Infinite Machines".

(Project): Working in a team of 3 or 4 people design, code, and test
a simple Turing Machine simulator.
.Set Notes
  You may use any language that can be demonstrated
in class.
  You may choose any kind of user interface you like.
  Your
$TM simulator does not have to have infinite memory capacity like a real $TM.
 Do the simplest thing that can possibly work.
 Consult with me in my office hours.
.Close.Set
 Process
.List
 Start by thinking about the design and developing tests for your code...
 (Project1): First deadline: bring a progress report to class and present it.
Grading: pass/fail.  Any running set of tests will pass.
 (Project2): Second deadline: bring a report on the final status, present it,
and hand in a hard copy for grading.
.Close.List
(URL): Submit one Universal Resorce Locator for a relevant page on a piece
of paper. Use the submit button at the top of the web page.  To earn 
complete credit you need to do this at least 90 minutes before the start of
class.
(Ex1): Handout listing some mathematical exercises: 
.See ./Ex1.pdf

(Ex):  Do as many  of the   relevant exercises as you have time for. You 
may work in a team of upto 4 students and hand in one joint solution. Bring
to class one written solution to an exercise. This must not be a solution 
to an exercise marked with an asterisk(*) to earn full credit. One of the 
authors will be invited to present the solution to the class -- failure 
will loose points. Students taking CS646 must hand in the solution to an 
exercise marked with an exclamation mark(!)  to earn full credit.
(Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page.  To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read.
(Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.