Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> index [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]
Sat Jun 17 13:05:39 PDT 2006
Opening the PDF files on this page may require you to download Adobe Reader or an equivalent viewer (GhostScript).
Opening the PPT files on this page may require you to download a viewer for MS Power Point files.


    CSci546/646 Theory of Computation Spring 2006

      2006-06-17 Sat Jun 17 13:06 Grades for final and course published

      Grade DistributionA/A-B-/B/B+C-/C/C+D-/D/D+F
      Please check for errors and tell me as soon as possible.

      2006-06-13 Tue Jun 13 15:06 PRefinal Grades posted

      Please check to see if there any any significant errors in the posted grades (I know I have Final Question 7 twice...). I hope to have the complete scores including the final MOnday afternoon...

      2006-06-12 Mon Jun 12 06:06 Submitting Work -- EMail Failing

      The Web server is out of file space again..... please bring your questions to class on paper or EMail them to
    1. rbotting at CSUSB.... with
    2. cs546 or
    3. cs646 as the first 5 characters of the Subject.

      2006-06-07 Wed Jun 7 16:06 My answers to exercises...

      Download [ Makefile ] [ Mod.cpp ] [ mod.cpp ] to get a program that compiles and runs and prints out answers to most of the homework... By the way [ binary.c ] is an old old program fro converting decimal notation into binary using C.

      The grades have been posted...

      The course review [ 20.html ] is next.

      2006-06-06 Tue Jun 6 09:06 Bonusses and Exercises for 19

      I will except Exercise 11.5.2 for full credit for CSCI646.

      I will offer a 20 point bonus for a running demonstration of a C++ template class

       	template<int p>Mod { ... };
      that defines a set of arithmetic(divison is not needed) and utility operations for numbers modulo p.

      Check out [ 19.mth ] the next classes web page.

      I've also updated [ final.pdf ] a little.

      2006-06-05 Mon Jun 5 16:06 Latest Info on Talks on Friday

      There are talks at 10:-11:30, 11:30-12:30 and 1-2pm: [ ../seminar/20060609UCSBTalks.txt ] (I'll offer 646 and 546 credit for the first one).

    4. 17:06 Grades have been posted!

      2006-06-02 Fri Jun 2 15:06 Joke proofs added

      [ 02.html ]

      2006-06-02 Fri Jun 2 14:06 Relevant Talk coming up next Friday

      Sara Woodworth ( will be talking about "Membrane Systems: A Natural Approach to Computing" [ ../seminar/20060609UCSBTalks.txt ] so I will give 10 points credit as a bonus for attending. By the way "Membrane Computing" can do some NP problems in P time!

      2006-06-01 Thu Jun 1 11:06 Started designing the final...

      Here [ final.pdf ] is my first rough outline of the final exam for this class.

      Remember that in every topic I will be interested in precise mathematical definitions, theorems, and examples. You will need to be able to quote the definitions, apply them, and discuss their meaning in plain english. There will be some proofs based on work done in class or as exercises. I may ask for an informal description of some of the harder proofs -- rather than expecting you to memorize the "gimicks" and "gadgets".

      Note: you can and should prepare a 8><11 sheet of paper to use in the exam as a "Cheat Sheet". You can write on both sides and use an size font you like.

      Also: the latest grades are posted and I've added some notes to [ 18.html ] the next class on randomized algorithms and machines.

    5. 2006-05-26 Fri May 26 16:05 Grades Posted, have a good break, ... I've posted the latest grades. The next class [ 17.html ] is on Wednsday and introduces two new "Complexity Classes". Meanwhile, Have a good break...
    6. 2006-05-23 Tue May 23 10:05 Deadline tomorrow I won't be able to access my EMail tomorrow at 12:30 as usual. I will give credit for submissions until 1:40pm. BUT I won't be able to include your questions that arrive after 11am in the web page until after class. The quality of the answer will probably suffer if the question arrives at 1:40pm. There may also be a loss of anonimity for late questions. So I would ask you to get the questions in early please!

    7. 2006-05-22 Mon May 22 16:05 Grading done.... check exercises for next session Please use [ 16.html ] as a study guide for the last part of Chapter 10.

      The URL [ 2SAT.ppt ] is a paower point presentation that includes a solution (almost complete) of Exercise 10.3.4 that I showed you today in class.

      Here is my solution to exercise 10.3.1 b -- the 3CNF extension to

    8. w x y z + u + v or
    9. w x y z + (u + v).

      First convert the second term to CNF

    10. w x y z + ((u+p)(v+p_bar)) (I introduced p to express (u+v) as a product)

      Now we have the sum of two CNFs so I introduce a switch a:

    11. (w+a)(x+a)(y+a)(z+a) (x+p+a_bar)(x+p_bar+a_bar)

      Which is in CNF.... now we go to 3-CNF by replacing the 2-literal clauses by a product of two 3 literal clauses.... again adding more varaibles

    12. (w+a+b)(w+a+b_bar) (x+a+c)(c+a+c_bar) (y+a+d)(y+a+d_bar) (z+a+e)(z+a+e_bar) (x+p+a_bar)(x+p_bar+a_bar)

    13. 2006-05-18 Thu May 18 13:05 Notes improving and grades done I've made some improvements to [ 14.html ] the notes from last class, and I'm working on the next 2 or 3 classes: [ 15.html ] (SAT and friends), [ 16.html ] (Graph and other problems), and [ 17.html ] (chapter 11).
    14. 2006-05-16 Tue May 16 13:05 Grades posted.... Intractable Problems Ahead See [ 14.html ] for more information.
    15. 2006-05-11 Thu May 11 16:05 Grades posted... next PCP in class 13 Check out your grades and also [ 13.html ] the notes for the next class.

      I also found [ pcp.php ] an live PCP example on the web! Also [ pcp1.png ] [ pcp2.png ] [ pcp3.png ]

    16. 2006-05-09 Tue May 9 12:05 Projects and notes I've been improving the notes for the coming sessions. Next is [ 12.html ] on undecidability. In particular I'm starting to insert proof structures -- they show the structure and steps in proofs of theorems. I hope they work.

      I've graded the projects and they will be posted "Real Soon Now".

      Grades have been posted! (4:40pm)

    17. 2006-05-04 Thu May 4 15:05 Class 10 graded + Bonus... I've posted the grades from the latest work. Next: you can earn a 20 point bonus by attending my seminar on an ambiguity in the UML2.0 on Friday at 10am in the Maths Seminar room on the 3rd floor of JBH.

      On Monday, in [ 11.html ] , each team will present its simulator of small non-deterministic Turing Machines to class.

    18. 2006-05-01 Mon May 1 16:05 Class 9 graded... The grades have been posted.... thanks for a fun session. Now on to [ 10.html ] on undecidability.
    19. 2006-04-28 Fri Apr 28 14:04 Submit Button now works again Brian told me last night that he couldn't submit his URL. I checked and told Ken this morning.... It appears to be working again.
    20. 2006-04-27 Thu Apr 27 14:04 Anecdotes on AI and the Halting Problem While working with a graduate student on their laptop the student said something that reflects a key thought I've had about AI
      1. I'll have to tell MicroSoft Word to do it my way. I wish it didn't try to do the thinking for me. I want it to do what I want, while I do the thinking.

      Earlier in the day, I was running a new browser and it suddenly reported

      1. Javascript seems to be in a loop that never halts.

      It invited me to let it [Continue] or to [Stop]. And I regretted that their can never be a program that diagnoses whether other programs will run for ever or not:-(

      I've just posted the latest grades.

      Remind me to return the last set of graded home work when we are reviewing the theory of recursive functions and sets in class [ 09.html ] on Monday.

    21. 2006-04-25 Tue Apr 25 15:04 Grades posted and URLs are arriving See [ 08.html ] for the assigned work and preparation for the next class.
    22. 2006-04-23 Sun Apr 23 12:04 Homework for CS646 Students I've been asked
        For Exercises 8.5 there is not a question to answer that has a ! only. In class you told us not to do !! questions. What should CS646 students answer. Thanks

      I will give full credit for either part (a) or (b) of Exercise 8.5.1, even for CS656.

      The asterisk on 8.5.1 part (a) that advertized a published solution is misleading -- I can't find it. As a result I will give credit for (a).

      Part (b) has typo. It should show

    23. {0^n 1^m | m>=n>=1 }

      as the target language for your countr machine.

      The *!! 8.5.1 (c) part has a useful thought for all the exercises.

      More questions on the page [ 07.html ] for the next class.

    24. 2006-04-20 Thu Apr 20 12:04 Grades posted I've posted the grades to date [ grading ] on the web site. Please check. I plan to add some notes to the last class [ 06.html ] this afternoon and may add more to the future class notes [ 07.html ] etc. by tomorrow.

      For example, I think that using a tree to explore the possible IDs that a NTM can get to is useful for human beings: [Tree of IDs]

    25. 2006-04-19 Wed Apr 19 12:04 Modification to Project Specification I've got a determinstic TM emulator. There are several on the web. What I'd like is to handle nondeterministic TMs. So to earn full credit for the project the final version should handle non-deterministic TMs by using a queue and breadth-first search.

    26. 2006-04-18 Tue Apr 18 13:04 Ready for class 6 I've posted the latest scores and grades.... please check.

      The questions are already arriving ready for [ 06.html ] on the techniques of the Turing Masters: store small data in the state, store moire data on the tape, reuse your designs, use several taps, and let the machine make guesses...

    27. 2006-04-17 Mon Apr 17 09:04 Most question for sesion 5 are in -- thanx [ 05.html ]
    28. 2006-04-13 Thu Apr 13 12:04 Hints for exercises in chapter 8 I've got the last set of work graded and will post the scores later this afternoon.

      I've added a couple of hints on the exercises [ 05.html#8.1.4 Exercises ] [ 05.html#8.2.7 Exercises ] due at the start of next class.

    29. 14:04 Grades posted: 2 A's, 5 B's, 5 C's, 2 D's and an F. Please check: I think I may have misplaced a couple of pieces of work.

    30. 2006-04-12 Wed Apr 12 12:04 Class 4 -- Review Automata I've graded the exam and work done so far. Scores have been posted at [ grading ] if you have got yor PINword.

      And the questions are arriving... and being posted [ 04.html ] for todays class.

    31. 2006-04-11 Tue Apr 11 17:04 Request for lecture on Automata I'm starting work on [ 04.html ] the next class meeting. I'll put together a lecture on DFA starting with a simple C++ program [ auto1.cpp ] that implements a simulation of the DFA in section 2.2.

      Submit your questions early so I can give you a considered answer!

      I plan to finish grading the exam tomorrow morning.

    32. 2006-04-06 Thu Apr 6 14:04 Wrapping up class 2 and prep for class 3 Having checked with some texts and a colleague, it seems that you do have to use the differential calculus to do exercise 2 that shows that for all constant a, a*x^2 is ultimately less than 2^x.

      I've started the web page for the next class [ 03.html ] and I've already got a couple of URL's submitted!

      And I've just posted the first scores at [ grading ] for people who recall their PINword. I don't have all the calculations running yet: statistics, averages, current grade, etc. But you can check to see what you scored vs the max possible for each class, submission, and piece of work.

      2006-04-04 Tue Apr 4 17:04 Answer to Question about Objectives

      I was asked in class about the objectives for this course. I've given it some thought -- partly as a result of writing the first quiz/exam. Here is an initial list

      By the end of the class you'll need to be able to:

      1. Quote standard definitions(from the reading) from memory.
      2. Use definitions in proofs and calculations.
      3. Prove theorems -- novel(simpler) and previously seen(complex) using
        • Deduction
        • Reduction
        • Induction (mathematical)
        • Contradiction
        • Contrapositives
        • Counterexamples
        • If-and-only-if (iff)
        • Discrete mathematics and simple algebra.
        • Sets
        • Mappings
        • Properties of numbers.
      4. Draw diagrams using notations found in the reading.
      5. Give examples (if any exist) of practical uses of the theory.
      6. Write a short essay on the philosophy behind part of the theory.
      7. More TBA

    33. 2006-04-03 Mon Apr 3 16:04 Get ready for class 02 Today we talked about the content and process of this class. Most of this is in the syllabus and schedule or in [ 01.html ] the notes for the class.

      Next: study chapter 1 in the book, the web pages [ schedule.html#math ] on big-O and graph theory and [ Ex1.pdf ] the handed out exercises.

      Submit a question before 12:30 on Wednsday on the above, and bring a written solution to one exercise to class with you.

    34. 2006-03-29 Wed Mar 29 11:03 Preparing session 02 I got the materials for session printed ready for Monday's class. Then I discovered some changes that I've posted to the web.

      The most important discovery is that I'll have to prepare some exercises on the material in Chapter 1 plus two topics that we'll need later in the class: the big-O notation and the theory of graphs.

      Spent time late last night and early this morning on a big-O exercise....

      Today I've just upload the outline for the second class. This acts as a rough study guide. I use the outline in class as a visual aid and a way to structure the class. It will fill out when people send me questions.

    35. 2006-03-14 Tue Mar 14 08:03 Draft Schedule and Syllabus Online See [ schedule.html ] and [ syllabus.html ] for my first ideas on this class.
    36. 2006-03-07 Tue Mar 7 15:03 Books Chosen You'll need a copy of:
      2. John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman [ ialc.html ]
      3. Addison Wesley 2001 ISBN 0-201-44124-1

      (We'll cover about 50% of it in this class, the rest was in the previous quarter's theory class).

      You may find the following helpful:

      1. Author: John Martin
      2. Title: Intro to Languages and Theory of Computation
      3. Edition: 3rd
      4. ISBN#: 0-07-232200-4 [ ]

      This was used in previous editions of this class.

      My favorite book on computability is a classic:

      1. Marvin Minsky
      2. Computation: Finite and Infinite Machines
      3. Prentice Hall NJ 1967

      Pity it doesn't discuss intractable problems:-( It's probably out of print and it isn't in the CSUSB library.
    37. 2006-01-12 Thu Jan 12 16:01 Starting to get web site organized This site is in preparation for the Spring quarter 2006 edition of CSCI546 and CS646 by Richard J Botting at CSUSB Computer Sceience Department.

      An interesting web site [ ] using Java to simulate Turing Machines and Finite State Machines etc.

      A possible book:

      2. John E. Hopcroft Rajeev Motwani Jeffrey D. Ullman [ ialc.html ]
          TABLE OF CONTENTS & Schedule
        1. - Intro
        2. ++ Ch 1 Automata: The Methods and the Madness 1
        3. + Ch 2 Finite Automata 37
        4. - MidTerm
        5. *** Ch 8 Introduction to Turing Machines 307
        6. -- Project TM
        7. *** Ch 9 Undecidability 367
        8. *** Ch 10 Intractable Problems 413
        9. *** Ch 11 Additional Classes of Problems 469
        10. - Review

        (Each +-* is one class meeting: - no reading, + reading, * vital)

    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. Recursive::="Languages that can be recognised (instances accepted or rejected) in a finite runtime".
  17. RE::=Recursive_enumerable,
  18. Recursive_enumerable::="Languages that are accepted in a finite time by a TM, but may be rejected by the TM failing to halt."
  19. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  20. P::@problem=class of problems that a DTM can compute in polynomial_time.
  21. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  22. 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

  23. LOGIC::= See

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