CS146 Practice Final


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