1. Minimum spanning trees. (20 points)

For this problem, use the graph below.

(a) What order does Kruskal’s algorithm add edges to the minimal spanning tree (include only those edges that are in the minimum spanning tree)? Denote the edges by the two nodes they attach. So, the edge with weight 9 attaching A to C is “AC”. Always put the letters in alphabetical order when denoting an edge.

(b) What order does Prim’s algorithm add edges to the minimum spanning tree (again include only edges in the MST)? Start the algorithm at node A.

(c) Now assume that every edge is directed from the node lower in the alphabet to the node higher in the alphabet. (Edge AC leaves A and enters C.) Use the minimum cost arborescence algorithm to find the minimum cost arborescence rooted at A. List the edges in the result. Show your work.

2. Divide-and-conquer / Algorithm analysis (20 points)

Consider recursive divide-and-conquer algorithms with the following descriptions. For each, determine the running time in Big-Theta notation. If necessary, you may assume that the regularity condition holds. You do not need to prove your result. You may use the Master Theorem.

(a)
Performs 5 recursive calls on
problems half the size of the input and performs Q(n^{2})
work per recursive call.

(b)
Performs 2 recursive calls on
problems a quarter the size of the input and performs Q(n^{ }log n) work per call.

(c)
Performs 8 recursive calls on
problems half the size of the input and performs Q(n^{3})
work per recursive call.

3. Divide-and-conquer (20 points)

Consider the algorithm to find the closest pair of
points in the plane. Let’s say you wanted to generalize the algorithm to find
the **two** closest pairs of points in the plane given a set of (unsorted)
points {p_{1}, … p_{n}}. Give an algorithm for finding the two
distances for this pair. In the step to conquer the two subproblems, you must
explain why your algorithm is guaranteed to find the correct result. You do not
need to specify the best possible algorithm, but your overall algorithm must
run in O(n log n) time. (Full pseudocode is not necessary, but your explanation
must describe how/why the algorithm works.)

4. Dynamic programming (20 points)

Your
company is able to take on two types of jobs – long jobs that require two days
and short jobs that require one day. You are given a schedule for the upcoming *d*
days that contains one long job and one short job that you may perform each
day. If you perform the long job, you are unable to take a new job the next
day. If you take a short job, you are able to take a job the next day. (You
can’t take a long job on the last day of the schedule.) Each job has a value,
the value of the long job on day *i* is *l _{i}* and the value
of the short job on day

(a)
Give a recurrence relation that
expresses the optimal value of the jobs completed through day *i*. (For
example, see Theorem 6.11 on page 272 for a recurrence relation for the
knapsack problem.)

(b) Give an efficient algorithm for computing the maximum value that can be achieved.

(c) What is the running time of your algorithm in Big-Theta notation?

5. Dynamic programming (20 points)

Recall the Cashier’s algorithm for coin changing that
we saw in the slides for Chapter 4. A greedy algorithm works perfectly when the
coin denominations are multiples of each other. However, this is not the case
with arbitrary coin values. Let’s say that you have values v_{1} < v_{2}
< v_{3} < … < v_{n}. Assume that v_{1}=1 (so
that you will always be able to make exact change). Find an efficient algorithm
to find the exact change for a given value C using the minimum number of coins.
Your algorithm may be pseudo-polynomial.

(a) Give a recurrence relation that captures the structure of the problem.

(b) Give an efficient algorithm for computing the solution.

(c) What is the running time of your algorithm in Big-Theta notation?

__ __

__ __

Rules:

· Working in pairs is acceptable, but both students must be present when all problems are solved.

·
It is **not** acceptable to
search the web for solutions to the problems.

· Solutions are to be turned in online. It is preferable that the solutions are typed (for example, in Word). However, clearly legible written solutions may be scanned.