Data Structures & Algorithms

Exam 3, Sample 2

2 Hours

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. [10] You are to write a method boolean twoColor(int i, int [] label). The invocation g.twoColor(theI, theLabel) labels all of the vertices in the component that contains vertex theI. Some of these vertices are labeled 1, and the remaining vertices of the component are labeled 2. The labeling is done in such a way that for every edge (i,j) in g, vertices i and j have different labels. You may assume that, initially, theLabel[j] = 0 for all vertices j that are in the same component as vertex i. The method returns false iff it is not possible to do the labeling as stated. An example component with theI = 11 and labeled as described above is shown below (only vertices in the component are shown, the remaining vertices of the graph are omitted).

   (a)

   [8] Write Java code for the method twoColor. Note that the labeling may be done using either a depth first or breadth first search beginning at vertex theI. If you wish to use recursion, you will need to write an additional private method. If you need to use a stack or a queue, use either ArrayStack or ArrayQueue. Use iterators to move around the graph; use the method vertex() to determine the number of vertices in g.

   (b)

   [2] What is the complexity of your labeling method as a function of the number of vertices and edges in the component being labeled? Provide this complexity under the assumption that adjacency lists are used. Explain your analysis (a few lines only).

   
   
2. [10] You are given n jobs. Each job has a length, release time, and deadline associated with it. All job lengths and deadlines are > 0, and all release times are >= 0. To successfully complete a job, the processing of this job must begin at or after its release time, the processing must complete by its deadline, and the job must be processed for an amount of time that equals its length. Only one processor is available to process jobs. Therefore, at any time at most one job may be worked on. Suppose there is a job whose length is 6, release time is 3, and deadline is 14. The processing of this job may commence at any time t, t >= 3. In a successful processing, the processing must finish by time 14 and the processing duration must be 6. So, if we start processing this job at time t, 3 <= t <= 8, we will finish at t + 6 <= 14 and have a successful processing of the job. While this job is being worked on (i.e., from time t to t + 6), we cannot work on any other job; the processing of another job may commence as early as t + 6.

   (a)

   [7] Give a greedy algorithm that attempts to select the maximum number of jobs that may be successfully processed by a single processor. Pseudocode (a precise statement of the algorithm using a combination of English and programming language constructs) will suffice.

   (b)

   [3] Does your algorithm guarantee to select the maximum number of jobs that can be successfully processed by a single processor? Prove your answer.

   
   
3. [18] A machine has n components. For each component, there are two suppliers. The weight of component i from supplier j is W(i,j), and its cost is C(i,j), 1 <= j <= 2. You may assume that W(i,1) > W(i,2) and C(i,1) < C(i,2) for all i.
   
   Assume that the Cs and c, are positive integers. The cost of the machine is the sum of the component costs, and its weight is the sum of the component weights.
   
   We wish to use dynamic programming to determine the supplier for each component so as to build the lightest machine with cost no more than c.

   (a)

   [5] Let w(i,j) be the weight of the lightest machine composed of components i through n that costs no more than j. Obtain the dynamic programming recurrence for w(i,j), 1 <= i <= n and 0 <= j <= c.

   (b)

   [10] Obtain an O(cn) time algorithm to compute w(i,j), 1 <= i <= n, 0 <= j <= c. Pseudocode will suffice.

   (c)

   [3] Describe how you can use the w(i,j) values computed in (b) to determine the suppliers for each component so that we get the lightest machine whose cost is at most c. (I.e., describe how the traceback works.)

   

4. [8] Let G be an undirected graph. We are interested in determining the largest subset S of vertices of G so that G has no edge that connects two vertices of S (i.e., if u and v are in S, then (u,v) is not an edge of G).

   (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