Review Questions for Midterm

CS409 - Spring 2000

The exam will take place at 8:40am (our regular time) in Philips 219 (our regular classroom) on Tuesday, March 7.  I will try to arrive early 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 2.  The course web is in the process of being updated to show readings corresponding to the lecture topics.

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.

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)        
    hashtable        
    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. Assume that the data set is going to be large unless otherwise indicated.  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 Hashtable

     

  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. Note that these are the only operations, so for this problem it is not an advantage for a data structure to allow more operations.
    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. 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.

  10. We know that a sequence of n union/find operations using weighted union and path compression takes time O(n alpha(n)) where alpha(n) grows extremely slowly.   What if all the union operations are done first?  Show that a sequence of n unions followed by m finds takes time O(n + m). [Hint: The time for a find operation is proportional to the number of links that it changes.  How many links are there?]