-
Session Topic:
Introduction to the Course.
Included:
general introduction to the course and
review of the
Course Information Handout;
background information sheet;
diagnostic quiz (does not count towards the course grade).
- Questionnaire on Background. Here.
- Diagnostic Quiz. Here.
Note: As mentioned in class, this was just a test
(so to speak) run, and does not count towards your course grade (as a
multi-chunk quiz or otherwise).
- Diagnostic Quiz Answers.
Here.
- Diagnostic Quiz Statistics. Low/median/high: 0/1/11 (out of 30).
This quiz does not
count towards your grade, so don't panic at all.
- Reading (due 08/9/8/159pm).
-
In our Hemaspaandra-Ogihara textbook, read the
"Invitation" subsection of the Preface. This will give you
some insight into how I view complexity (the topic that we will
cover as the second part of the term). By the way, you'll notice
even in the first part of the course that many proofs are
quite algorithmic (or perhaps procedural, if you want to be very
finicky about word use).
-
In the first edition (the 1979 first edition, that is---NOT
the 2nd or 3rd editions) of
Hopcroft and Ullman's "Introduction to Automata
Theory, Languages, and Computation"
(Addison-Wesley)---which is on
reserve for us at the library--- review chapters 1, 7, and 8.
Do not use the
*second* edition of the same book
(which has DIFFERENT authors: Hopcroft, Motwani, and Ullman)---use
the first edition only for this reading.
You should also review the
following (as another treatment of some of the same stuff):
In our Bovet-Crescenzi textbook,
Chapters 1 and 2 except skip sections 2.1.4 and 2.1.5.
You can also look at the analogous parts of Chapter
2 of our (optional textbook) Papadimitriou if
you like, but actually Bov-Cre is actually
clearer on this.
-
Also, though we went over it in class today,
you should read for yourself, in full detail,
the class information handout, so
that you know the rules under which the course will
operate (it is always available,
in its most recent version, from this web site).
The version handed out in class today is version 1.00, which
is (currently) the current version.
If/when I create updated versions during the course, I
will announce that via
a "note" on the this page.
(On each version of the course
document, the base date will be the date of version 1.00 and the
"last updated" date/time will be the date/time of the version you are
looking at. Oh... if I ever say a document is up and it isn't up,
please let me know. Sometimes the TA or I put into the
web site but forget to turn it from latex into postscript, and so
we think it is up but if you click on the link it won't be there.)
- Note 1 (080903/637pm): Notes will be used by me to stick
on comments and so on. The number will be only within the class day,
i.e., the first note, if any, after the next class session will again
be a "Note 1." Note that I may put up new notes as the day goes
on, or during the days between one class and the next. Notes start
with the date/time they went up, in the format YYMMDD/time.
(I at times will, often
for emphasis, instead use
the format YY/MM/DD/time or even YYYY/MM/DD/time.)
Note: It is now 6:37pm on 9/3 and if you're seeing this and
this is the last note, please be aware that I'll probably between
now and the next class put up here
a bunch of additional notes, and most of them
will probably go up this evening (actually, I'll before saving
this file stick in lots of notes, and then save it to the web...
but even after that I might add more notes between now and next
class, so please do look here often).
- Note 2 (080903/640pm).
Oh... I'll generally try (though I am not promising this in blood) to have
the web site up and (relatively settled
regarding the stuff that happened in that day's class, except perhaps
whatever
Notes (such as this one) or quiz solutions or statistics
that will be added later) by about 9PM on the given day. A corollary
is even if you peek at the page before 9PM, you should definitely
reload the page (making sure not to get a cached copy!) after 9PM---or
early the next day---so
that you get the final version of the readings/etc. (Note: very
often I'll have it up even earlier.)
- Note 3 (080903/643pm). How to avoid having your browser
cache pages: It varies from browser to browser and I'm no expert
on that. In Firefox you might want to just bite the bullet and
set your cache size to 0 (under Tools/Options/Privacy/Cache). Under
Internet Explorer, probably a good approach is to go to
Tools/Internet Options/General/Temporary Internet Files/Settings,
and then change that to "Every visit to the page" (do NOT
trust "Automatic" to do the right thing---it does not, I think).
Note that even if you do the above things, sometimes
browsers hold things without rechecking them. This most
typically happens on things such as postscript documents
called by links from web pages (even when it knows to recheck the
web page each time, a browser may be too lazy to do that for
files in its cache). If you have problems with that, simply
emptying your cache should get you the fresh version of the object.
Note that in Netscape/Mozilla/Firefox, if you find that
it seems not to be grabbing the most current version of a web page
(and on some browsers, using the forward/back buttons
evades even the most emphatic preference settings),
it often helps to simply use
Shift-[ReloadButton] to tell it, "Go check again."
Disclaimer: Hey, I'm a theory professor, so I'm probably
the worst person imaginable to take advice from on taming your
browser.
P.S.
A bit of
additional browser
advice, from a
Firefox fan:
[Here is] how to tune cache settings for Firefox. The following steps
are used do it:
1) Type "about:config" (without quotes) in URL bar, press ENTER,
2) Find key "browser.cache.check_doc_frequency",
3) Change value to "1", which means "Check every time I view the page".
That should do it. The default is "3 (default): Check when the page is
out of date (automatically determined)", but that does not always work.
- Note 4 (080903/646pm). Don't panic; note 3 is unlikely to
be on the midterm or the Comprehensive Exam.
- Note 5 (080903/646pm). Oh... if you happen to be interested in
theory, please do feel very much invited to attend the
Rochester Theory Seminar if you wish. It is open to
the public, and is filled with lots of interesting stuff.
It meets 2 or 3 times a month, right after the CS Department
Seminar's slot.
You can find full information
via the following link:
Rochester Theory Seminar Home Page.
- Note 6 (080903/653pm).
The two chapter 1's (chapter
1 of Bov-Cre and chapter 1 of Hop-Ull) from your reading assignment
give some coverage of discrete math
basics. However, if you are seriously short of discrete math
background, that is a severe worry. If you fall in that
category, *please* read
carefully one or more of the following
excellent discrete mathematics books, some of which
are on---or on the way to coming back from recall and
being on---reserve for our course (Biggs;
Graham-Knuth-Patashnik; Gries-Schneider; Maurer-Ralston; Rosen) on
reserve. The best one to start with is perhaps Rosen---if you have
problems with proofs, pay particular attention
to Chapter 3, and to the proofs throughout Rosen's book.
In particular, though we will read or cover quite a bit about
undecidability, we can't possibly build the MTH150 course (the
undergraduate discrete math course) into this course. So, do make
sure that you know (as in, by this coming Wednesday at latest) the
equivalent of MTH150. As to what that means, you can easily see that
(and, implicitly, what to read in Rosen)
from the MTH150
web site's course outline.
- Note 7 (080903/703pm).
Very many people seem not to have ever seen or had a course touching
on how to prove things undecidable. (Many people seem to have
had an undergraduate models course that covered regular sets,
CFLs, and Turing machines, just stopped just sort of reaching such
issues as undecidability.)
So, if you are such a person---someone who has not before
had a course that covers how to prove something undecidable,
you have much company.
This isn't a cause for panic. Rather, in light of how many
people have this particular background, we'll do the following. The
coming lectures will take as a starting point that people know the
basics of Turing machines (and your current reading assignment will
review even that, and at the very start of Monday's class I'll
actually quickly define even the basic formalization of Turing
machines), but we will as part of this course review the definitions
of recursive/RE/undecidability, and cover in quite good detail the
techniques for proving undecidability, and will try to do so in such a
way that even people who have not had that before will, with serious
effort, be able to learn it from this class. (I apologize to the
people---for example, all the undergraduates---who are coming in
with a broader exposure, in case this prefix of the course may be a
bit repetitive to you. However, Knuth, one of the most brilliant computer
scientists ever, always says that he himself only learns something
deeply after seeing it at least twice. So maybe the review
will help you lock this material in even more firmly.)
As a side effect of the above, let me mention that if there is a
surprise quiz this Monday, I will *not* ask you to already on that
prove things undecidable. So, just to be clear
about this particular possible surprise quiz (or surprise
quizzes!): Anything about the course
logistics mentioned
during the first class session might be on the quiz, anything about the
course info handout might be on the quiz, but as to reading material,
for this particular quiz, what might be asked includes just:
the "Invitation" of Hem-Ogi, Chapter 7 of the *first*
edition of Hop-Ull (yes, classic 1979 edition with only two authors, not
the lower-level second edition)
and Chapter 2 of Bov-Cre except not sections 2.1.4 and 2.1.5 and 2.2.
(This doesn't mean you should ignore the other stuff, such
as Chapter 8 of Hop-Ull and Section 2.2 of Bov-Cre, but rather,
I'm just trying to more tightly define what might be on the quiz.)
Quizzes can be of any form. For example, regarding Chapter 7 I
might (or might not!)
give one or two theorems from your readings---or things that
look very similar to those theorems but are not (or are) true
statements. Note that you generally will have
a much better shot of doing well on quizzes if you do the reading
carefully and make a good notes sheet. And of course,
making this page your home page (or at least reading it
all the time) is a good idea, so that you can read (with
luck) helpful notes such as this one.
- Note 8 (080903/718pm).
A reminder regarding the books on reserve at the
library:
Please remember, if you look on the regular shelves under their
call numbers for books on our
reserve list, you'll usually find nothing. That is because books on
our list are on reserve.
What this means
is that you must to go the library main desk to request it (and so
that everyone can have a chance to with luck have
equal access it can be kept out for a fixed period of
time---2 hours for some books
and overnight for
the others).
By the way, you are responsible for all the readings, even if you
have bad luck and the reserve copies are heavily checked out. It is
true that the reserve copies can get very busy during the few days
before a class (that might have a surprise quiz---and they all might)
or before a homework set is due, so if you want to use those, you'll
want to start very early to be safe.
- Note 9 (080903/719pm). Regarding "Hopcroft-Ullman"
(which, in the second/third editions, actually adds Motwani as an author),
please don't confuse the editions, or do problems or
readings in one when I in fact ask you to do such in the other.
(note that the chapter numbers and problems are NOT identical between
the editions). FYI,
the first edition is written at a far more
advanced level/flavor than the second and third editions.
Almost always when I
use one, it will be the first edition that I use (the one with
copyright date 1979!!!!... not the copyright date 1969 one, and not
the one copyright date 2000 one, and not the copyright 2006 one).
- Note 10 (080903/725pm).
I commend to your attention the rules of the course regarding the one
sheet of handwritten self-prepared notes that you are allowed to use
on surprise quizzes. (I think the act of distilling information
and preparing such a sheet is itself a valuable learning experience.
And who knows... when you are sitting there at some quiz with your
books and notes closed to you, you might at times be very happy to have your
one-page-of-wisdom open to you.) Of course, so far we're only coming
to the second class, so maybe you think there is not much
to write down... but when we're a bit deeper into the course,
and you (with luck) have lots of learned things to organize, the notes
sheet can really be a help... and even before next class, you'll have
a reasonable amount of information (from the readings, for example!) to
distill.
- Note 11 (080903/728pm). Oh... just to
make sure no one has any unpleasant surprises later in the term
regarding academic honesty or regarding grading/regrading rules:
-
please do read extra carefully the section of the course info handout
called "homework preparation" so you know what is cheating (as that
is very very bad and the school's firm academic honesty rules apply in
that case) and, and this is important too, what is quite allowed in
the course (as knowing that will help you learn collaboratively with
your class colleagues).
- please do read carefully the grading
rules... e.g., regarding chunks and dropped chunks
For example, a quiz that has 6 10-point questions
might if one were careless look like a 60-point quiz as it has 60
points (and we list the statistics on such things and homeworks and so
on in terms of a 0-60 or 0-whatever range), but do keep in mind that
it in terms of chunks such a quiz is six separate 10-point chunks when
it comes to the issue of computing your grade and chunk-dropping.
NOTE IN PARTICULAR: Sometimes a question may look as if it
is an integral 20 (or 30, or) point question. Such things
are handled as follows (in the case of 20, in this example).
It is actually two identical 10-point chunks, i.e.,
if you got 7/20 then this is recorded as two 3.5/10 scores. you'll
see this type of superchunking in a big-time way if we have a course
project---e.g., if the project has the value of K points (K being
a multiple of 10), it actually will be K/10 identical chunks, each
of which will have the score YOURSCORE (out of an ideal total of K)
times 10 divided by K---and possibly on midterms or elsewhere.
- Note 12 (080903/737pm). As to Homework Set 1 (and maybe
even Set 2), it probably
will be given out sometime next week. For now, please focus mostly on
the things mentioned above, such as the reading (and, if you have
worries about background in discrete math or DFAs/NFAs and so on, in
also doing reading related to those).
- Note 13 (080903/741pm). I've already sent transparency copies
to Carlson library, and I see they show up already in the
reserve collection list online, under the strange
item title "CS 286" and kept on the
reserve course notebook shelf.
There is also a
copy
in the black "486" box in the 7th floor mailroom.
Note
that neither version should be permanently taken---they are just
masters from which to make a copy, if you wish to have a copy.
Also, the library in concept is scanning it in and will put a copy
electronically online as an e-reserve for the course and when they
do that you could alternatively print it from there.
The
following disclaimer applies:
No promises of any sort are made about these xeroxes (some
slides may be missing that I will use, some that are in the packet
I won't use, some I'll have edited somewhat before using them,
etc., etc.). They are simply made available to you in case you
choose to make a copy of them. Note: The first sheet has the
number "0" and the last one has the number "101," so there are 102
sheets in total in the packet.
But indeed you should each please make a xerox of this
about-102-page-long item, as it will save you lots of note-taking
time/effort in class. Namely, you might wish to add your own
hand-made class notes right
onto these sheets during class.
- Note 14 (080903/743pm). Usually, we will not put a note up
when we put up the scores or answer sheets. They have slots around where
they naturally belong,
and will appear there typically before the class or two after the item
for the case of scores, and also for the case of answers in those cases
where there is a slot for answers.
- Note 15 (080903/753pm). FYI, when
we update an already posted answer sheet and the changes
are important, we will
typically post a note letting you know to re-download the
revised answer sheet. Answer sheets will always
(unless we're careless), if they have been
revised, contain the revision date and time.
- Note 16 (080903/753pm). Reminder: If you want a
bookmark that will always take you to the most recent material on
the page directly (i.e., to the bottom of the page, rather
than the top of the page), please look,
near the top of the page, at the discussion under "Navigation
Information." Myself, I do use that suggestion regarding my bookmark
for the page---so that I always when I click on my bookmark indeed
get sent to whatever is most recent. (My guess is that you also
will want to use that. It save you from having to scroll down
the web page each time.)
- Note 17 (080903/808pm).
Oh... most of the documents for the course will go up as postscript
documents. Of course, the URCS machines have postscript previewers,
and free postscript previewers are easily available, e.g.,
at this site.
- Note 18 (080903/808pm).
One yellowjacket will typically the class days on this page.
But at the bottom of the page there will be two yellowjackets, back to
back, so that is an easy way to tell if you are looking at the
bottom of the page.
- Note 19 (080905/1256pm). This note modifies Note 7
above. Regarding any possible quiz Monday, in addition to everything
Note 7 puts as potentially on the quiz, all of the discrete math
prerequisites are also fair game to be on the quiz (see Note 6 for
points on how to review discrete math if you've forgotten it). If I
were you, I'd make sure to come into class on Monday with a very firm
grasp of such notions as, for example, proof by induction. If there
is a quiz Monday (and there very, very well might be), it might very
well be for a short period of time yet have multiple questions on it,
so you'll want to come into class with a firm, comfortable control of
the items mentioned in Note 7 and earlier in this note (as there will
not be time during the quiz to thrash around).
- Note 20 (080907/1232pm).
As I mentioned earlier,
usually, we will not put a note up
when we put up the scores or answer sheets. They have slots above where
they naturally belong,
and will appear there typically before the class or two after the item
for the case of scores, and also for the case of answers in those cases
where there is a slot for answers (typically quizzes and
in-class midterms; homework sets we'll instead go over in class).
However, because this is the
first time any answer set has gone up, let me mention that
you can now find (in the natural place above) answers for the
diagnostic quiz. But do not worry---I will NOT on Monday quiz you
again on building such reductions... rather, we'll (rather quickly, I
hope) via reading and class lectures build to the point where you can
(I hope) confidently do such proofs.
Although we as I just mentioned typically don't mention when
answers go up, and exception is that we do typically mention when
answer sets that were up get modified, and we already have the first
example of that. Regarding the diagnostic quiz, please make sure you
have the version that is marked "revised 080907/1229PM" (an earlier
version was up on the web very briefly so if you printed it, please
chuck that and use the revised answer set).