Quiz 3

The third quiz will cover everything we have learned in the course, but will focus algorithm analysis. Note that algorithm analysis and big O deal with many of the topics from earlier in the course: relations, functions, propositions, predicates, sets, and of course proofs and thus all of the proof techniques. Thus, while the questions will focus on big O and algorithm analysis, you will want to be familiar with the ideas from earlier in the course.

The quiz will have five parts.

1. Given some propositions about big O and their proposed proofs, identify whether the proof is valid or not.
2. Given a function, prove that it is big O of another function using the defintion.
3. Given an algorithm in pseudocode form, give a proposed function counting the number of primitive operations, and the tightest big O (i.e., big theta) runtime of the function.
4. Given a recursive algorithm, use a recurrence relation to give its runtime.
5. Drill-style questions on the analysis of algorithms.

You may bring a 3-by-5 index card of notes (front and back) to reference during the quiz. Otherwise, no other resources are allowed.