CSCI 3300
Spring 2010
Exercises for Quiz 7

1. How much time does Quicksort take to sort an array of n integers in the average case?

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

   Answer

2. How much time does Quicksort take to sort an array of n integers in the worst case?

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

   Answer

3. The Quicker-sort algorithm is similar to Quicksort, but it guarantees that, when sorting an array of size n, it will never need more than about log₂(n) frames in the run-time stack at once. (A frame in the run-time stack is a running call to the function.) How does Quicker sort make that guarantee?

   Answer

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

   Answer

5. If a first-in-first-out queue is implemented efficiently, how long does each operation take, to within a constant factor?

   Answer

6. We looked at an efficient way to implement sequences with concatenation, where concatenating two sequences does not destroy either of the two sequences that are being concatenated. What is the amortized cost per operation of that data structure? (The amortized cost looks that the worst case over all sequences of operations, but measures the average time per operation, averaged over all of the operations.)

   Answer

7. You need to travel two miles. Suppose that you travel the first mile at 30mph. How fast do you need to travel the second mile in order to average 60mph?

   Answer

8. Our efficient algorithm for sequences with concatenation is efficient on average, but some operations can be expensive. Does that mean that some sequences of calls to the supported operation lead to very slow behavior by our algorithm, but that most lead to efficient behavior?

   Answer

9. Does a queue have to be implemented in a destructive way, or does it make sense to have a nondestructive implementation of the concept of a queue?

   Answer

10. A quasi-deque is similar to a queue in that it holds, at any given time, a sequence of values. But there are four operations, plus one constructor. This is a destructive data structure, so operations typically change what it is holding.

    QDeque

    When a quasi-deque is created, it is initially empty.

    isEmpty(d)

    This is true if d is empty

    insertAtFront(d, x)

    This inserts x at the front of d

    insertAtBack(d, x)

    This inserts x at the back of d

    removeFromFront(d, x)

    This removes the front value from quasi-deque d, and stores it into variable x. Notice that x must be call-by-reference, since it is an out parameter. An attempt to remove a value from an empty quasi-deque does nothing, and does not store anything into x.

    Using a linked list to represent the members of the quasi-deque, write an implementation of type QDeque, including a type, a constructor and all of the functions. Assume that the members of a quasi-deque have type QDequeMemberType. For now, define QDequeMemberType to be int, but make it so that the type can be changed by changing only one line of the program.

    Answer

11. You can implement a first-in-first-out queue as a linked list, with just a pointer to the front of the list. To add a value to the end of the queue, just scan to the end of the linked list and add the new value. Why isn't that a good way to implement a queue?

    Answer