Math 211
Exam #2 review
Cavaet: 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 second hour exam will be Friday, October 14, and will cover sections 2.2
(Growth of functions) through section 3.4. In your review look over assigned
problems, definitions, and biographical essays. In particular, be able to
- Be able to describe the algorithms for linear and binary search and for
bubble sort.
- Be able to define and use O, Ω, Θ. Be
able to find the "witnesses" for these.
- Know the order of the functions we have used
so far for O (log n, n, nlog(n), etc.).
- Be comfortable with the basic number theory
discussed so far, including modular arithmetic and the statement of the
fundamental theorem of arithmetic. Be able to calculate the greatest common
divisor both by prime factorization and Euclid's algorithm (either the
textbook version or the version discussed in class).
- Be able to convert amongst radix 2, 8, 10,
and 16, and to do binary arithmetic.
- Be able to calculate the internal
representation of an integer.
- Be able to calculate with matrices, including 0-1 matrices.
- Be able to describe in detail what a proof using mathematical induction
looks like, and be able to prove basic theorems (on the order of the homework
exercise assigned 10/7) using mathematical induction.
- Be able to construct and use recursive definitions.
- Be able to work with summations and sequences
- Know (as always) the brief biographies in the
reading (same sort of question as before).
- We didn't talk very much about proof methods
(except for mathematical induction). Mathematical induction will be on
this test, but the other material (including descriptions of famous problems)
will not.
Any questions? Please ask! - Bob