Name:________________________________________

These questions are over the prerequisite material for the course (undergraduate analysis of algorithms). You should either be able to answer these questions quite easily, or be prepared to do a significant amount of work on your own to learn or review the material. Pretest will be Thu, Sep 4, and count as a homework.

~~~~~~~~~ BACKGROUND ~~~~~~~~~
1. Why does the efficiency of an algorithm matter in today's world of fast processors and cheap memory?
2. Prove the following statement using mathematical induction:
   For all n >= 0, the sum, for i from 0 to n-1, of (2i+1) equals n^2.
3. Prove the following statement using mathematical induction: A complete binary tree of height h has 2^{h+1} - 1 nodes.
4. True or False:
   • 2^{n+1} = O(2^n)
   • 2^{2n} = O(2^n)
   • For all functions f and g, if f = Θ(g), then f = O(g) and f = Ω(g).
   • For all functions f and g, if f = O(g), then f = Ω(g).
5. Suppose mergesort is executed on an array of length n. Write the recurrence relation that describes the worst-case running time. Then solve the recurrence.
   
   
6. Name one advantage of insertion sort over mergesort and one advantage of mergesort over insertion sort.

   ~~~~~~~~~ BINARY HEAPS ~~~~~~~~~

7. Draw the result (in tree format) of inserting the following sequence of numbers into an initially empty binary max heap:
   10, 15, 7, 9, 12, 4, 14.
8. Draw the result of removing the minimum from this binary min heap:

               2
             /   \
             8    5
           /  \  / 
          10  9  6
   

9. Describe heapsort briefly. What is the tight asymptotic bound on the worst-case running time of heap sort?

   ~~~~~~~~~ SORTING ~~~~~~~~~

10. What is the tight asymptotic worst-case running time for deterministic quicksort?
11. What is the tight asymptotic worst-case running time for randomized quicksort?
12. What is the tight asymptotic expected running time for randomized quicksort?
13. Explain the difference between calculating the average running time for deterministic quicksort and calculating the expected running time for randomized quicksort.
14. What is the lower bound on the time to sort n numbers using any comparison-based sorting algorithm? What is a sorting algorithm that improves on this bound and why is not comparison-based?

    ~~~~~~~~~ BINARY SEARCH TREES ~~~~~~~~~

15. What is the binary search tree property?
16. What is maximum height of a binary search tree with n nodes?
17. What is minimum height of a binary search tree with n nodes?
18. Draw the result of inserting the following sequence of keys into an initially empty binary search tree:
    10, 15, 7, 9, 12, 4, 14
19. Draw the result of deleting key 9 from the following binary search tree:

                9
              /   \
              5    12
            /  \    \ 
           3    7    15
    

20. What is the asymptotic time to do an in-order traversal of a binary search tree on n nodes with height h?
21. What is treesort and what is its worst-case running time?

    ~~~~~~~~~ HASHING ~~~~~~~~~

22. What is the main advantage of using hash tables over using search trees? What assumptions are required in order to realize this advantage?
23. Compare the two ways of doing collision resolution in hashing (chaining and open addressing) by giving one advantage of each.

    ~~~~~~~~~ GRAPHS ~~~~~~~~~

    Consider the following graph G.
    Nodes are labeled a through g. (Undirected) edges are: {a,b} with weight 1, {a,c} with weight 2, {c,e} with weight 3, {b,e} with weight 4, {b,d} with weight 5, {d,g} with weight 6, {e,g} with weight 7, {f,g} with weight 8, {a,f} with weight 9, and {a,g} with weight 10.

24. Draw the breadth-first search tree for graph G starting at node f. Consider neighboring nodes in alphabetical order.
25. Draw the depth-first search tree for graph G starting at node f. Consider neighboring nodes in alphabetical order.
26. What is the asymptotic running time of depth-first search? Of breadth-first search?
27. Draw the minimum spanning tree (MST) of graph G.
28. Consider the execution of Kruskal's minimum spanning tree algorithm on graph G. List the edges in the order in which they are added to the set T. Recall that T is the set of edges of the MST that is output at the end of the algorithm.
29. What is the asymptotic worst-cast running time of Kruskal's algorithm, as a function of the number of nodes and the number of edges of the input graph?
30. What is the asymptotic worst-cast running time of Prim's MST algorithm, as a function of the number of nodes and the number of edges of the input graph?