CMSC 435 Algorithm Analysis & Design

Homework # 6

Due October 8 (#1, 4, 5) for discussion, due October 15 (#2, 3) for submission

Given a set S of unit time tasks, |S| = n, with a deadline and a penalty for missing the deadline, {(d_i, p_i)}, where d_i is the deadline for the i^th task, 1 £ d_i £ n, and p_i is the penalty incurred for missing this deadline. Write a greedy algorithm for assigning each of the n tasks to n time slots so that the total penalty incurred is a minimum. Consider the input to the algorithm to be p = <p₁, p₂,…, p_n> and d = <d₁,…, d_n>. (See the job scheduling problem in the Algorithm Design Lab for assistance.)

(Problems 2 - 3 are to be implemented and submitted on the due date. Submit,

in a folder, a hard copy of the code and output)

Construct and implement efficient algorithms (with the same compiler) of Prim’s and Kruskal’s algorithms to find the minimum spanning tree (MST) for the graph included with this assignment. Compare the run-time for each program. Build counters into your program so that you can record the number of times that the costliest operations are executed for each of these examples. Use these figures to discuss the relative cost of the two algorithms. Do these costs compare with the values you expect from your analysis of the runtime of each algorithm? Your output should consist of a list of edges in each of the trees, and you may also choose to color these edges on a copy of the graph that you have received. (You should use the heap that you constructed in Advanced Data Structures last semester – or get documentation for building such a heap now.) G = {V,E} and |V| = 25, |E| = 32

As you know, Prim’s algorithm is very similar to Dijkstra’s single source – shortest path algorithm. Can you modify your implementation of Prim’s algorithm (by changing only one or two lines of code) to run Dijkstra’s algorithm on the same input data.