Review Problems for AP CS Test

1. Under what circumstances does a hash (Set, Map, Tree, or any other thing that can be hashed) NOT take O(1) time? Explain.
   A hash can result in collisions if multiple elements map to the same bucket. The bucket would then have to return a structure as opposed to an individual item, and you would then have to process the structure.
   
   
2. If quicksort is applied to a sorted array of n elements, how many comparisons will it need to make? (Try this by hand; if you get stuck, take a look at the JavaSort.exe program by Tony Wang. Use some number of elements that will make the math fairly intuitive.)
   If quicksort is invoked on sorted elements, and the pivot is fixed at the beginning or the end of the array, then the resulting binary chops will be very poor--all the data will be on the same side of the pivot. It is the equivalent of selection sort. All n elements will be the pivot at some point, but each will be selected each time with no log₂n benefit. So instead of getting n elements times log₂n swaps, we would have n elements being compared to O(n) other elements which will be O(n²).
   
   
3. Thinking about problem #2, above, to what other sorting routine did quicksort essentially degenerate? Explain.
   See above.
   
   
4. Suppose 35 million students take a test. You want to find the top 10 scores. Which sorting algorithm would you choose?
   The first 10 iterations of selection sort will give you the top 10 scores. Bubblesort could also be used, but it would do many more swaps than needed.
   
   
5. Now suppose that all you really care about are 10 tests with scores in descending order. Which algorithm would you choose now?
   If we don't need the stop scores, but any 10 scores in order, insertion sort is excellent. It permits us to ignore the overwhelming majority of the data.
   
   
6. Suppose you have a max-heap that is sorted as follows: 12, 11, 10, 9, 7, 6, 5, 4, 3, 2, 1, 0. Now you wish to add 8 to the heap and sort it. What is the the order of growth for producing the freshly sorted heap?
   Since the data are in a heap, compare the 8 with the root value and trickle it down accordingly. Note that it does not matter whether the 8 is next compared with the 11 or the 10. What matters is that it starts the log₂n process of working data down the tree.
   
   
7. For problem 6, suppose the numbers are in an ArrayList and that you are using quicksort. Once again, you want to add the number 8 and sort. What is the order of growth for this process?
   If you have a random or otherwise sensible pivot that breaks the data into significant pieces, then it's O(nlog₂n). A bad pivot will degenerate to selection sort and be O(n²).
   
   
8. Suppose you have the following method:
   

       public static void thing(int[] a) {
           int low = 0;
           int high = a.length - 1;
           
           while (high > low) {
               for (int i = low; i < high; i++) {
                   if (a[i] > a[i+1]) {
                       swap(a, i, i+1);
                   }
               }
               high--;
               for (int i = high; i > low; i--) {
                   if (a[i] < a[i-1]) {
                       swap(a, i, i-1);
                   }
               }
               low++;
           }
       }
       

   If a contains n elements, what is Big-Oh of this sorting algorithm? (Do you know what this algorithm is called?)
   It's O(n²) It's called shaker sort. It basically bubbles right then left then right then left, etc., hence the term "shaker."
   
   
9. Suppose you have the numbers 1..10000 in random order. You insert them into a binary search tree. What is the largest depth possible? The smallest depth? The average depth?
   Largest depth: 10000. Smallest: ceiling(₂10000) = 14. Average: about 22. Pretty amazing, eh?
   
   
10. What is the difference between a complete tree and a full tree?
    A full tree has every level filled with nodes. A complete tree has every level but the last one filled with nodes. (The last one could be filled, but does not have to be. A full tree is always complete. A complete tree is not necessarily full.
    
    
11. Suppose we have the following expression tree:

          *
         / \
        6   -
           / \
          5   2
        

    1. If evaluated as an expression, what would the value of this tree be?
       6 * (5 - 2) = 18
       
       
    2. What would the preorder printing of this tree be? This is called prefix notation and is what is used in Scheme.
       Preorder is node, left, right: * 6 - 5 2.
       
       
    3. What would the inorder printing of this tree be? This is called infix notation and is what we typically use when we write out mathematics.
       6 * 5 - 2. (Note that there are no parentheses--a good inorder printing really ought to have parentheses.)
       
       
    4. What would the postorder printing of this tree be? This is called postorder notation and was used on old HP calculators.
       6 5 2 - *.
       
       
    
    
    
12. Translate the binary number 1011011 into decimal.
    91
    
    
13. Translate the decimal number 177 into binary.
    10110001
    
    
14. Translate the hexadecimal number 0xe5 into binary.
    11100101
    
    
15. Translate the binary number 1011101101 into hexadecimal.
    0x2ed
    
    
16. Translate the IP address 255.255.255.255 into hexadecimal.
    0xffffffff
    
    
17. Consider the following code:

    public class Main {
    
        public static void main(String[] args) {
            System.out.println(mystery(2,12));
        }
        
        public static long mystery(long a, long b) {
            return mysteryHelper(a, b, 1);
        }
        
        public static long mysteryHelper(long a, long b, long n) {
            if (b == 0) {
                return n;
            } else if (isEven(b)) {
                return mysteryHelper(a*a, b/2, n);
            } else {
                return mysteryHelper(a, b-1, a*n);
            }
         }
        
        public static boolean isEven(long b) {
            return (b%2 == 0);
        }
    }
    

    1. What does the function mystery do?
       It is a power function and returns a^b.
       
       
    2. What is the loop invariant for mysteryHelper function?
       n * (a^b).
       
       
18. Which comes first, the casting operator or the dot operator? How can you prove it?
    The first code segment fails. The second works. Dotting is done before casting.

    ArrayList al = new ArrayList();
    al.add(new Integer(10));
    System.out.println((Integer) (al.get(0)).intValue());
    

    ArrayList al = new ArrayList();
    al.add(new Integer(10));
    System.out.println(((Integer) (al.get(0))).intValue());