2006-06-17 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.
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
- rbotting at CSUSB....
with
- cs546
or
- 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).
- 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 (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!
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.
- 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...
- 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!
- 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
- 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 3-CNF by replacing the 2-literal 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)
- 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).
- 2006-05-16 Tue May 16 13:05 Grades posted.... Intractable Problems Ahead
See
[ 14.html ]
for more information.
- 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 ]
- 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)
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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
- {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.
- 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]](NTMtreeOfIDs.gif)
- 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.
- 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...
- 2006-04-17 Mon Apr 17 09:04 Most question for sesion 5 are in -- thanx
[ 05.html ]
- 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.
- 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.
- 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.
- 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.
- 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:
- 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
- If-and-only-if (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
- 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.
- 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.
- 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.
- 2006-03-07 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 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:
- Author: John Martin
- Title: Intro to Languages and Theory of Computation
- Edition: 3rd
- ISBN#: 0-07-232200-4
[ http://highered.mcgraw-hill.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.
- 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
[ 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)