Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> schedule [Text Version]
[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search ]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Mon Jun 5 17:08:00 PDT 2006
Opening the PDF files on this page may require you to download Adobe Reader or an equivalent viewer (GhostScript).

Contents

    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 NP-Complete
    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 Co-NP & 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 big-O 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.

  1. Process
    1. Start by thinking about the design and developing tests for your code...
    2. (Project1): First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass.
    3. (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.

    Standard Definitions

  2. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  3. ND::="Non-deterministic", 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 high-level designs for more complicated deterministic machines. Plus it's fun.
  4. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  5. RJB::=The author of this document, [ ../index.html ]
  6. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  7. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
  8. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
  9. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
  10. TBA::="To Be Announced".
  11. TM::="Turing Machine".
  12. NTM::="Nondeterministic Turing Machine".
  13. DTM::="Deterministic Turing Machine".
  14. P::@problem=class of problems that a DTM can compute in polynomial_time.
  15. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  16. 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.

    From Logic

  17. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html


  18. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
  19. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
  20. (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.
  21. (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.
  22. (LOGIC)|- (def): By definition of a term defined above.
  23. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
  24. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.

End