Assignment 3: due 3/29 in class

Reading assignment Chapter 7, 8,9

Problems to be handed in:

  1. Illustrate the operation of PARTITION on the array A=<11, 9, 5, 8, 7, 6, 2, 21, 16, 10>.
  2. Exercise 7.3-2.
  3. Problem 7.1 (a) and (e).
  4. Illustrate the operation of COUNTING-SORT on the array A=<1, 5, 5, 8, 2, 6, 2, 1, 6, 1>.
  5. 8.2-3. page 196.
  6. Show how to sort n integers in the range 0 to n^2 -1 in O(n) time.
  7. Illustrate the operation of BUCKET-SORT on the array A=<.11, .5, .8, .6, .2, .21, .16, .10>.
  8. Write an iterative version of RANDOMIZED-SELECT.
  9. Exercise 9.3-9.

  10. Programming assignment:

    Consider N distinct positive integers a[1],..., a[N], where N<10000000 and each a[i] < 2 32 -1.
    Write a program to find an integer b such that the following sum is minimal:
    |a[1]-b| + |a[2]-b| + ... + |a[N] -b|.

    INPUT:

    The first line contains an integer K. indicating the number of test cases, where K < 10.
    For each test case, the first integer N indicates the number of integers. Then N integers a[1] .... a[N] follow.

    OUTPUT:

    For each test case find the proper b and output the minimal sum mentioned above.

    Sample Input

    2
    2 8 6
    3 1 5 3

    Sample Output

    2
    4