CS 381
Introduction to the Theory of Computation
Summer 2003
Old Announcements
 Note on problem sets: you may use (without reproving) anything which I
proved in class or which is proved in the book.

Final: in class, 2 July 2003. You may start at 8:00a, and the exam
is open book and open notes. Coverage: Lectures 114, 1935.
You should expect to give a formal proof or two, including one which requires a small
degree of creativity. Here are some
practice problems (from Fall 2001) and a practice
final (from Summer 1999) and another
(from Fall 2002).

Problem Set #6 handed out in class on 24 June 2003; due Tuesday, 1 July 2003.

Do not use Rice's Theorem to prove anything on the problem set!

Problem Set #5 handed out in class on 18 June 2003; due Tuesday, 24 June 2003.

Prelim #2 will be in class on Friday, 20 June 2003. You can start at
8:00a, as in Prelim #1. Coverage is through
the middle of lecture on Tuesday, 17 June 2003, through Lecture 23 in Kozen.
The exam is open notes and open textbook. Sample exams from last
summer and last
fall are available. The style of the exam will be about the same as
the first exam: mostly running of algorithms/constructions from class, and
one noncreative proof. You can expect a question in which you are given a
list of languages, and have to identify whether they are regular, contextfree,
or neither.

Review session, Thursday, 19 June 2003, 6:00p, Hollister 362. Come with
questions.

Problem Set #4 handed out in class on 10 June 2003; due
Tuesday, 17 June 2003
Wednesday, 18 June 2003.

Problem Set #3 handed out in class on 3 June 2003; due Tuesday, 10 June 2003.

Required: submit comments to David! Your PS#3 grade will
depend on it.
 Improve your life: read Lecture 10 and understand what a
homomorphism is.
 Prelim #1 will be held on Thursday, 5 June 2003, in class. It will
cover Lectures 19 in the book and lectures through Friday, 30 May 2003
(plus the spillover of the example from Friday's lecture to Monday.) You can find a
copy of last summer's first prelim (with solutions) here,
and last fall's first prelim (with solutions) here.
 You may bring one 8.5" by 11" sheet of notes. You may
write on both sides, but you may not use: staples, paper clips, tape
(masking, scotch, electrical, or other), glue, etc.
 I will arrive at 8:00a on Thursday for people who would like a little
extra time. I don't believe that it will be necessary, but you are
welcome to use an extra halfhour if you would like.
 Review session: Reba will hold a review session, 6:00p, Wednesday, 4
June 2003. Location: B17 Upson.
 Clarification on PS2#4,5: you may not use
epsilontransitions in an NFA or NFAbar. Sorry.
 Clarification on PS2#4 and the definition of a DFA/NFA: a finite
automaton has a nonempty finite set of states.
 Typos on PS2#5: the acceptance conditions were all wrong. They
should have been (boldface for corrections):
 x in L(N) <=>
DeltaHat(S, x) Intersect F Not= EmptySet
 x in L(Nbar)
<=> f in DeltaHat(S,x).
 Problem Set #2 handed out in class on 27 May 2003; due Tuesday, 3 June 2003.
 David will hold office hours instead of Reba on Friday, 30 May 2003:
David 11:15a12:15p in 420 Rhodes.
 David and Reba have switched office hours on Thursday, 29 May 2003:
Reba 11:15a12:15p in 5136 Upson, David 1:30p2:30p in 420 Rhodes.
 Lecture is cancelled for Memorial Day, 26 May 2003. Office hours
will be held as normal.
 Reba's Friday office hours have changed to 11:15a12:15p, 5136 Upson.
 Because of the conflict with 414 lecture, David's office hours have
changed to MTWR 11:15a12:15p, 420 Rhodes.
 If you have not received email from David, please email him (dln@cs) to
let him know.
 For Problem Set 1: on Problem #4, you may give diagrams without
proving their correctness.
 Problem Set #1 handed out in class on 21 May 2003; due Tuesday, 27 May
2003.
 If you missed the first class, please get in touch with us ASAP.
 The purpose of this web page is for us to make announcements; handouts
will be distributed in lecture (with extras placed in the bins outside 303
Upson).