Foundations of Computing Theory Midterm

Topics

• The book: Chapter 0, Chapter 1, Problem 1.51, Problem 1.52 and answer, and the minimization algorithm from Problem 7.42.
• The notes: All notes from weeks 1-5 (before Chapter 2).
• Homeworks 1-4.
• Everything we did in class weeks 1-5 (before Chapter 2).

Notes:

• You do not have to memorize proofs, but you should understand the proofs.
• You should know and be able to apply the constructions in the proofs, like the subset construction, the minimization algorithm, DFA to regular expression, regular expression to NFA, etc.
• You should be able to do simple proofs. This includes, but is not limited to, proofs by (structural) induction, proofs by contradiction, and proofs of non-regularity.
• The midterm will be closed book and notes, but you may bring one sheet of letter-sized paper with your own hand-written notes. You may write on both sides.
• The midterm will consist of five or six questions of equal weight. Your lowest question score won't count. Since it is often hard to judge how well you did on a question, make sure to answer all questions.
• The midterm can not be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required. If at all possible, you should contact me prior to the midterm. Oversleeping, cars that don't start etc. do not constitute a valid excuse.
• Calculators, cell phones, PDAs, etc. are not allowed. I suggest that you bring a watch.
• The midterm is worth 25% of your course grade.
• To get some idea of the format of the midterm and the level of difficulty of the questions, you can look at an old midterm. This is just to get some idea. The old midterm does not guarantee anything about the topics of the questions on your midterm and it does not guarantee the exact level of difficulty of the questions on your midterm.
• answers to old midterm.

4003-700