20060617 Sat Jun 17 13:06 Grades for final and course published
Grade Distribution  A/A  B/B/B+  C/C/C+  D/D/D+  F


Frequency  3  6  2  1  0

Please check for errors and tell me as soon as possible.
20060613 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...
20060612 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
 rbotting at CSUSB....
with
 cs546
or
 cs646
as the first 5 characters of the Subject.
20060607 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.
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.
There are talks at 10:11:30, 11:3012:30 and 12pm:
[ ../seminar/20060609UCSBTalks.txt ]
(I'll offer 646 and 546 credit for the first one).
 17:06 Grades have been posted!
20060602 Fri Jun 2 15:06 Joke proofs added
[ 02.html ]
20060602 Fri Jun 2 14:06 Relevant Talk coming up next Friday
Sara Woodworth (swood@cs.ucsb.edu) 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!
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.
 20060526 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...
 20060523 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!
 20060522 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
 w x y z + u + v
or
 w x y z + (u + v).
First convert the second term to CNF
 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:
 (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 3CNF by replacing the 2literal clauses
by a product of two 3 literal clauses.... again adding more varaibles
 (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)
 20060518 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).
 20060516 Tue May 16 13:05 Grades posted.... Intractable Problems Ahead
See
[ 14.html ]
for more information.
 20060511 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 ]
 20060509 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)
 20060504 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 nondeterministic
Turing Machines to class.
 20060501 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.
 20060428 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.
 20060427 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
 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
 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.
 20060425 Tue Apr 25 15:04 Grades posted and URLs are arriving
See
[ 08.html ]
for the assigned work and preparation for the next class.
 20060423 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
 {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.
 20060420 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:
 20060419 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 nondeterministic
TMs by using a queue and breadthfirst search.
 20060418 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...
 20060417 Mon Apr 17 09:04 Most question for sesion 5 are in  thanx
[ 05.html ]
 20060413 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.
 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.
 20060412 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.
 20060411 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.
 20060406 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.
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:
 Quote standard definitions(from the reading) from memory.
 Use definitions in proofs and calculations.
 Prove theorems  novel(simpler) and previously seen(complex) using
 Deduction
 Reduction
 Induction (mathematical)
 Contradiction
 Contrapositives
 Counterexamples
 Ifandonlyif (iff)
 Discrete mathematics and simple algebra.
 Sets
 Mappings
 Properties of numbers.
 Draw diagrams using notations found in the reading.
 Give examples (if any exist) of practical uses of the theory.
 Write a short essay on the philosophy behind part of the theory.
 More TBA
 20060403 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 bigO 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.
 20060329 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 bigO notation
and the theory of graphs.
Spent time late last night and early this morning on a
bigO 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.
 20060314 Tue Mar 14 08:03 Draft Schedule and Syllabus Online
See
[ schedule.html ]
and
[ syllabus.html ]
for my first ideas on this class.
 20060307 Tue Mar 7 15:03 Books Chosen
You'll need a copy of:
 INTRODUCTION TO AUTOMATA AND LANGUAGE THEORY
 John E. Hopcroft & Rajeev Motwani & Jeffrey D. Ullman
[ ialc.html ]
 Addison Wesley 2001 ISBN 0201441241
(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:
 Author: John Martin
 Title: Intro to Languages and Theory of Computation
 Edition: 3rd
 ISBN#: 0072322004
[ http://highered.mcgrawhill.com/sites/0072322004/ ]
This was used in previous editions of this class.
My favorite book on computability is a classic:
 Marvin Minsky
 Computation: Finite and Infinite Machines
 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.
 20060112 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
[ http://jflap.org ]
using Java to simulate Turing Machines and Finite State Machines etc.
A possible book:
 INTRODUCTION TO AUTOMATA AND LANGUAGE THEORY
 John E. Hopcroft Rajeev Motwani Jeffrey D. Ullman
[ ialc.html ]
TABLE OF CONTENTS & Schedule
  Intro
 ++ Ch 1 Automata: The Methods and the Madness 1
 + Ch 2 Finite Automata 37
  MidTerm
 *** Ch 8 Introduction to Turing Machines 307
  Project TM
 *** Ch 9 Undecidability 367
 *** Ch 10 Intractable Problems 413
 *** Ch 11 Additional Classes of Problems 469
  Review
(Each +* is one class meeting:  no reading, + reading, * vital)