CS 381
Introduction to the Theory of Computation
Summer 2003

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, 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 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 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).