Fundamental Algorithms, Final Examination, May 6, 1998

Explain your reasoning for each answer. An answer, such as `` '', or ``true'', even if correct, may get no credit if there is no explanation. The phrase ``sketch an algorithm'' asks you to list the steps of the algorithm in some kind of code or pseudocode.

1.

A credit card company has 50,000 active accounts, each with a unique 12 digit credit card number. For the month of April, it has 70,000 records of credit card transactions. Each transaction record has a field, record.number, which is an array of 12 characters, one for each digit in the credit card number for the transaction. Each record also has a field, record.amount, that records the dollar amount of the transaction. We want to write a program that determines the total of the amounts for each account in April. For example, if account number 2345-6789-1223 has two transactions for and respectively, then the total for 2345-6789-1223 is .

a.

Sketch an algorithm that would do this by hashing the credit card numbers from transaction records. What would be a reasonable size for the hash table? Assume the hash function is int hf(char num[12]). Use closed hashing to resolve collisions. What other arrays are needed for this task?

b.

Sketch an algorithm that would do this by sorting the account numbers in the transactions. Consider the sorting algorithms insertion-sort, quicksort, and radix-sort. Choose one of these for your algorithm. Explain your choice.

2.

In each case, state whether the assertion is true or false. Briefly explain your answer. To prove that something need not always happen, give a counterexample. For example, to prove that a graph need not be connected, just draw a graph that is not connected.

a.

Suppose that an algorithm performs operations on n objects, and that the amortized cost per operation is . Then no single operation may take more than O(n) operations.

b.

We have a weighted connected undirected graph, G, which has two subgraphs, , and . Each vertex of G is either in or in . Any edge of G that connects two vertices in is in , and similarly for . We find a minimum spanning tree for and another for . We connect these spanning trees by adding the lowest cost edge that connects to . Is it true that the result is a minimum spanning tree of G?

c.

The numbers , , are integers between 0 and 2n with no integer repeated. Then . Hint: what are the largest and smallest possible values of S?

d.

Every spanning tree of a connected undirected graph has the same number of edges.

e.

.

f.

A root of a DAG is a vertex so that doing DFS from that vertex visits all the vertices of the DAG. Is it true that every connected DAG has a root?

g.

We have a weighted graph and have computed the distance from each vertex to a source vertex, s. We now add one new edge. It is possible to determine in O(1) time whether any of the distances decreases.

3.

Sketch an algorithm that performs the following operations, which define a ``split queue''. There is a fraction, f, between 0 and 1, that is specified in the beginning and never changes afterwards. If there are n numbers in the queue, we define m to be the largest integer smaller than fn. The largest m numbers go into the ``top queue'' and the rest go into the ``bottom queue''. As n changes, some numbers may have to be moved from one queue to the other. The operations are

• insert(x): puts x into the split queue.
• delete_top(): returns and deletes the smallest number in the top queue.
• delete_bottom(): returns and deletes the largest number in the bottom queue.

The cost for each operation should be . You may use priority queue operations without saying how they work.

4.

Consider the following pseudo C code:

float bp( int x, int k ) { /* Solve an optimization problem:
           k = number of levels left.
           x = the position.  
           At each stage, you may leave x constant or decrement x by one
           (except that x is not allowed to become negative).  We want to
           optimize our reward after k stages.  There is a multiplier for
           each stage that depends on the position at that stage. */

   extern float p[n]; /* p[x] is the reward at the final stage if you are
                         at level x.       */
   extern float m[n]; /* m[x] is a multiplier that changes the reward if you
                         are at position x and there are some levels left.  */

   if ( k < 0 ) ERROR;
   if ( ( x < 0 ) or ( x > n ) ) ERROR;
   
   if ( k == 0 ) return p[x]; /* Just get the reward at the last stage.
   if ( x == 0 ) return m(0)*bp(0,k-1); /* Can't decrement x from 0.
 
   return max( m(x)*bp(x,k-1), m(x-1)*bp(x-1,k-1) );

}

a.

How much work is required to execute bp(n,n)?

b.

Rewrite bp using dynamic programming to get the same answer in work.

5.

Below is a B tree with parameter t=2. Draw the results of the following operations, each starting with the same tree: Insert 23, Delete 43, Delete 30.

6.

An undirected graph is ``bipartite'' if the vertices can be divided into two subsets, L and R, so that there is no edge connecting any vertex of L to any other vertex of L, and similarly for R. Sketch an algorithm that is a modification of DFS that determines whether a graph, G is bipartite. We may arbitrarily assign the first vertex to the L set. Then, if the graph is bipartite, the assignments of all the other vertices in the connected component are determined.

• About this document ...