Exercise 2

  1. Pen-and-paper exercises (in PDF):
    1. Give examples of two functions f and g such that neither f(n) = O(g(n)) nor g(n) = O(f(n)).
    2. Analyze the following pseudocode and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis. 
      
    k = n
    while k > 0
        for j=1 to n2
            sum += data[j];
        k = k / 2
    3. Let W(n) be the "work done" (time taken) by MergeSort on an array of size n. Write the recurrence relation for W(n) and work out the solution.
    4. Submit your pseudocode (at a reasonably detailed level) for the non-recursive version of quicksort.
    5. Review binary trees from from previous courses or from sources online. Insert the following elements "A C B G H D E F" into a standard binary search tree and draw the tree at each step.
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. A Selection Algorithm is an algorithm that, given an integer K and a set of unsorted data (say, integers), will find the K smallest elements in that set. For example, suppose K=3 and the (unsorted) data is: 
      85 21 5 33 2 19 72
    Then, the output, in sorted order, is: 
    2 5 19
    You are to implement three algorithms for the selection problem, two of which are quite straightforward. Each of these must implement the SelectionAlgorithm interface. It will help to examine this interface before continuing.
    1. The InsertionSelect algorithm scans the data to find the smallest integer and puts that in the first position of the return array. Then, it scans the data to find the second-smallest integer and puts that in the second position of the return array. And so on. This needs to be repeated K times.
    2. The SortSelect algorithm sorts the data array and simply copies over the first K elements from the sorted array into the return array. Java provides a sorting algorithm (see java.util.Arrays) that makes it a one-line method call to sort an array.
    3. You will notice that the SortSelect algorithm runs much faster. The most interesting question is whether it's possible to beat this algorithm. Algorithm PartitionSelect will use the ideas of quicksort in an attempt to outperform SortSelect. Here are the key ideas: write a method called recursiveSelect with the following signature: 
        void recursiveSelect (int[] data, int K, int left, int right)
      Like the recursive part of quicksort, the input is the data and a range. Here, the number K is also part of the input. Now, use the quicksort partitioning algorithm to find the partition position. If the partition position is K, then we're done, because all elements to the left of that position are less than the element at the partition position. If the partition position is larger than K, then we recurse on the left partition; otherwise, we recurse on the right partition. Finally, when the recursion is completed, the array will have all elements less than the K-th element in the first K-1 places. Then, we will need to create and sort the result array (because the recursive partitioning does not sort).
    What to deliver for this assignment:
    • Your implementations of the three algorithms. The first two should take very little time (each like an in-class exercise); the third is a little more challenging and will take longer.
    • For each of your implementations, you only need to get it working for integers. Simply provide an empty implementation for the method that uses Comparable's.
    • Apply PartitionSelect to the 7-element example (with K=3) above on paper to show that you understand how it works. Do this before you implement your algorithm.
    • For the partitioning part of PartitionSelect, use the leftmost element as the partitioning element.
    • Implement some test code of your own to make sure that your algorithms are working.
    • Use this properties file for testing your algorithm with the algtest environment. Note: you can set numAlgorithms=1 to test InsertionSelect by itself numAlgorithms=2 to test both InsertionSelect and SortSelect.
    • Test the performance of your implementations by setting display=true and testPerformance=true in the properties file. Include a screenshot of the graph produced.
    • What is the running time (in order notation) of each algorithm? Explain your answer.

Submission: