Review Questions for Midterm

CS409 - Spring 1999

The exam will take place at 8:40am (our regular time) in Upson 205 (our regular classroom) on Thursday, March 11.  I will try to arrive early so that the chairs can be spread out somewhat and so that we can start right at 8:40.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material covered in lecture through March 9 and the corresponding material in the text (Chapters 1, 2, 4.1, 4.3, 7.1-3, 7.5, 11, 12.1-3, 13.1-3, 14.1-2, 16, 19.1-2, 22.1-3, 31.2, 35.4).  See the online schedule for a list of topics covered.

The exam will attempt to gauge your knowledge and understanding of course concepts. You should understand the terms used in the course and understand how the various data structures and algorithms work, but you shouldn't need to memorize the specific code given in the text or in lecture.

The review questions given here are not meant to exhaust the possible topics for exam questions.  Check the online schedule and consider reviewing the homework assignments and quizzes.

There will be no new homework assigned this week.

Review Questions

  1. Fill in the table below with the expected time for each operation. Use big-O notation. The operations are insert (place a new item in the data structure), member (test if a given item is in the data structure), getMin (return the value of the minimum item in the data structure and delete it from the data structure), and successor (given an item, return the successor of that item).
    Data Structure insert member getMin successor
    sorted array        
    unsorted array        
    balanced tree (red-black tree)        
    hashing        
    sorted linked list        
    unsorted linked list        
  2. Short Answer.
    1. Where is the smallest element in a red-black tree?  In a 234-tree?
    2. When the subject is balanced trees, what does rotation mean?
    3. What is path compression in the union/find algorithm?
    4. How long does it take to insert a new element into a heap? To return the smallest thing in a min-heap? To delete the smallest thing in a min-heap? To find the largest thing in a min-heap?
  3. The following picture represents a 234-tree. 
                      24
               /      \
        2 , 22            30 , 40 , 48
      /   |     \      /    /      \      \
     1  5,11,19  23  29  32,36  41,42,43  50
    1. Draw an equivalent red-black-tree.
    2. Draw a picture of the 234-tree that results from inserting 31 into the original 234-tree.
  4. For each of the following problems, choose the best of the listed data structures and explain why your choice is best. Where several operations are listed, you should assume, unless stated otherwise that the operations occur with about equal frequency.
    1. Operations are Insert, DeleteMax, and DeleteMin.
      balanced tree or sorted doubly-linked list
    2. Operations are Insert and FindMedian. (The median is the item m such that half the items are less than m and half are greater than m.)
      red-black trees or sorted array
    3. You have a dictionary containing the keywords of the Pascal programming language.
      ordered array or red-black tree
    4. You have a dictionary that can contain anywhere from 100 to 10,000 words.
      unordered linked-list or red-black tree
    5. You have a large set of integers with operations insert, findMax, and deleteMax.
      unordered array or hashing with linear probing
  5. You have a hashtable of size m=11 and a (not very good) hash function h:

    h(x) = (sum of the values of the first and last letters of x) mod m

    where the value of a letter is its position in the alphabet (e.g., value(a)=1, value(b)=2, etc.). Here are some precomputed hash values:
    word ape bat bird carp dog hare ibex mud koala stork
    h 6 0 6 7 0 2 0 6 1 8

    Draw a picture of the resulting hashtable (using chaining) after inserting, in order, the following words: ibex, hare, ape, bat, koala, mud, dog, carp, stork. Which cells are looked at when trying to find bird.

  6. Suppose you are given the following information about a hashtable.
    Space Available (in words) 10000
    Words per Item 7
    Words per Link 1
    Number of Items 1000
    Proportion Successful Searches 1/3

    What is the expected number of probes for a search operation when hashing with chaining is used?

  7. Consider a tree implementation for the union/find problem in which the smaller set is merged to the larger and the name of the set is taken to be the element stored at the root of the tree. Suppose we initialize our sets so that each integer between 1 and 8 (inclusve) is contained within its own set.
    1. Give a sequence of seven unions that produces a tree whose height is as large as possible. Your answer should be a sequence of procedure calls of the form Union(a,b) where a and b are integers between 1 and 8. Draw the resulting tree.
    2. Give a sequence of seven unions, on the original eight sets, that produces a tree of minimum height. Draw the resulting tree.
    3. Explain why both the min- and max-height trees use seven unions.
  8. The following questions refer to an implementation of an ADT with operation Insert, Delete, and isMember.
    1. Under what conditions would you use a red-black tree instead of hashing with chaining?
    2. Under what conditions would you use an unordered array instead of a red-black tree?
    3. Under what conditions would you use a binary search tree instead of a heap?
    4. What implementation would you use to get the best expected time for a search?
    5. What implementation would you use to get the best worst-case time for a search?
  9. Consider the following program outline where |A| represents the number of items in array A. 
      method Review (array A) {
     if (|A| > 1) {
        Do something to A that takes time O(|A| log(|A|));
        Split A into two equal size pieces called B and C;
        Review(B); Review(C);
        Modify A using O(|A|) time;
     }
  }

    What is the recurrence that describes the time used by this program?

  10. 234 Tree (Dictionary) Max-Heap (Priority Queue) 
          (3 , 5)
     /   |   \
(1,2)   (4)   (6)
    		 
         6
   /   \
  3     4
 / \
1   2

    For each of the preceding trees, find a sequence of appropriate operations that will produce it starting from an empty tree.

  11. Determine the best possible big-O bounds on T(n) where T(n) is defined by the following recurrence:
    T(n) = cT(n/2) + n2 and T(1) = 1.  The variable c here represents a positive constant.  You should have 3 different answers depending on the value of c.
  12. You are given a k×k checkerboard with a nonnegative number in each square (the square colors are not significant).  A token is moved from square to square on the board.   Each time the token enters a square it is charged the amount written in that square.  Assume that the only legal moves are to-the-right, down, and diagonally right-down.  Give an algorithm that runs in O(k2) time to find the cost of the minimum cost sequence of moves beginning in the upper left corner of the board and ending at the lower right corner.
  13. Suppose we are given a sequence A = (a1,a2,...,an) of numbers.  Describe an O(n2) time algorithm for finding the longest subsequence of A such that the numbers in this subsequence are monotonically increasing.   (Hint: For each ai, compute the longest increasing subsequence that ends at ai.)  It's possible, but more difficult, to develop an algorithm that takes time O(n log n). [from Goodrich & Tamassia 98]