CMSC 435  Algorithm Analysis & Design

 

Homework # 6

Due November 19

 

  1. Given a set S of unit time tasks,  |S| = n, with a deadline and a penalty for missing the deadline, {(di, pi)}, where di is the deadline for the ith task,   1 £ di  £ n,  and pi 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 = <p1, p2,…, pn> and d = <d1,…, dn>.  (See the job scheduling problem in the Algorithm Design Lab for assistance.)

 

  1. 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

 

  1. 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.

 

  1. Given the recurrence relation:  T(n) = (2/n)åi=1,…n-1T(i) + (n-1), where T(1) = 0,   for the average case in quicksort, write a program to determine the average number of compares for values of n = 16, 64, 256, and 1024.  (Use dynamic programming to relieve the “Alzheimer algorithm” of its memory loss problem.  How small a table will you be able to use?)

 

  1. In class we discussed the 0-1 weighted knapsack problem.  Given a set of n objects, each having an integer size and value, what is the optimal selection of items that maximizes the value contained in the knapsack subject to the constraint that the total size of the objects placed in the knapsack be less than or equal to the capacity of the knapsack.  We examined a greedy approach to this problem, but saw that it did not necessarily produce an optimal solution.  Write a dynamic programming algorithm to find a solution to this problem.  Run this algorithm, along with a greedy algorithm on the following data set and compare the solutions obtained by each.

 

Size of knapsack = 120            Number of items in the set to choose from = 25

 

Set of objects = {(si, vi)}  where si is the size and vi the value of the ith object.

 

{(15,20), (30,25), (5,10), (35,30), (40,25), (17,21), (12,23), (24,16), (9,24), (7,16), (28,31),

  (29,27), (16,28), (3,8), (6,17), (12,15), (5,7), (9,14), (14,29), (20,24), (14,9), (6,10), (2,3),

  (19,24), (20,28)}