Math 210
Exam #4 review
(Draft)
Caveat: Although I try to be comprehensive in these exam reviews,
please understand that you are responsible for the material covered since the
last exam. If you notice something that I have missed, please do let me
know.
The fourth hour exam will be Friday, April 29, and will cover
sections 4.1 (recursion, again) through section 4.3 of the textbook, and through
section 2.5 and section 2.8 (skipping material on regular expressions) in the
handout on formal languages In your review look over assigned problems and definitions.
- More induction
- Big-O and Big-Theta
- Be able to give closed form equations and
asymptotic analysis of first order linear recurrences.
- Be able to give big-theta descriptions of
"divide and conquer" algorithms. In particular, know Lemma 4.7 on page
209
- Be able to sketch a finite state automata
from a state-transition table.
- Be able to construct a state-transition
table from a finite state automata diagram
- Given either a diagram or a
state-transition table for a finite state automata and example strings, be
able to trace the workings of the finite state automata and say if the
string is accepted or not.
- Be able to give an overview of the
compilation process, saying (roughly) what goes on at each step.
Any questions? Please ask! - Bob