CSE332 Summer 2010 Midterm
What: Midterm on material up through (and including) hashing; sorting will NOT be on the midterm
When: Monday July 19th, regular class time; you'll have the full hour to work on the exam
Where: In class
How: Closed notes, closed book; however, a calculator is allowed for computations, but isn't necessary
Why: Why not?
Summer 2010 Midterm pdf and solutions
Review slides: pptx pdf
Topics (not necessarily an exhaustive list):
- Big Oh (and Omega & Theta):
- Know the definition
- Be able to evaluate whether f(x) is O(g(x)), Big Omega, etc.
- Be able to find constants c & n0 to demonstrate Big Oh, etc.
- Recurrence Relations:
- Know closed form for common recurrence relations
- Given a recurrence relation, solve to closed form
- Binary Heaps:
- Structure & ordering properties
- Insertion, findMin, deleteMin, increaseKey, decreaseKey, remove, buildHeap
- Run-times for all the above; including intuition for expected O(1) for insert & O(n) for buildHeap
- Array representation
- Binary Search Trees:
- Binary property, BST ordering property
- Find, insert & delete
- Run-times for all the above
- AVL Trees:
- BST with stored height & balance property
- Height bound resulting from balance property (you did not need to memorize the proof, but being familiar with it may be helpful)
- Insertions; different rotation cases
- Run-time for find & insert
- B-Trees:
- Structure, ordering; use of M, L; principles behind the selection of M & L
- Motivation for the B-Tree; how it can minimize harddrive accesses
- Insertion, find, deletion; the rules followed for insertion and deletion will be those shown in lecture
- Run-times of the above
- Hashtables:
- Array as underlying representation
- Key to array cell mapping
- Different versions of collision resolution:
- Separate Chaining
- Open Addressing: Linear probing
- Open Addressing: Quadratic probing probing
- Open Addressing: Double hashing
- Strengths/weaknesses of the above versions
- Load factor
- Run-times for the different versions (though you do not need to memorize the equations for expected # of probes for a given load factor)
- Rehashing
Stuff that you will NOT be tested over:
- Eclipse
- Generics
- Junit
- Java syntax
Misc.:
- Note that you WILL be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code
- Writing a proof of some sort is a distinct possibility
- The homeworks thus far are a decent indication of the types of questions that could be asked
- This quarter's midterm will be along the same general lines as the 332 midterm last quarter & 326 midterms in prior quarters, though the topics covered may vary (especially from those in the 326 midterm). Check out exams from other quarters here and here