CS410: Review Questions for Midterm

Review Questions

1. Show that (n³lg(n)) +7 is O(n⁴).
2. Solve the following recurrences:
   1. T(n) = 2T(n/2) + lg(n)
   2. T(n) = 16T(n/2) + (n lg(n))⁴
   3. T(n) = 9T(n/3) + n³ lg(n)
3. 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), search (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	search	getMin	successor
   sorted array
   unsorted array
   red-black tree
   hashing
   sorted linked list
   unsorted linked list

4. Short Answer.
   1. What is an abstract data type? Give an example.
   2. What is a data structure? Give an example.
   3. Order the following running times from fastest to slowest.
      O(n), O(1), O(n²), O(lg n), O(n lg n), O(n/(lg n)).
   4. Where is the smallest element in a red-black tree? 
   5. Explain why double hashing is better than hashing with linear probing.
   6. Why must care be taken when deleting an item from a hashtable?
   7. When the subject is red-black trees, what does rotation mean?
      
      The following questions refer to an implementation of an ADT with operation Insert, Delete, and isMember.
      
   8. Under what conditions would you use a red-black tree instead of hashing with chaining?
   9. Under what conditions would you use an unordered array instead of a red-black tree?
   10. What implementation would you use to get the best expected time for a search?
   11. What implementation would you use to get the best worst-case time for a search?
       
5. Build a binary search tree by inserting the following integers: 7, 0, 5, 2, 4, 6, 3, 8, 1.
   
6. 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.
   red-black 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. Operations are Insert and FindMedian.
   sorted linked list or sorted array
4. A large dictionary (operations: Insert, Delete, Find), but we must conserve space.
   balanced tree or singly linked list or array
5. Items are integers between 1 and 100. There is data associated with each item. Operations are Insert, Delete, and Find. Duplicate items do not occur.
   array or linked list
6. You have a dictionary that contains at most 10 words.
   red-black tree or unordered array
7. You have a dictionary that can contain anywhere from 100 to 10,000 words.
   unordered linked-list or red-black tree
8. You have a large set of integers with operations insert, findMax, and deleteMax.
   unordered array or hashing with linear probing
7. You have a hashtable of size m=11 and (not very good) hash functions h1 and h2:
   
   h1(x) = (sum of the values of the first and last letters of x) mod m
   h2(x) = ((value of the last letter) mod (m-1)) +1
   
   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
   h1	6	0	6	7	0	2	0	6	1	8
   h2	6	1	5	7	8	6	10	5	2	2

   Draw a picture of the resulting hashtable after inserting, in order, the following words: ibex, hare, ape, bat, koala, mud, dog, carp, stork. Also highlight cells that are looked at when trying to find bird. Do this for each of the following techniques.

   • Chaining with h1 as your hash function.
   • Linear probing with h1 as your hash function.
   • Double hashing with h1 as your first hash function and h2 as your second hash function.

   Why not use h2(x) = (value of the last letter) mod m? (i.e., why did we include -1 and +1?)
   Why not use the same function for both hash functions?

8. We wish to implement a RangeSearch operation on sets of integers. For example, RangeSearch(a,b) will return all the integers c in the set such that a<c<b. The time for a RangeSearch will be of the form O(X+i) where i is the number of integers within the given range and X is some function that depends on n, the number of items in the set. (We are stuck with i here since it takes that much time just to print the answer to a given RangeSearch query.) For each of the following data structures, determine the best value of X in the RangeSearch query time. Give a short explanation of why you think that amount of time is needed.
   (a) Sorted array. (b) Red-black tree. (c) Hashtable.
   
9. Suppose you are given the following information about a hashtable.

   Space Available (in words)	10000
   Words per Item	7
   Words per Pointer	1
   Number of Items	1000
   Proportion Successful Searches	1/3

   "Proportion Successful Searches=1/3" means that of every 300 search queries into the table, about 100 are successful and about 200 are unsuccessful.
   (The expected time for successful search in double hashing is (1/a)*ln (1/(1-a)), where a is the load factori, and in chaining it is 1+a/2.)
   Which hashing method, chaining or double hashing, looks best (i.e., the one that we expect to use the least amount of time)?  You should use the following assumptions:

   • It takes twice as long to compute a hash function as it does to do a key comparison.
   • For hashing with chaining use a singly linked list.
   • Double hashing behaves like random hashing.
   • During double hashing, we always compute both hash functions, even when we find the item we're looking for on the first probe.
   • Items are not copied directly into the hashtable; instead we maintain a link to the item.  Note though that the items themselves still use up some of the space.
10. Suppose we wish to insert the keys D A T A S T R U C T U R E into a Dictionary.   Assume we are using a tree-based implementation. Further, assume that identical keys share a single node (i.e., their data reside in a linked list attached to this single node). 
    1. Show the resulting Binary Search Tree.

    Assume now that we are using a hashtable of size 17 with the hash function h(x) = x mod 17 for the letter at position x in the alphabet (e.g., A=1, B=2, etc.).

    3. Show the hashtable that results when we use chaining.
    4. Show the hashtable that results when we use linear probing.
    5. Show the hashtable that results when we use double hashing. Use g(x) = 1 + (x mod 13) for the second hash function.

    10. 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 X;
    
    
    
            Split A into two equal size pieces called B and C;
    
    
    
            Review(B); Review(C);
    
    
    
            Modify A using O(|A|) time;
    
    
    
         }
    
    
    
      }          

     

    a. What is the recurrence formula that describes the time used by this program if X=O(|A|lg(|A|))?
    b. Solve the recurrence formula that describes the time used by this program if X = O(|A| ).