Data Structures & Algorithms

Exam 3, Sample 1

2 Hours

1. [14] Let cost[i][j] be the cost of buying item i from store j. Let n be the number of different items and let m be the number of stores. Assume that n <= m. We are to purchase exactly one quantity of each item. Each item is to be bought from a different store. We wish to complete the purchase at a small cost. The solution to our purchasing problem is a one dimensional array x[1:n] such that x[i] is the store from which item i is to be purchased. All x[i] values are different.

   (a)

   [10] Write a procedure to determine x using the greedy method. Pseudocode (a precise statement of the procedure using a combination of English and Java) will suffice.

   (b)

   [4] Does your procedure guarantee a minimum cost solution for all instances? Prove your answer.

   
   
2. [10]

   (a)

   [6] Provide a divide-and-conquer algorithm to find the maximum of n elements. Pseudocode will suffice.

   (b)

   [3+1] What is the number of element comparisons your algorithm makes? Do you expect the divide-and-conquer algorithm to outperform the simple algorithm that finds the maximum making exactly n-1 comparisons?

   
   
3. [18] Let G be a directed acyclic graph (i.e., there are no cycles in G) with n vertices and e edges. Assume that the vertices are numbered 1 through n such that for every directed edge (i,j) in G, i < j. Assume further that S(i) is the set of vertices adjacent from vertex i (i.e., the set of j such that (i,j) is an edge of G). Let length[i][j] be the length of the edge (i,j). Assume that all lengths are > 0.

   (a)

   [15] Obtain an O(n+e) time algorithm to determine the length of the longest path in G. Pseudocode will suffice. (Hint: Define L[i] to be the length of the longest path that originates at vertex i.)

   (b)

   [3] Show that the complexity of your algorithm is, in fact, O(n+e).

   
   
4. [8] Let G be an undirected graph. We are interested in deleting the smallest number of vertices from G so that the resulting graph has no cycles. (When a vertex is deleted, all edges incident to it are also deleted.)

   (a)

   [2] Obtain a formulation for the solution space for this problem. Your formulation must correspond either to the subset (fixed or variable tuple size) or permutation space model. State which one you are using.

   (b)

   [2] List all members of your solution space for a graph with 3 vertices.

   (c)

   [2] Draw a tree organization for your space. Label all nodes and/or branches.

   (d)

   [2] Number the nodes in your tree organization in the order in which they are first reached during a backtracking procedure in which the bounding functions fail to curb any node expansions.

   Solutions