Schedule
Date
 Meet'g
 Study(2 pts)
 Bring(5 pts)
 Topic(5 pts)
 Notes


Mon Apr 3
 1
 
 
 Survival

Wed Apr 5
 2
 Chapter 1+math
 Ex1
 Methods

Mon Apr 10
 3
 Preface+Web1
 URL
 History
 Exam on math(50 pts)

Wed Apr 12
 4
 Chapter 2+Chapter 6 section 6.1
 Ex
 Automata

Mon Apr 17
 5
 Chapter 8 sections 8.1, 8.2
 Ex
 Turing Machines

Wed Apr 19
 6
 Chapter 8 sections 8.3, 8.4
 Ex
 Programming TM

Fri Apr 21
 
 
 
 Last day to drop

Mon Apr 24
 7
 Chapter 8 sections 8.5, 8.6
 Ex
 Restricted TM

Wed Apr 26
 8
 Chapter 8 section 8.7+Minsky
 Ex
 The Halting Problem
 Start Project

Mon May 1
 9
 Web2
 URL
 Recursive Functions
 Acker(10 pts Bonus)

Wed May 3
 10
 Chapter 9 sections 9.1, 9.2
 Ex
 Undecidability & RE
 Project1 (10 pts)

Mon May 8
 11
 Project2 (20 pts)
 
 Turing Machines

Wed May 10
 12
 Chapter 9 section 9.3
 Ex
 Undecidability & TM

Mon May 15
 13
 Chapter 9 sections 9.4, 9.5.1, 9.6
 Ex
 Post Correspondence+ Programs

Wed May 17
 14
 Chapter 10 sections 10.1
 Ex
 Intractable Problems P & NP

Mon May 22
 15
 Chapter 10 sections 10.2, 10.3
 Ex
 NPComplete

Wed May 24
 16
 Chapter 10 sections 10.4, 10.5
 Ex
 Graph Problems & TSP

Mon May 29
 
 
 
 HOLIDAY

Wed May 31
 17
 Chapter 11 sections 11.1, 11.2, 11.3
 Ex
 CoNP & PSPACE

Mon Jun 5
 18
 Chapter 11 sections 11.4
 Ex
 Randomization RP ZPP

Wed Jun 7
 19
 Chapter 11 sections 11.5, 11.6
 Ex
 Primality

Mon Jun 12
 20
 Chapters 8, 9, 10, 11
 Ex
 Review

Fri Jun 16
 Final
 Chapters 1, 2, 8, 9, 10, 11
 
 Comprehensive (200 pts)

Tue Jun 20
 
 
 
 Grades Due in

(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 bigO notation
[ bigOnotation.html ]
[ Big_O_notation ]
[ time1.cpp ]
(Down load and run some tests on UNIX system)
+ notes on directed graphs.
[ Graph_theory ]
[ 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.
 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.
 Process
 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.
(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:
[ 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.
 FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite
set of states.
 ND::="Nondeterministic", a machine that can try out many possibilities
and always guesses the right choice. Note: For a given problem
a ND solution is simpler and easier to understand than a deterministic
one. We study ND machines to discover how to use them as highlevel
designs for more complicated deterministic machines. Plus it's fun.
 PDA::="Push down Automata", a machine with a finite control and a
single stack for remembering intermediate data. Kind of like half a TM.
 RJB::=The author of this document,
[ ../index.html ]
 RJB="Richard J Botting, Comp Sci Dept, CSUSB".
 Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
 Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
 Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html,
and also see
[ syllabus.html ]
(my generic syllabus).
 TBA::="To Be Announced".
 TM::="Turing Machine".
 NTM::="Nondeterministic Turing Machine".
 DTM::="Deterministic Turing Machine".
 P::@problem=class of problems that a DTM can compute in polynomial_time.
 NP::@problem=class of problems that a NTM can compute in polynomial_time.
 polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.
 LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html
 (LOGIC) (ei): Existential instantiation  if P is true of something then we can
substitute a new variable for it.
 (LOGIC) (eg): existential generalization  if P is true of this thing then
it is true of something!
 (LOGIC) (given): a proposition that is assumed as part of a Let...End Let argument.
Typically if A and B and C then D starts with assuming A,B, and C are
given. They are called the hypotheses.
 (LOGIC) (goal): a proposition that we wish to prove. Typically the part after
the then in an if...then... result. This is called the conclusion.
 (LOGIC) (def): By definition of a term defined above.
 (LOGIC) (algebra): Either by using well known algebraic results, or by
use a series of algebraic steps.
 (LOGIC) (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that
establishes the negation of the last set of assumptions/hypotheses.