The exam will consist of short-answer questions, multiple choice questions, understanding written code, and writing your own code. The emphasis is on reading and writing code, and it is cumulative. The following materials are considered fair game:
If you're pushed for time, my personal recommendation is to spend the majority of your time studying the code you wrote for your labs. You may also benefit from writing additional code.
What is the time complexity of removing a node from a binary search tree? Why?
O(N). Worst-case scenario, the tree will have the
shape of a linked list, and removing elements from linked lists
occurs in O(N).
What is the time complexity of removing a node from a balanced binary search tree? Why?
O(log(N)). The longest path from the root to
any other node is log(N).
For an arbitrary binary search tree, how many levels deep
could a tree containing N nodes be?
N
For a balanced binary search tree, how many levels deep
could a tree containing N nodes be?
log(N)
In what ways are heaps different from binary search trees?
Heaps have the heap property, which stipulates that all parent nodes must be greater than or equal to their children. With binary search trees, the left child must be less than the parent and the right child must be greater than the parent.
In what ways are heaps similar to binary search trees?
Both are binary trees.
Assuming a heap is complete, how many levels deep is a heap
containing N nodes guaranteed to be? Why?
log(N). Complete trees are balanced, and with
balanced trees the longest path from the root to any node
is log(N).
Name and describe an abstract data type which can be efficiently implemented using heaps.
Priority queues work much like queues, except the ordering is determined by some priority which is assigned to input elements as opposed to strictly by when nodes were inserted.
Be able to illustrate how bubbleUp works, given a heap
and an element which is to be enqueued. You should be able
to draw out the different intermediate forms of the data structure
as it is processed (i.e., the results of the various swaps
performed).
Draw out any heap and go through the whole process of enqueueing an element.
Be able to illustrate how bubbleDown works, given a
non-empty heap. You should be able
to draw out the different intermediate forms of the data structure
as it is processed (i.e., the results of the various swaps
performed).
Draw out any heap and go through the whole process of dequeueing an element.
Given that your labs have not required you to implement anything regarding hash tables, there will be no questions requiring you to implement anything regarding them. However, you should still understand the basic ideas behind how they work, and be able to draw diagrams consistent with the hash table implementation discussed in Tuesday's lecture.
What is the worst-case time complexity of looking up an element in a hash table?
O(N)
What is the best-case time complexity of looking up an element in a hash table?
O(1)
Name two reasons why hash tables are used.
Typically lookups and additions are O(1), despite
the O(N) time complexity.
Do not require us to define an ordering of the keys, only equality. This is in contrast to something like a balanced binary search tree, which requires a total ordering to work.
(Advanced) computers work better with arrays than with linked data structures, and we can expect better performance out of such a data structure.
List two situations in which hash tables are likely to degrade
from the best-case O(1) complexity into the worst-case
O(N) complexity. Discuss how to remedy these situations.
Small array to many elements. Pre-allocating a large array or dynamically reallocating and redistributing elements can get around this problem.
Poor hash function, as with return 0.
A simple solution is to take more care in defining the
hash function.
Given a hash function and a series of key/value pairs, draw out a hash table which results from adding all the elements in sequence.
You should experiment with this one yourself. The week 9 lecture 1 notes cover one example, but you should be able to work with your own as well.