General comments about what to study:

The exam will focus primarily on the last third of the course, but there
will be some material that is cumulative.  The practice exam posted gives an
idea of the balance.

Make sure you know about diagonalization, dovetailing, and their uses.
Make sure you understand the particular languages L_u, L_d.
Make sure you can do a standard reduction showing a language not recursive
by reducing the universal language to it.
Make sure you understand, in particular, all the material on the last
homework set.   There will be similar problems on the exam
Understand how TMs are coded, how the universal TM works, and why this is
significant.  
Understand how various "extensions" of TMs can be simulated by the basic TM
model.
Sometimes, we've seen TMs computing in apparently constrained ways (e.g.,
left-reset), and find out that the constraints were not really that
constraining after all.  Be able to think along these lines.
Know the proof that nondeterminism does not increase the power of a TM.
Know the definition of recursive, recursively enumerable.
Know how to simulate a generator with an acceptor, and vice versa, and the
basic theorem relating generators and acceptors.
Be able to prove various closure properties about recursive and recursively
enumerable languages.


Comments about the practice final:

Note that this is the final exam from CS 475, fall 2004, and some parts are
probably significantly harder than what we might expect.  Also, some
material was not covered in 273 that was covered in cs 475.  Below are some
general comments about what to study, as well as specific information about
the practice exam so you know how it might relate to an actual exam for this
course.

When you look at the exam, here is what I think you should be able to do, or
not...

Problems 1 and 2 are similar to problems that we will have.  I didn't look
yet at the individual parts, but you should have these skills.  Ignore
anything you might see about NP, NP-completeness, etc.

Problem 3: do the top half only.

Problem 4:  the hardest part is probably understanding exactly what is being
asked, and connecting it to what you have learned.  Parts 1, 2, and 4,
should be easy once you've done that.

Problem 5: ditto... the first two parts should not be difficult

Problem 6: while you have the tools to solve this, it may be too hard.  I am
not likely to put a problem like this on the exam

Problem 7: completely reasonable problem.

Problem 8: don't look at.