Monday, October 15
1. ( T / F ) If f(n) = O(n2) and g(n) = O(n3), then g(n) / f(n) = O(n).
2. ( T / F ) If f(n) = Q(n2) and g(n) = 5n3 + 6n + 5 log n, then f(n) = O(g(n)).
3. ( T / F ) Any algorithm to find the maximum sum subsequence of an array of numbers requires W(n) time.
4. ( T / F ) It is possible to swap two adjacent elements in a singly linked list, given pointers to the two elements, in O(1) time.
5. ( T / F ) Even given an optimal algorithm, it might take as much as W(n) time to swap (any) two elements in a doubly linked list, given pointers to the two elements.
6. ( T / F ) A disadvantage of using a linked list implementation (versus an array implementation) for the Queue ADT is that the linked list implementation uses extra space for pointers.
7. Write a recursive routine makeEmpty() for a Stack that makes the stack logically empty, using only the isEmpty() and pop() operations. Is this a good use of recursion? Why or why not?
template <class Object>
void Stack<Object>::makeEmpty()
8. Suppose a recursive algorithm A divides a problem into three subproblems, where the size of each subproblem is half the size of the original problem, and performs c steps to combine the result of the subproblems. Write a recurrence equation that describes the running time of the algorithm A.
9. Extra credit Consider ternary search, which is a natural extension to binary search. Instead of dividing the array into two halves and repeatedly searching for the number in the appropriate half, ternary search picks two probes, one at position N/3 and another at position 2N/3, determines which third of the array to continue searching, and then repeatedly searches in the same way. Do you think ternary search would be a faster algorithm than binary search in big-O terms? Why or why not?