Problem Set 6. Posted 3/23. Due on 3/30.

1. Here is a simplified version of the knapsack problem. The input is a knapsack of weight W and n items of weights x1, x2, x3,..., xn. The problem asks that we find a subset of items of total weight exactly W or report that such as subset does not exist. You may assume that W and the weights of the items are all non-negative integers.

   For example, suppose that we are given a knapsack of weight 20 and five items of weights 11, 8, 7, 6, and 5. Then, a solution to the problem would be items 2, 3, and 5, whose total weight 8 + 7 + 5 = 20.

   Implement a solution to the knapsack problem using the "search with backtracking" strategy described in class for depth-first search and the n-Queens problem. Use the following function header:

   	int[] knapSack(int[] items, int target)
   

   The int array items contains the weights of the given items. The int parameter target gives the target weight permitted in the knapsack. The function should return an array of item weights that fit exactly in the given knapsack.

   It is quite possible that you may need additional parameters just to control the recursion. In that case, use the above function header for a "wrapper" function and define a function called recursiveKnapSack.

2. Here is the code for the quick sort function, discussed in class. The code contains some print statements meant to show you how the array is being sorted. Without running the code, write down the output of these print statements when quick sort is given the following array as input:

   	11  4  8  3  17  1  9  19  20  27  5  7
   

   Note: You will be asked to solve this problem on the quiz with some other sequence of numbers as input. So it is worth your time to try and answer this question without running the code.

3. In this problem you are asked to perform experiments to compare the performance of bubbleSort, mergeSort, quickSort and randomizedQuickSort. The difference between quickSort and randomizedQuickSort is that quickSort uses the function partition, whereas randomizedQuickSort uses the function randomizedPartition. To perform the experiments, generate for each value of n, 10 integer arrays of size n, run all four sorting algorithms on each of the 10 arrays, time each run, and report the mean running time (taken over the 10 runs) for each sorting algorithm. Do this for the following values of n: 1000, 2000, 3000, ..., 10,000 and make a plot of running times, one for each of the four sorting algorithms. Write a few paragraphs summarizing your observations, based on these plots. Consider the following questions:
   • Which implementation is faster?
   • How does the running time seem to grow, as a function of n, for each implementation?

   Repeat the above experiments for input generated as described below. Generate each size-n integer array in the following manner. Start by assigning the integer i to slot i in the array. Thus the array starts off with entries 0, 1, 2, ..., n-1 in that order. Then do the following 20 times: pick a pair of indices i and j, at random, in the range [0, n-1], and swap the elements in slots i and j. After this is done, we may no longer have a sorted array, but the array will still be "almost sorted''. Our expectation for "almost sorted'' inputs is that quickSort should run in O(n^2) and will clearly be slower than randomizedQuickSort, which runs in O(n log(n)) time, on an average, independent of the type of input.