Math 210

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 20, and will cover sections 3.1 - 3.3, 3.6 (representation of integers only), 4.1 - 4.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 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 describe in detail what a proof using mathematical induction looks like, and be able to prove basic theorems.
• Be able to construct and use recursive definitions.
• To construct recursive algorithms (in your favorite language)
• Know (as always) the brief biographies in the reading (same sort of question as before).

Any questions?  Please ask!  - Bob