Data Structures & Algorithms

Exam 3, Sample 3

2 Hours


Notes:
  1. Points allocated to each part are shown in square brackets. Answers will be graded on correctness as well as efficiency, elegance, and other measures of quality.
  2. Make sure you understand the problem before attempting to answer it.
  3. Write partial answers when you cannot figure out a complete solution.
  1. [12] Define the length of a path to be the number of edges on the path. A shortest path is a path with fewest edges. You are to write a method public void nearest(int i, int d, int [] reach). The invocation g.nearest(theI, theD, theReach) labels all vertices j such that the shortest path from theI to j has at most theD edges. You may assume that, initially, theReach[j] > theD for all vertices j. When done, theReach[j] equals the length of the shortest path from theI for those vertices j that have been labeled by your code. For the remaining vertices, theReach[j] is unchanged.
    (a)
    [10] Write Java code for the method nearest. If you need to use a stack or a queue, use either ArrayStack (the relevant methods are empty, push, and pop), or ArrayQueue (the relevant methods are isEmpty, put, and remove). Use iterators to move around the graph. The statement
    Iterator iw = iterator(w);
    gets you an iterator for vertex w of the graph, and the statement
    u = ((EdgeNode) iw.next()).vertex;
    gets you a vertex that is adjacent to vertex w.
    (Hint: one of the standard search methods may work.)
    (b)
    [2] What is the complexity of your labeling method as a function of the number of vertices that are labeled and of their out-degrees? Provide this complexity under the assumption that adjacency lists are used. Explain your analysis (a few lines only).

  2. [8] Consider the following undirected graph.


    (a)
    [4] A minimum-cost spanning tree is to be constructed using Kruskal's method. Describe the working of Kruskal's method on this graph. Draw the spanning tree that is constructed and also give the steps (draw figures and state the dicision made at each step) used to arrive at this tree. What is the cost of the constructed tree?
    (b)
    [4] Do part (a) using Prim's method instead of Kruskal's method.

  3. [12] The 1D array x[] is a sorted array iff x[0] < x[1] < x[2] < ... < x[x.length - 1]. A sorted aray has an equilibrium point iff there is an i, 0 <= i < x.length for which x[i] = i.
    (a)
    [10] Write Java code for the method public int equilibriumPoint(int [] x). You may assume that x is a sorted array. If the sorted array has no equilibrium point, your method should return -1. If the sorted array has an equilibrium point, your method should return an integer i such that x[i] = i. Use divide and conquer.
    (b)
    [2] What is the time complexity of your method? Explain how you arrived at this complexity.

  4. [20]
    (a)
    [4] In the Bellman-Ford single-source all-destinations shortest-paths algorithm, d(v,k) is the length of a shortest path from the source vertex to vertex v, under the constraint that the path has at most k edges; p(v,k) is the vertex (if any) that comes just before vertex v on this constrained shortest path. The p matrix computed for a certain 7 vertex graph is given below. 
                          v  ------>
            [1] [2] [3] [4] [5] [6] [7]
      [0]    -   -   -   -   -   -   -
      [1]    -   1   1   -   -   1   1
 k    [2]    -   1   6   2   6   1   6
 |    [3]    -   1   6   2   3   1   4
 |    [4]    -   1   6   5   3   1   5
 V    [5]    -   4   6   5   3   1   5
      [6]    -   4   6   5   3   1   2
    The source vertex is vertex 1. Determine the shortest path from the source to vertex 7. Show how you obtained your answer.
    (b)
    [4] Consider Floyd's all-pairs shortest-paths algorithm. This is based on the dynamic-programming recurrence:

    c(i,j,k) = min{c(i,j,k-1), c(i,k,k-1) + c(k,j,k-1}, k > 0

    where c(i,j,k) is the length of the shortest path from i to j that goes through no vertex larger than k. Explain why the following pseudocode computes c(i,j) = c(i,j,n) when started with c(i,j) = c(i,j,0) (n is the number of vertices in the graph). 
    for (int k = 1; k <= n; k++)
   for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
         c(i,j) = min{c(i,j), c(i,k) + c(k,j)}
    (c)
    [4] n items are to be packed into the fewest number of bins. The height of each bin is h, and the height of item i is h(i). Each bin must contain a consecutive set of items. For example, if items 2 and 5 are packed into the same bin, then items 3 and 4 must also be packed into this bin. The items in a bin are packed in ascending order of item index from bottom to top. For example, if items 2 through 5 are packed in a bin, then item 2 is at the bottom and item 5 at the top. Let p(i) be the height of padding needed at the bin bottom (or top) when item i is the bottom (top) item of the bin. So, items 2 through 5 can be packed into the same bin iff h(2) + h(3) + h(4) + h(5) + p(2) + p(5) <= h. You may assume that h(i) + 2p(i) <= h for all i. Let bins(j) be the minimum number of bins needed to pack items j through n. So bins(n+1) = 0. Obtain a dynamic programming recurrence for bins(j), 1 <= j <= n.
    (d)
    [8] Students in an algorithms class obtained the following dynamic programming recurrence for a certain problem.

    q(i,j) = 0, i = n+1 or j = m+1
    q(i,j) = 1 + q(i+1, j+1), if ai = bj
    q(i,j) = max{q(i+1, j), q(i, j+1)}, otherwise

    Write a nonrecursive O(mn) time algorithm to compute q(i,j), 1 <= i <= n+1, 1 <= j <= m+1. Pseudocode will suffice. a1...an, b1...bm, m and n are inputs to your algorithm. Show that the complexity of your algorithm is O(mn).
    Solutions