Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 01 [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]
Thu Jun 8 13:02:46 PDT 2006


    Class 01 -- Surviving the Theory of Computation


        CSCI546 Introduction to Theory of Computation

        Deterministic and non-deterministic Turing machines, decidable and undecidable problems, complexity classes P and NP. PreReq: 431 Elective in the CSci BS.

        Note: this class will make more sense if you have completed CSCI500 first.

        CSCI 646 Theory of Computation

        Theoretical foundations of computer science: models of Computation, recursive functions; Church's thesis and undecidable problems; complexity classes: P, NP, CO-NP and PSPACE. Prereq: classified. Elective in the CSci MS.

        Note: this class will make most sense if you have completed CSCI600 or 500 first.

        If you are enrolled in CS646 then to earn full credit for the work you have to select the tougher exercises marked by an exclamation mark in the book(!).

        Why take this class

        1. Do you want to be a millionaire? [ ] [ ] [ ]
        2. Do you want to tackle some of the most intriguing and powerful results in the whole CSci curriculum?
        3. Why is some encryption so hard to crack? Does it have to be that way?
        4. Why am I still waiting for the answer? Has the computer crashed?
        5. Which programs can not be solved by programming?
        6. What kind of problem is hard to solve quickly?

        Instructor Information

        I haven't taught this class for nearly a decade. I've never taught it with this text book or as a co-scheduled class (CS546 + CS646). [ ../index.html ]

        Calendar, Schedule, Required Work

        The schedule may have to change.... since I've not used this book before etc... [ schedule.html ]

        Support, Instructional Methods, Policies, & Grading

        [ ../syllabus.html ]


          Required Text

          2. John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman [ ialc.html ]
          3. Addison Wesley 2001 ISBN 0-201-44124-1

          (We'll cover chapters 1,2,8,9,10, and 11 of it in this course, the rest was in the previous quarter's theory course).

          A relevant book

          The following was used in previous editions of this class. You may find it helpful but you don't need to buy it if you haven't got a copy:
          1. Author: John Martin
          2. Title: Intro to Languages and Theory of Computation
          3. Edition: 3rd ISBN#: 0-07-232200-4 [ ]

          A Classic Text

          1. Marvin Minsky
          2. Computation: Finite and Infinite Machines
          3. Prentice Hall 1964
          5. Written before complexity and intractability was published.

          I will be handing out a couple of pages as reading for one class.

          This has just been rated the 13th most popular computer science book that is out of print by the Association for Computing Machinery.

          Do not buy -- unless you see a second hand copy going cheap.


          There are very few books on computability and tractability in the CSUSB library. Possible library of congress classifications are QA9 (Foundations of mathematics) and QA76.6 G35. I have found (and borrowed) a useful reference work: Michael R Garey & David S Johnson, Computers and Intractability: A Guide to the theory of NP-Completeness, Bell Telephone Labs 1979.

          Research on the World Wide Web

          The preparation for two classes requires you to search the web for topics and submit a relevant URL that you have discovered as assigned work/study.

        . . . . . . . . . ( end of section Readings) <<Contents | End>>

        Work to be done

          Project Work and Programming(6%)

          You will work in a team to produce a simple simulator of a Turing Machine. More details in the schedule. The whole project earns 30 points: 10 points for a progress report(2%) and 20 points (4%) for the finished product and presentation.


          I will ask you to program and test a single, well known function. This is a bonus of 10 points(2%).

          Assigned work(26%)

          (Study): The schedule assigns a piece of reading to be studied to prepare for class. You must "[Submit]" a questions based on the reading using the "[Submit]" button on the web pages at least one hour before the start of each class. This is worth 2 points if on time. You get a 2point bonus for attending the first class.

          Notice that if you don't ask about something we probably will not spend time class time on it. So ask about things you need help with.

          (Ex): You should also attempt all the exercises that you have time for and bring a written answer to one of them that is not marked by an asterisk(*). An exercise is one part of a numbered exercise.

          You may work in a team of up to 4 people and hand in one answer with all the names on the front sheet. This is worth 5 points(1%). All members of the team will get the same score. I will pick one person from the team to present -- and they may lose all their points if they apparently don't know what their team did.

          When the reading in the schedule is on the web you should "[Submit]" a URL for a page at least one hour before class. This is worth 5 points max(1%).

          Quizzes and Exams (50%)

          The will be a short test of the material in the first chapter of the book (math) in the third class -- it contributes 50 points(10%) to the total grade for the class. The final exam is comprehensive and contributes 200 points (40%) to the total grade.

          Participation (20%)

          To earn all 5 points you must: (1) turn up and be ready to take part at the start of the class, (2) stay until the class is dismissed, (3) Answer questions, (4) ask questions, and (5) take part in class discussions and exercises.

        . . . . . . . . . ( end of section Work to be done) <<Contents | End>>


        All points earned before the final will be totaled with the maximum possible score being set to 300 points. The maximum on the final is 200 points. These two totals will be added together to calculate the grade for the course according to the rules [ ../syllabus.html ] in my generic syllabus.

      . . . . . . . . . ( end of section Syllabus) <<Contents | End>>

      Beta 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+O(.)+graph Ex 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.2, 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 two page handout from Minsky's 1964 "??"

      (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.
    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.
      (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.

    . . . . . . . . . ( end of section Class 01 -- Surviving the Theory of Computation) <<Contents | End>>

    Standard Definitions

  1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  2. 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.
  3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  4. RJB::=The author of this document, [ ../index.html ]
  5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  6. Schedule::= See
  7. Search::= See
  8. Syllabus::= See, and also see [ syllabus.html ] (my generic syllabus).
  9. TBA::="To Be Announced".
  10. TM::="Turing Machine".
  11. NTM::="Nondeterministic Turing Machine".
  12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
  13. DTM::="Deterministic Turing Machine".
  14. runtime::=run_time,
  15. run_time::="The number of steps a TM takes before it halts when start on a given input".
  16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  17. P::@problem=class of problems that a DTM can compute in polynomial_time.
  18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  19. 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

  20. LOGIC::= See

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