CMSC 415  Algorithm Analysis & Design

Homework # 9

Due  November 9

Read Kleinberg & Tardos, Chapter 6  Dynamic Programming

1.      Amend the quicksort algorithm to find the k^th smallest element in an unsorted list of Comparables.

2.      Modify the exact-fit knapsack algorithm discussed in class to select a subset of items from the input that will put the maximum value in the knapsack without exceeding its capacity.  The input to P(n,K) will be:                             

K = size of the knapsack

n = cardinality of the set of distinct elements from which a solution is found

<s₁,…,s_n> = a list of sizes for each of the n elements.

<v₁,…,v_n> = the value of each item in the list.

Suppose each item i of size s_i has value v_i, modify the knapsack

table construction algorithm to ascertain the solution that places the maximum value in the

knapsack while not exceeding its size.

3.      Given the dimension vector p = <5, 10, 3, 12, 5, 50, 6> for a chain of 6 matrices, construct a table and simulate the execution of the dynamic programming matrix-chain multiplication algorithm by calculating and filling in by hand the respective table entries.

4.      Based upon the observations you have made from completing the Sorting Laboratory Worksheet, choose or design your own sorting algorithm that will perform most efficiently (require the least amount of time) when running on a suite of test data of various kinds of distributions (unique random, highly degenerate, almost sorted, reverse ordered) and various sample sizes.  The sorting algorithm may be one of the algorithms tested in the Sorting Lab, one that was not tested, such as Shellsort, or a hybrid algorithm of your own construction.  Your sorting algorithm must be written as a static java method with the interface described below.  Your algorithm will be imported into a test program that first tests that your algorithm correctly sorts a few initial data sets.  Then your algorithm will be used to sort the suite of data sets in a timed trial.  The algorithm with the best time will be awarded 10 bonus points.  The second place finisher will receive 7 points and the third place finisher will receive 5 points.  All other programs that run correctly will receive 3 bonus points each.  Your algorithm will be sorting integer data sets.  You may add other methods to class Sorts (such as a partition if you are using quickSort), but remember to make all methods and any added data members static in scope.  The test program will be importing Sorts and running superSort, so your program must conform to this interface.

                public class Sorts {

                 public static void superSort(int [ ] A, int low, int high) {//your code

                 }

            }

5.      Given a matrix chain A₁ …A_n with the dimension of each of the matrices given by the vector p = <12,21,65,18,24,93,121,16,41,31,47,5,47,29,76,18,72,15>. (n=17)  Write and run both the dynamic programming and memoized versions of this algorithm to determine the minimum number of multiplications that are needed (use type longint) and the factorization that produces this best case number of multiplications.  Run each of the two programs over an appropriately large number of times (put each in a loop to run repeatedly x times) and obtain the times at the beginning and end of the run.  Use these times to determine the comparative runtimes of he two algorithms.

6.      Given a list of states with their (2004) electoral votes.  Can you determine a grouping that will produce a tie vote in a two-candidate election?  Write a program to produce such a list or determine that none exists.  (Is this problem like one you already know how to solve?) 

Alabama                       9          Alaska                          3          Arizona                      10          Arkansas                      6

California                    55          Colorado                      9          Connecticut                  7          Delaware                      3

Florida                       27          Georgia                      15          Hawaii                          4          Idaho                           4

Illinois                         21          Indiana                       11          Iowa                            7          Kansas                         6

Kentucky                     8          Louisiana                      9          Maine                           4          Maryland                    10

Massachusetts            12          Michigan                    17          Minnesota                  10          Mississippi                    6

Missouri                     11          Montana                       3          Nebraska                     5          Nevada                        5

New Hampshire           4          New Jersey                15          New Mexico                5          New York                  31

North Carolina           15          North Dakota               3          Ohio                           20          Oklahoma                    7

Oregon                         7          Pennsylvania               21          Rhode Island                4          South Carolina              8

South Dakota               3          Tennessee                  11          Texas                         34          Utah                             5

Vermont                       3          Virginia                       13          Washington               11          Washington, D.C.            3

West Virginia                5          Wisconsin                   10          Wyoming                      3

Problems 4, 5, and 6 are programming problems that are to be submitted (copy of the code and output) in a folder on the assignment due date. For problem 4 you will also submit a CD containing the java class Sorts described above.  The other problems will be discussed in class and could appear on a subsequent quiz.