Typical Midterm Questions
CMPS 102 - W05

Simple inductive proofs and summations

Loop invariants

O-notation
- Use limits and l'Hospital's rule

Recurrence equations:
- Solve with Master Theorem
- By expanding and summing
- By guess and induction

Sorting algs:
- What are the advantages and disadvantages of each method
- What input order makes each algorithm make the most comparisons
- Which ones are stable
- Rationales for various improvements of Quicksort 
- How to make Builheap efficient
- Information theoretic lower bound
- Simple questions about average case and worst-case analysis
- What is the assumption used in the average case analyses of each alg.

Algs for finding the median or the $k$-th largest element
- What algorithm can do this in O(n) average case
- How do you do it in O(n) worst case time
- Simple questions about finding the minimum and maximum

Basic data structures
- What operations are supported by a heap
- How is a heap implemented in an array
- What addressing scheme is used

Hash tables
- Basic questions about how to construct a good hash function
- What is the problem with linear probing