1. Explain the differences between average-case running time analysis and expected running time analysis. For each type of running time analysis, name an algorithm we studied to which that analysis was applied.
2.(a) T F A preorder traversal of a binary search tree will output the values in sorted order.
(b) T F The cost of searching in an AVL tree is O(lg n).
(c) T F The expected amount of space used by a skip list on n elements is O(n).
(d) T F Any mixed sequence of m increments and n decrements to a k-bit binary counter (that is initialized to zero and is always non-negative) takes O(m+n)time in the worst case.
(e) T F Given a bipartite graph G and a matching M ,we can determine if M is maximum in O(V+E).
(f) T F Suppose you are given an undirected connected graph with integer edge weights in which each vertex is degree 2. An MST can be computed for this graph in O(V) time.
3.Short Answer Problems
Give brief, but complete, answers to the following questions.
Amortized Analysis
You are to maintain a collection of lists and support the following operations.
(i) insert(item, list): insert item into list (cost = 1).
(ii) sum(list): sum the items in list, and replace the list with a list containing one item that is the sum (cost = length of list).
(a) Use the Accounting Method to show that the amortized cost of an insert operation is O(1)and the amortized cost of a sum operation is O(1).