Exercise 3

  1. Reading: Search the net for material on Java performance. What is garbage collection and how does it impact performance? What are other ways to tune a Java application?

  2. Pen-and-paper exercises:
    1. Write down at least three ways of improving the performance of a Java application that you learned from the reading above.
    2. Consider Binary Search in a sorted array:
      • 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.
      • Intuitively, because BinarySearch cuts the "search-work" in half each time, it takes O(log(n)). Read through a more careful analysis (books, websites) to see why.
      • It is possible to write a simple recursive program that finds successive sub-ranges to search from.
      Suppose instead, we consider "ternary search" in which the array is divided into three thirds of roughly equal size. Provide pseudocode for ternary search and analyze the running time of the algorithm in terms of n (the array size). Show where the analysis would differ from that of binary search.
    3. Analyze the following code and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis. 
          for (i=1; i <= n; i++) {
      k = 1;
      for (j=1; j <= i; j++) {
        k = 2*k;
      }
      j = k*k;
      while (j > 1) {
        j = j / 2;
      }
    }
    4. Duplicate removal, part 3. In this problem we'll return to the problem of duplicate removal.
      • Suppose we are given a sorted array of integers with possible duplicates. Show how duplicates can be removed from the array in O(n) time using no additional space except for some additional variables. Provide both detailed pseudocode and an example showing why your pseudocode works. The goal, recall, is to rearrange the elements in the array so that the unique elements are up front. You will then have an index indicating the position of last element that's not a duplicate. Thus, if given the sorted array [2,3,3,3,4,4], what is returned is [2,3,4,0,0,0], along with the index 2.
      • If the array is not sorted, is it possible to remove duplicates in O(n)? Explain why or why not.

    5. Write recursive pseudocode (both high-level and detailed) for an algorithm to count the number of leaf nodes in a binary tree. What is the big-O running time of the algorithm? Consider both cases: when the tree is balanced and when it's highly unbalanced.

    6. Module exercise 4.5

    7. Module exercise 4.8

    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  3. Programming. This week we'll take a break from programming.

Submission: