Exam 1 was Tuesday, evening, 2/28/2006,
7:00 PM - 9:00 PM in 151 Everitt Lab.
The solution is here.
Topics and Skills Review
Example Midterms:
Note that this class was last taught at a more advanced level.
Consequently, the past exams we are posting are more demanding (for
some problems) than you can expect on the upcoming exam. So, do not
panic. Read the comments provided here about which problems to ignore.
- Fall 2005 Exam 1.
(This exam was given by Professor Viswanathan.)
Ignore problem 1 parts (a) and (g).
Problem 4 is harder than what we might put on an exam, but you should
be able to understand it, and understand the alternate solution given.
(Do not bother reading the main solution.)
Ignore the last problem.
- Fall 2004 Exam 1.
(This exam was given by Professor Pitt.)
Ignore Problem 1, parts g and j. For the other parts, some of these
are trickier than we might assign in a large multipart problem. But
some are not. Problem 3's solution writeup may be cryptic due to some
terminology you do not know, but the machine described just keeps track
of the net imbalance of 0's and twice the number of 1's as it is going,
and this imbalance is somewhere between -2 and 2. If the imbalance exceeds
this in either direction, it rejects. An input of "0" adds 1 to the imbalance,
and an input of 1 subtracts 2 from the imbalance.
The following was posted in the newsgroup.
Here are types of problems
that are likely to appear on the exam:
- A pumping lemma proof.
- Implement an algorithm of some type or another that we've seen:
Convert an NFA to a DFA, or minimize a DFA, etc.
- Determine whether various languages are regular or nonregular.
- Understand the different algorithms, and why they work.
- Design a DFA, NFA, and/or regular expression, for a stated
language, and/or describe the language accepted or denoted by a given
DFA, NFA, or regular expression.
- Know how to use closure properties to prove a language is regular
or nonregular.
