CS 61B: Practice for the Final Exam
Please try to answer these questions. We'll release solutions two or three
days before the exam. Starred problems are particularly difficult--much more
difficult than any exam question would be.
Warning: Midterm 1 topics are absent here, but they can reappear on the Final.
[1] Given an array containing the digits 71808294, show how the order of the
digits changes during each step of [a] insertion sort, [b] selection sort,
[c] mergesort, [d] quicksort (using the array-based quicksort of Lecture
31, and always choosing the last element of any subarray to be the pivot),
and [e] heapsort (using the backward min-heap version discussed in Lecture
30). Show the array after each swap, except in insertion sort. For
insertion sort, show the array after each insertion.
[2] Some sorting methods, like heapsort and array-based quicksort, are not
naturally stable. Suggest a way to make _any_ sorting algorithm stable by
extending the keys (making them longer and adding extra information).
[3] Consider the graph at right. e f
|17 |15
[a] In what order are the vertices visited using DFS | |
starting from vertex a? Where a choice exists, use 3 | 9 | 1
alphabetical order. What if you use BFS? a---c---g---h
[b] A vertex x is "finished" when the recursive call | | | /
DFS(x) terminates. In what order are the vertices |7 9| 11| /5
finished? (This is different from the order in | | |/
which they are visited, when DFS(x) is called.) b---d---i
[c] In what order are edges added to the minimum 12 14
spanning tree by Kruskal's algorithm? List the edges
by giving their endpoints.
[4] [a] How long does it take to determine if an undirected graph contains
a vertex that is connected to no other vertex [i] if you use an
adjacency matrix; [ii] if you use an adjacency list.
[b] Suppose we use DFS on a binary search tree, starting from the root.
The edge to a left child is always traversed before an edge to the
right child. In what order are the nodes visited? Finished?
[c] An undirected graph contains a "cycle" (i.e., loop) if there are two
different simple paths by which we can get from one vertex to
another. Using breadth-first search (not DFS), how can we tell if
an undirected graph contains a cycle?
[d] Recall that an undirected graph is "connected" if there is a path
from any vertex to any other vertex. If an undirected graph is not
connected, it has multiple connected components. A "connected
component" consists of all the vertices reachable from a given
vertex, and the edges incident on those vertices. Suggest an
algorithm based on DFS (possibly multiple invocations of DFS) that
counts the number of connected components in a graph.
[5] What does the splay tree at right look like after: 3
/ \
[a] max() [the operation that finds the maximum item] 1 5
/\ /\
[b] insert(4.5) \ 0 2 4 11
| Start from the _original_ tree, / \
[c] find(10) | not the tree resulting from the 7 12
| previous operation. / \
[d] remove(9) / 6 9
/ \
8 10
[6] Consider the quick-union algorithm for disjoint sets. We know that a
sequence of n operations (unions and finds) can take asymptotically
slightly more than linear time in the worst case.
[a] Explain why if all the finds are done before all the unions, a
sequence of n operations is guaranteed to take O(n) time.
[b] Explain why if all the unions are done before all the finds, a
* sequence of n operations is guaranteed to take O(n) time.
Hint: you can tell the number of dollars in the bank just by looking
at the forest.
-----
[7] [a] Suggest a sequence of insertion operations 4 |3 5|
that would create the binary tree at right. / \ -----
[b] Suggest a sequence of operations that would 2 6 / | \
create the 2-3-4 tree at right. You are / \ ----- --- ---
allowed to use removal as well as insertion. 1 3 |1 2| |4| |6|
----- --- ---
[8] Suppose an application uses only three operations: insert(), find(), and
remove().
[a] Under what circumstances would you use a splay tree instead of a hash
table?
[b] Under what circumstances would you use a 2-3-4 tree instead of
a splay tree?
[c] Under what circumstances would you use an unordered array instead of
a 2-3-4 tree?
[d] Under what circumstances would you use a binary heap instead of
an unordered array?
[e] Under what circumstances would you use a hash table instead of
a binary heap?
[9] [a] Suppose we are implementing a binary heap, based on reference-based
* binary trees (_not_ arrays). We want to implement a deleteRef()
operation which, given a _reference_ to a node in the tree, can
delete that node (and the item it contains) from the heap while
maintaining the heap-order property--even if the node isn't the root
and its item isn't the minimum. deleteRef() should run in O(log n)
time. How do we do it?
[b] Building on your answer to the previous question, explain how to
combine a min-heap and max-heap (both using reference-based binary
trees) to yield a data structure that implements insert(),
deleteMin(), and deleteMax() in O(log n) time. Hint: You will need
inter-heap pointers. Think of how you deleted edges in Project 3,
for example.
[c] How can we accomplish the same thing if we use array-based heaps?
Hint: Add an extra field to the items stored in each array.
[10] Suppose we wish to create a binary heap containing the keys
D A T A S T R U C T U R E. (All comparisons use alphabetical order.)
[a] Show the resulting min-heap if we build it using successive insert()
operations (starting from D).
[b] Show the resulting min-heap if we build it using bottomUpHeap().
[11] [a] In Lecture 26, we told you how to implement a method
smallestKeyNotSmaller(k) that returns the smallest key not less than
k in a binary search tree. If the search tree contains an entry
with key k, then an entry with key k is returned.
Describe how to implement a method smallestKeyGreater(k) that
returns the smallest key strictly greater than k in a binary search
tree. Hint: write a slightly modified version of find() that acts
as if it were searching for k + epsilon, where epsilon > 0 is an
infinitesimally small number. Therefore, it is never an exact match
with any key in the tree. (This "hint" is actually a very useful
general-purpose technique worth remembering.)
For extra practice, code it in Java. Use the BinaryTree data
structure from Lecture 26.
[b] You are given a binary search tree that is NOT a splay tree and does
* not rebalance itself. However, every node of the tree stores a
field that specifies the number of items/nodes in the subtree rooted
at that node (as described at the end of Lecture 40).
Given two search keys x and y, describe an algorithm that computes
the number of keys in the range [x, y] (inclusive) in O(h) time,
where h is the height of the binary search tree.
For extra practice, code it in Java. Assume that every
BinaryTreeNode has an extra int field named "size" that stores the
size of the subtree rooted at that node.
[12] Suppose we modify the array-based quicksort() implementation in the
Lecture 31 notes to yield an array-based quickselect() algorithm, as
described in Lecture 34. Show the steps it would use to find the median
letter in D A T A S T R U C T U R E. (The median in this case is the 7th
letter, which would appear at array index 6 if we sorted the letters.)
As in Question [1], choose the last element of any subarray to be the
pivot, and show the array after each swap.
[13] Suppose our radix-sort algorithm takes exactly n+r microseconds per pass,
where n is the number of keys to sort, and r is the radix (number of
queues). To sort 493 keys, what radix r will give us the best running
time? With this radix, how many passes will it take to sort 420-bit
keys? To answer this question, you'll need to use calculus (and a
calculator), and you'll need to remember that log2 r = (ln r) / (ln 2).
[14] Suppose that while your computer is sorting an array of objects, its
memory is struck by a cosmic ray that changes exactly one of the keys
to something completely different. For each of the following sorting
algorithms, what is the _worst-case_ possibility? For each, answer
[x] the final array won't even be close to sorted, [y] the final array
will have just one or two keys out of place, or [z] the final array will
consist of two separate sorted subsets, one following the other, plus
perhaps one or two additional keys out of place.
[a] Insertion sort
[b] Selection sort
[c] Mergesort
[d] Radix sort
[15] [Note: this is included for those who want some programming practice.
You are not responsible on the Final Exam for knowing anything about the
video Sorting Out Sorting.]
Implement tree sort (as described in the sorting video) in Java. Assume
your treeSort() method's only input parameters are the number of items
and a complete (perfectly balanced) BinaryTree of depth d in which each
leaf has an item; hence, there are 2^d items to sort. All internal nodes
begin with their item field set to null. Use the data structures below
(in which each node knows its left and right child), not a general tree.
Your algorithm should never change a node reference; only the items move.
The centerpiece of your algorithm will be a method that fills an empty
node by (i) recursively filling its left and right children if they're
empty, and (ii) choosing the smaller of its children's items, which is
moved up into the empty node. treeSort() will repeatedly: (i) apply
this method to the root node to find the smallest item remaining in the
tree, (ii) pluck that item out of the root node, leaving the root empty
again, and (iii) put the item into an array of type Comparable[]. Your
treeSort() should allocate and return that array.
public class BinaryTreeNode { | public class BinaryTree {
Comparable item; | BinaryTreeNode root;
BinaryNode leftChild; | int size;
BinaryNode rightChild; | }
} |