CSE 332 Winter 2011 Midterm

Midterm Exam: Monday, February 7, 2011

Exam policies
- Closed book, closed notes.
- The exam begins promptly at 2:30 and ends at 3:20.
All material from lecture 1 up to and including hashing is fair game; sorting will NOT be on the midterm. Check the lecture calendar for links to all slides and ink used in class, as well as readings for each topic.

Winter 2011 Midterm, Sample Solution

Topics (not necessarily an exhaustive list):

Stacks and Queues - array and list implementations.
Big Oh (and Omega & Theta):
- Know the definition
- Be able to evaluate whether f(x) is O(g(x)), Big Omega, Big Theta
- Be able to find constants c & n0 to demonstrate Big Oh, Big Omega, Big Theta
- Examining code to determine its Big O running time.
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
Dictionary ADT: insert, find, delete
Binary Search Trees:
- Binary property, BST ordering property
- Inorder, Preorder, Postorder traversals
- 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, no delete
- 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)
- Deletion
- Rehashing

Stuff that you will NOT be tested on:

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 simple proof of some sort is a possibility
The homeworks thus far are a decent indication of the types of questions that could be asked

Previous Exams

This quarter's midterm will be along the same general lines as 332 midterms from previous quarters & 326 midterms in prior quarters, though the topics covered may vary (especially from those in the 326 midterms). Our hope is that these exams will be useful in your studying, but you should not take them as a guarantee of exactly what your exam will be like this quarter.

Previous CSE 332 Exams

Old CSE 326 Exams

We did not cover as many priority queues and balanced trees, so ignore questions about skew heaps, leftist heaps, binomial queues, null path lengths, and splay trees. Many of the old exams do not have sample solutions available, but feel free to post to the message board or ask the course staff if you have questions.