Introduction to the Theory of Computation
- 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 1-14, 19-35.
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 non-creative proof. You can expect a question in which you are given a
list of languages, and have to identify whether they are regular, context-free,
Review session, Thursday, 19 June 2003, 6:00p, Hollister 362. Come with
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
- Prelim #1 will be held on Thursday, 5 June 2003, in class. It will
cover Lectures 1-9 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 half-hour if you would like.
- Review session: Reba will hold a review session, 6:00p, Wednesday, 4
June 2003. Location: B-17 Upson.
- Clarification on PS2#4,5: you may not use
epsilon-transitions in an NFA or NFA-bar. Sorry.
- Clarification on PS2#4 and the definition of a DFA/NFA: a finite
automaton has a non-empty 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:15a-12:15p in 420 Rhodes.
- David and Reba have switched office hours on Thursday, 29 May 2003:
Reba 11:15a-12:15p in 5136 Upson, David 1:30p-2: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:15a-12:15p, 5136 Upson.
- Because of the conflict with 414 lecture, David's office hours have
changed to MTWR 11:15a-12: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
- 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