Assignment 7

Algorithms and Complexity

[ I made a few changes to this assignment, which are in red below. ]

Related Reading:

Chapters 1, 11, 15, 35, and 40 in the Omnibus, Chapter 7 of SOE,
and class notes on lower bounds and upper bounds.

Due: Midnight Sunday March 30, 2008

Remember that a lower bound of L steps for a problem P says that there is no algorithm for solving P in less than L steps, and an upper bound of U steps says that there is at least one algorithm for solving P in U steps. Generally we strive to "lower the upper bound" (meaning that we have better and better algorithms), and "raise the lower bound" (meaning that we have proven that a larger and larger class of solutions cannot exist).

For each of the following problems, give both an upper and a lower bound, and informally justify your answers. The narrower your "algorithmic gap" (the difference between the upper and lower bounds), the better your grade!

a) Find both the minimum element and the maximum element in a list of n numbers.

b) Suppose that I have a sequence of n integers, say [2,5,3,6,9,7,8,2,5], and I want to know if another, shorter sequence of m integers, say [6,9,7] can be found in the longer sequence. (In this example the answer is "yes".) Give your answer in terms of n and m.

c) Given integers n and x, compute the value of x raised to the nth power. Give your answer in terms of n.

Write Haskell programs to implement the "mergesort" and "heapsort" algorithms described in Chapter 40 of the Omnibus. Test your program on some suitable inputs. What are the worst-case and best-case time complexities (counting the number of comparisons) for each of these algorithms? What do you think the average case might be? Informally justify your answers. For extra credit: write the recurrence equations counting the number of comparisons, and for extra extra credit, solve the recurrences.

Hints on the Haskell implementations:

For heapsort, I suggest defining two functions:

initHeap :: Ord a => [a] -> Heap a
This function takes the initial unsorted list and generates a balanced heap. In my implementation I found it useful to define a function insert :: Ord a => a -> Heap a -> Heap a that inserts an element into a heap. Then initHeap can be defined by starting with an Empty heap and inserting the elements one at a time. The trick, however, is making the heap balanced! To do this, my insert function alternates between inserting the elements into the left sub-heap and the right sub-heap.

sortHeap :: Ord a => Heap a -> [a]
This function takes the heap generated from initHeap and creates a sorted list as output. In my implementation I found it useful to define a function promote :: Heap a -> Heap a -> Heap a that takes two heaps and combines them into one by "promoting" the larger value up, which recursively involves promoting elements from the lower levels.

A function heapSort can then be defined trivially as the composition of the above two functions.

For mergesort, the only difficulty is figuring out how to "split" the list into two halves. Using the splitAt function in the Standard Prelude, I just do this:
let (ys, zs) = splitAt (length xs `quot` 2) xs
in ...

Finally, to test your code, I suggest creating a random list of, say, 1000 elements. Here's a simple way to do that. First, import Haskell's Random library, like this:

> module Assignment7 where
> import Random
...

Then, at the place in your module where you need the random numbers, do this:

> seed :: Int
> seed = 42

> rands :: [Int]
> rands = take 1000 (randomRs (1,1000) (mkStdGen seed))

If you want the list to be different, just change the values of seed.

Solution.