- Exam policies
- Closed book, closed notes.
- No calculators, cell phones, or other electronic devices allowed.
- Writing after time has been called will result in a loss of points on your exam.
- You will be provided closed forms of any summations you need and a statement of the Master Theorem.
- All material from the course from lecture 1 up to and including
AVL trees is fair game; hashing will NOT be on the
midterm. Check the lecture calendar for links to all slides.
Possible 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
- Given code for a recursive function, find a recurrence to describe its running time or output
- Binary Heaps:
- Structure & ordering properties
- Related: Perfect and Complete Trees.
- Insertion, findMin, deleteMin, increaseKey, decreaseKey, remove, buildHeap
- Run-times for all the above; including 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
Stuff that you will NOT be tested on:
- Eclipse
- Generics
- 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 strong 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, section problems and quickchecks 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 to help with
your studying. Be aware that the topics covered may vary from what
will be covered on our exam - refer to the list above if you are
wondering about a particular topic. In particular, B-trees will not be
covered on our midterm (but will be very frequent in the old ones)
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*. They are provided only to help you in your
studying. We recommend *taking* these exams on your own in a timed
environment to get practice both with the material and with
managing your time. Most students find this approach better
preparation than just looking at the solutions.
Previous CSE 332 Exams
- CSE 332 17au Midterm,
Solution
- CSE 332 16au Midterm,
Solution
- CSE 332 15wi Midterm,
Solution
- CSE 332 14 sp Midterm,
Solution
- CSE 332 13au Midterm,
Solution
- CSE 332 13sp Midterm,
Solution
- CSE 332 13wi Midterm,
Solution
- CSE 332 12sp Midterm,
Solution
- CSE 332 12wi Midterm,
Solution
- CSE 332 11wi Midterm,
Solution
- CSE 332 10su midterm Solution
- CSE 332 10sp midterm Solution