CS146 Practice Final
Return to classpage.
1. Show after each insertion the Binomials queues one would get after
inserting the elements 2, 7, 1, 3, 4, 5 into an initially empty
Binomial queue.
2. Suppose we 7-sort and 3-sort an array a. List all the
possible orderings of a[0], a[3], a[8], a[11], a[15].
3. Suppose in Quicksort we always choose the middle position in the array
as pivot. Prove or disprove: There are sequences which will cause
Quicksort to have quadratic worst case behavior?
4. Explain using an example how two-way merge sort works? When would
one use this kind of sorting scheme.
5. Suppose we have Disjoint Set ADT with 6 elements where everything is
initially disjoint. Show the resulting array after each of the
following operations if we are using union by size without path
compression: union(1,2), union(3,4), union(0,2), union(1, 0), union(3, 0).
6. Show step by step how the topological sort algorithm would sort the
graph below:
(a)--->(b)
| ^ \
V | \
(c)--->(d)-->(e)
7. Show how Dijkstra's algorithm would find the shortest path from s to t
in Figure 9.79 from the book. How can we modify Dijkstra's algorithm
to compute a minimal spanning tree?
8. Show how the Network Flow algorithm from class would compute a maximal
flow for the following graph (the edge in the middle goes b to a):
5
(s) --->(a)
| 7 _/ |
8 | _/ | 10
V / V
(b)--->(t)
6
9. Given two graphs G and H, the subgraph isomorphism problem is to determine
if H is isomorphic to (the same graph as) a subgraph of G. Prove this
problem is in NP and is in fact NP-complete.
10. Use the Huffman algorithm to find an encoding scheme for the following
characters using the frequency table provided.
Character Frequency
a 20
b 5
c 6
d 19
e 30
f 27
|