- Exam policies
- You must take the exam in the lecture section you are
officially registered for.
- You must bring your student ID with you to the exam.
- After taking the exam, you may not communicate
with anyone about the exam until after 1:30pm on Wednesday.
- Closed book, closed notes.
- No calculators, cell phones, or other electronic devices allowed.
- 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.
Topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)
- Stacks and Queues - array and linked list implementations. Runtimes.
- 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
- Related: Perfect and Complete Trees.
- 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
- D-heaps - how different/related to Binary Heaps
- 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 do not need to memorize the proof, but being familiar with how you construct the worst case AVL tree may be helpful)
- Insertions; different rotation cases, no delete
- Run-time for find & insert
- Memory:
- Temporal and spatial locality
- Data structure choice and locality
- B-Trees:
- Motivation for the B-Tree; how it can minimize disk accesses
- Structure, ordering; use of M, L; principles behind the selection of M & L
- Insertion, find, deletion; the rules followed for insertion and deletion will be those shown in lecture
- Run-times of the above
- Hashtables:
- Basics of good Hash function design
- 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 Testing
- Java syntax
Misc.:
- Note that you may 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. Any such
proof will be intended to show that you know how to prove
things. You will not be expected to have a "magic insight" in
order to complete the proof.
- The homeworks thus far are a decent indication of the types of
questions that could be asked.
Previous Exams
We provide some exams from previous quarters of 332 and 326 to
help with your studying. Be aware that 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
most definitely NOT, I repeat *NOT* take them as a guarantee of
exactly what your exam will be like this quarter*. They are
provided only to help you in your studying.
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.
Good luck with your exam studying!