Homework 2

 

  1. Pen-and-paper (PDF) exercises:
    1. Consider the functions f(n) = n2 and g(n) = n(-2)n. Argue that neither f(n) = O(g(n)) nor g(n) = O(f(n)) can hold.
    2. Analyze the following code and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis. 
      
    int k = n;
    while (k > 0) {
      for (int j=0; j < k*k; j++)
        sum += data[j];
      k = k / 4;
    }
    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. Review binary trees from any source (such as this CS-1112 material). 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.
    5. Exercise 2.2 in Module 2.
    6. Exercise 2.7 in Module 2.
    7. Exercise 2.9 in Module 2.
    8. Array section problem, part 1. In this problem, we are given two arrays A and B. An array section is a contiguous part of an array, as in the part of the array between (and including) indices 1 and 3: 
      
    3 2 6 7 8 9 2 1 4 3
      The goal is to find the largest section of array A that is also a section of B. For example consider: 
      
    A:   3 2 6 7 8 9 2 1 4 3
    B:   0 8 9 2 1 3 3 4 3 2 6 7 6 6
      Here, the largest section of A that occurs as a section in B is the section 8 9 2 1. Now consider the method definition 
      
    Method: findSection (A, i, j, B)
    Input: arrays A and B, indices i and j

    (... fill in pseudocode here ...)
    
    Output: true or false, depending on whether the section 
            i through j (inclusive) in A is a section in B
      Write out the pseudocode for this method, assuming the most straightforward way of solving the problem. Then, write the pseudocode for 
      
    Algorithm: findLargestSection (A, B)
    Input: arrays A and B

    (... fill in pseudocode here ...)
    
    Output: return the i,j range of the largest section of A
            that is also a section in B, and where it occurs in B.
      This algorithm should use the method findSection(). Analyze the overall time taken by findLargestSection(), assuming both arrays are of similar size (n elements).
    9. Who devised Quicksort? Write down three things you learned reading his biography.
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. Implement Binary Search for Comparable objects:
    • What is BinarySearch?
      • Inserted items are kept in sorted order in an array.
      • To search for an element, a straightforward scan would require O(n) time.
      • In BinarySearch, you compare the search-item with the middle element. If the search-item is smaller, then you know that it cannot lie to the right of the middle-element (because those elements are larger since the array is sorted). So, now you restrict your search to half the array.
      • Because BinarySearch cuts the "search-work" in half each time, it takes O(log(n)).
      • It is possible to write a simple recursive program that finds successive sub-ranges to search from.
    • You will need to have your algorithm implement the OrderedSearchAlgorithm interface. which itself extends the SearchAlgorithm interface.
    • For this interface, you do not need to implement the delete, successor and predecessor operations (Provide empty implementations).
    • Observe that the insert returns a value. Most of the time, this will be null. We are following Java's convention here: if you insert a value that's already there, then the new one replaces the existing one. The existing one is returned. Thus, if every value inserted was never previously inserted, the return value will always be null.
    • What are "keys" and "values"? From a data structure point of view, you can think this way:
      • All searching is done based on keys.
      • Whenever a user inserts a key, the user also inserts a "value" that is associated with the key.
      • Whenever a search on a key is performed, the associated value is also returned.
      • To return both a key and a value together, a object called a ComparableKeyValuePair is used.
      • Keys are themselves objects that can compare themselves. To make this possible, the test environment uses key objects that contain a compareTo method. Since Java already provides an interface with this method, we use that interface, the Comparable interface in java.lang.
      • Thus, to summarize, you should be thinking like this: whenever the test environment wants to insert something, "it'll give me a key and a value, which I'll put together into an instance of a ComparableKeyValuePair. Then, when the test environment wants me to search for something, it'll give me a key, for which I'll return the instance of ComparableKeyValuePair containing the key. If the key was indeed inserted earlier, then I surely have such an instance in my data structure. If not, then I return null. Lastly, I know how to compare two keys because I know both have a compareTo() method since keys implement the java.lang.Comparable interface."
      • Thus, for a binary search, you'll need to create and use an array of ComparableKeyValuePair objects.
    • The methods you need to concentrate on are: initialize(), getCurrentSize(), insert(), search(), minimum(), maximum(). For all others, use an empty implementation.
    • To use the testing environment, you can use the hw2.props properties file.
    • Note: your algorithm will be called with both insertions and searches.
    • Also implement simple SequentialSearch: put the objects in an array (unsorted) and, when given an element to search, scan sequentially. Make your SequentialSearch implement the OrderedSearchAlgorithm interface.
    • Plot a graph of BinarySearch vs. SequentialSearch by setting testPerformance=true in the props file.
    • Note: you will need to name your classes: BinarySearch, SequentialSearch.
    • You do not have to implement the following: deletion, predecessor and successor: provide an empty implementation (always return null).

Submission: