Exam 2 Topics and Practice Problems
CSSE 221 – Fundamentals of Software Development Honors
Fall 2008–2009

Exam format

• The exam is closed-book, closed-notes, except that you may bring a 3x5 index card with whatever you want on it (handwritten, typed, xeroxed, whatever, on both sides).
• The exam is designed to take less than 1 hour, although you may start as much an hour early and stay as much as an hour late.
• The exam is paper-and-pencil; no computer is needed or allowed.
• This document lists at least 95%, and perhaps 100%, of the topics on this exam.
• The points listed for each item indicate approximately how many points of the exam (out of 100 points) will be devoted to that topic.
  • However, there are 130 points in the problems below -- problems totaling approximately 30 points will not show up on the exam at all.

Exam topics and Practice problems

Big-Oh

1. [5 points] The definition of big-Oh. Be able to repeat the definition, substituting particulars for f and g as required. Sample problem:

   1. According to the definition of big-Oh, what does it mean when you say The space required by MergeSort to sort an array of length p is O(p)?

2. [5 points] Determining the big-Oh class for a given function, by using shortcut rules. Sample problems:

   1. Fill in the blank in the most appropriate way: 7n^1.5 + 25n² log n + 1.1ⁿ + 703 is O(____________).
   2. Fill in the blank in the most appropriate way: 7n^1.5 + 25n² + 37n log n + 703 is O(____________).

Data structures for implementing Collections interfaces

3. [10 points] Implementing Collections interfaces: strengths and weaknesses of various data structures. Sample problems:

   1. We discussed four primary data structures for implementing Java Collections Framework interfaces: resizable array, linked list, tree, and hash table. For each of these, state its main advantage(s) and its main disadvantage(s).
   2. Explain how to use a hash table to implement the Map interface.
   3. Explain how to use a binary search tree to implement the Map interface.
   4. Suppose you want to implement the Map interface. Two of its implementations are TreeMap and HashMap. Under what circumstances is TreeMap the better choice? Why? Under what circumstances is HashMap the better choice? Why?
   5. Which of the above four data structures (resizable array, linked list, tree, and hash table) would be the best choice for implementing the SortedSet interface? Why?
   6. What is the main advantage of a contiguous implementation of a List over a non-contiguous implementation? What is the main advantage of a non-contiguous implementation of a List over a contiguous implementation?

4. [10 points] Resizable arrays: Determining the big-Oh class for the run-time of a given operation on a given data structure. Sample problems [Be able to explain your answers to any of these sample problems]:

   If resizable array X has m elements:

   1. What is the run-time of adding an element:
      • to the beginning of X?
      • to the middle of X?
      • to the end of X? (State any assumptions you need here.)
      • to the 5^th spot in X?
      • to the 5^th spot from the end of X? (State any assumptions you need here.)
   2. What is the worst-case run-time of finding in X an element whose key is K:
      • if X is sorted?
      • if X is NOT sorted?
   3. What is the best-case run-time of finding in X an element whose key is K:
      • if X is sorted?
      • if X is NOT sorted?
   4. What is the run-time of traversing (i.e., iterating through) X?

5. [10 points] Linked lists: Determining the big-Oh class for the run-time of a given operation on a given data structure. Sample problems [Be able to explain your answers to any of these sample problems]:

   If linked list X has m elements:

   1. What is the run-time of adding an element:
      • to the beginning of X?
      • to the middle of X?
      • to the end of X? (State any assumptions you need here.)
      • to the 5^th spot in X?
      • to the 5^th spot from the end of X? (State any assumptions you need here.)
      • to the spot to which your iterator is pointing?
   2. What is the worst-case run-time of finding in X an element whose key is K:
      • if X is sorted?
      • if X is NOT sorted?
   3. What is the best-case run-time of finding in X an element whose key is K:
      • if X is sorted?
      • if X is NOT sorted?
   4. What is the run-time of traversing (i.e., iterating through) X?

6. [10 points] Trees: Determining the big-Oh class for the run-time of a given operation on a given data structure. Sample problems [Be able to explain your answers to any of these sample problems]:

   If binary tree X has m elements:

   1. What is the run-time of adding an element:
      • to the root of X?
      • to a leaf of X, if X is balanced?
      • to a leaf of X, if X is completely UN-balanaced?
   2. What is the worst-case run-time of finding in X an element whose key is K:
      • if X is a balanced, binary search tree (i.e., is sorted)?
      • if X is NOT a search tree (i.e., is NOT sorted)?
   3. What is the best-case run-time of finding in X an element whose key is K:
      • if X is a balanced, binary search tree (i.e., is sorted)?
      • if X is NOT a search tree (i.e., is NOT sorted)?
   4. What is the run-time of traversing (i.e., iterating through) X?
   5. What is the run-time of traversing (i.e., iterating through) a balanced binary tree if its DEPTH is n?

7. [10 points] Hash tables: Determining the big-Oh class for the run-time of a given operation on a given data structure. Sample problems [Be able to explain your answers to any of these sample problems]:

   If hash table X has m elements:

   1. What is the run-time of (state any assumptions that you need for each of your answers):
      • finding in X the data associated with a key K?
      • inserting new data for key K?
      • adding a new key/data pair?

Recursion

8. [5 points] Recursion: definition. Sample problem:

   1. What is the definition of a recursive method?

9. [10 points] Recursion: advantages and disadvantages. Sample problems:

   1. What are the main advantages of implementing an algorithm recursively? The main disadvantages?
   2. List two techniques applicable to recursive methods that address the disadvantages of recursive implementations.
   3. Explain what a memory table (aka memory function) is, how it is used, and why it is used.
   4. Explain what tail recursion is and why it is used. Also give an example of a tail recursive method.

10. [10 points] Writing recursive methods for recursive definitions. Sample problems:

    1. The nth Padovan number P(n) is given by the following definition:

           P(0) = P(1) = P(2) = 1
           P(n) = P(n-2) + P(n-3) for n > 2
       

       Write a recursive method that returns the nth Padovan number.
    2. The Ackermann function A is given by the following definition:

           A(0, n) = n + 1
           A(m, 0) = A(m-1, 1) if m > 0
           A(m, n) = A(m-1, A(m, n-1)) if m > 0 and n > 0
       

       Write a recursive method that computes Ackermann(m, n) for any positive integers m and n.

11. [10 points] Writing recursive methods for recursive data structures. Sample problems:

    1. Sample problem: What is a recursive data structure? Give an example of a recursive data structure.
    2. Sample problem: A linked list must contain a recursive structure. Suppose that recursive structure is called Node. What are the fields (types and meaningful names) of that recursive structure?
    3. Sample problem: Consider a linked list whose recursive structure is as follows:

           class Node {
               E element;
               Node next;
           }
       

       Write a recursive method add(E e) in the Node class that adds the given element to the end of the linked list. Note that this method is a member of the Node class; you do not need to deal with an empty linked list in this problem.
    4. Sample problem: Consider a linked list whose recursive structure is as above. Write a recursive method get(int n) in the Node class that returns the element in the n^th node from the current node in the linked list. Note that this method is a member of the Node class; also, you may assume that n is not greater than the length of the remaining list.
    5. The following defines a ternary tree (i.e., each non-leaf has 3 children):

           class TernaryTreeNode {
               E data;
               TernaryTreeNode left;
               TernaryTreeNode middle;
               TernaryTreeNode right;
           }
       

       Write a recursive method in the TernaryTreeNode class that prints the data on the rightmost branch (root to leaf) of the tree, with the root first and the leaf last.
    6. Continuing the previous problem, write a recursive method in the TernaryTreeNode class that prints the data on the rightmost branch (root to leaf) of the tree (as in the previous problem), but now with the leaf first and the root last.
    7. Continuing the previous problems, write a recursive method in the TernaryTreeNode class that returns the number of nodes in the tree whose value for E equals null.

12. [10 points] Writing recursive methods for recursive algorithms. Sample problems:

    1. Write a recursive method that, given a sorted array X of integers and an integer K, returns the index of the array where K appears (or -1 if K does not appear in the array). (You may use a helper method if you wish. There is more than one correct answer to this problem.)
    2. Write the (recursive) algorithm for MergeSort, GIVEN the merge method. Write in English, not in Java, and do NOT write merge; just write MergeSort.

Searching and Sorting

13. [10 points] Searching. Sample problems:

    1. State the algorithm for sequential search for key K in an array X of integers.
    2. State the algorithm for binary search for key K in a sorted array X of integers.
    3. State the algorithm and relevant data structures for binary search for key K in a binary search tree X whose keys are integers.
    4. When an array is sorted, which is a better choice: binary search or sequential search?
    5. When an array is NOT sorted, which is a better choice: binary search or sequential search?
    6. What is the worst-case run-time for finding a key K using sequential search on an array X of length n? Best-case run time? Average-case run-time? [Be able to explain your answers.]
    7. What is the worst-case run-time for finding a key K using binary search on a sorted array X of length n? Best-case run time? Average-case run-time? [Be able to explain your answers.]
    8. What is the worst-case run-time for finding a key K using binary search on a balanced binary search tree with n nodes? Best-case run time? Average-case run-time? [Be able to explain your answers.]
    9. What is the worst-case run-time for adding a key K and its associated data in a balanced binary search tree with n nodes (where you need NOT keep the tree balanced)? Best-case run time? Average-case run-time? [Be able to explain your answers.]
    10. What is the advantage of doing binary search on a binary search tree instead of on a sorted array? What is the disadvantage?

14. [10 points] Sorting. Sample problems:

    1. When we talk about the "best-case run-time" for a sorting algorithm, what do we mean? What do we mean by the "average-case run-time"?
    2. Here is a description of how SelectionSort operates on an array X on length N:

           1. Traverse X to find the smallest element in X.  Put that smallest element into X[0].
           2. Repeat step 1 to find the 2nd smallest (putting it into X[1]).
           3. Repeat step 1 to find the 3rd smallest (putting it into X[2]).
           4. Etc until all N elements are done.
       

       Be able to explain your answers to the following:
       • What is the worst-case run time of SelectionSort?
       • What is the best-case run time of SelectionSort?
       • What is the average-case run time of SelectionSort?
       • How much extra space (beyond the space for X) does SelectionSort require?
    3. Here is a description of how MergeSort operates on an array X from indices start to end:

           1. If start >= end, stop (the array is sorted in the range from start to end).  Otherwise:
           2. Recursively MergeSort the left half of X (from start to the middle).
              Recursively MergeSort the right half of X (from middle to end).
           3. Merge the two sorted halves [as described in class].
       

       Be able to explain your answers to the following:
       • What is the worst-case run time of MergeSort?
       • What is the best-case run time of MergeSort?
       • What is the average-case run time MergeSort?
       • How much extra space (beyond the space for X) does MergeSort require?
    4. Here is a description of how a space-inefficient version of QuickSort operates on an array X from indices start to end:

           1. If start >= end, stop (the array is sorted in the range from start to end).  Otherwise:
           2. Let Pivot = X[start].
              For k from start + 1 to end:
                -- If X[k] <= Pivot, copy X[k] into the next spot of temporary array called LessThanPivot.
                -- If X[k] >  Pivot, copy X[k] into the next spot of temporary array called MoreThanPivot.
           3. Recursively QuickSort LessThanPivot.
              Recursively QuickSort MoreThanPivot.
           4. Copy the sorted LessThanPivot into X,
              then put Pivot into the next position in X,
              then copy the sorted MoreThanPivot into the remaining positions in X.
       

       Be able to explain your answers to the following:
       • Explain why QuickSort does in fact sort array X.
       • What is the worst-case run time of QuickSort?
       • What is the best-case run time of QuickSort?
       • What is your best guess for the average-case run time QuickSort? (no analysis required)
       • How much extra space (beyond the space for X) does this version of QuickSort require?
    5. [5 points] Function objects: what are they, how are they used, why are they useful, Comparable and Comparator as examples.

       1. Sample problem: What is a function object?
       2. Sample problem: Is a Comparator a function object? Explain.

    Total: 130 points (but the exam will cover only 100 of the above 130 points, i.e., some topics will not show up on the exam)