CSCI 3300
Spring 2010
Exercises for Quiz 6

1. To within a constant factor, how much time does it take, on average, to insert a value into a hash table that has n values in it?

   Answer

2. Would a hash table be a useful tool for sorting an array? Why or why not?

   Answer

3. Suppose that a linked list is used to store a set of numbers. If there are n numbers in the list, how long, to within a constant factor, does it take to check whether a given number is in the list, in the worst case?

   Answer

4. If you insert 6 into the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

5. If you remove the smallest value from the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

6. If you insert 10 into the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

7. If you remove the smallest value from the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

8. An efficient algorithm that implements a priority queue uses how much time per insert or remove operation, in the worst case?

   1. O(1)
   2. O(log₂(n))
   3. O(n)
   4. O(n log₂(n))
   5. O(n²)

   Answer

9. To within a constant factor, how long does Heapsort take to sort an array of n numbers, in the worst case?

   Answer

10. If an algorithm sorts a list of n values by using comparisons, then, to within a constant factor, in the worst case, that algorithm must use at least

    1. log₂(n) comparisons.
    2. n/log₂(n) comparisons.
    3. n comparisons.
    4. n log₂(n) comparisons.
    5. n² comparisons.

    Answer

11. Is it possible to create an implementation of binary search trees that is nondestructive (so that it builds new trees rather than modifying existing trees) or must every implementation of binary search trees work by making modifications to existing data structures?

    Answer

12. Larry says that he has a comparison algorithm that sorts an array of n integers in time O(n^0.5), in the worst case. Explain why Larry cannot possibly be right.

    Answer

13. Larry says that he has an algorithm that sorts an array of n integers in time O(log₂(n)), in the worst case. It is not based on doing comparisons, but access the data to be sorted in a more general way. Explain why Larry still cannot possibly be right.

    Answer