CS 2401 Test #3

Date: Wednesday, November 21, 2010.

Name: ___________________________________________________________________

1-3. Show, step by step, how the following algorithms will sort the list consisting of elements 11, 21, 20, and 10:

No code is needed. What is the worst-case and average complexity of each of these algorithms?










































4-7. Show, step by step, how the following algorithms will sort the list consisting of elements 11, 21, 20, and 10: Describe a pseudocode for mergesort. No code is needed. What is the worst-case and average complexity of each of these algorithms?


















































8. Show, step by step, how binary search will look for an element 19 in the sorted list 10, 11, 20, and 21. No code is needed. What is the worst-case and average complexity of binary search?


























































9-10. Show, step by step, what will happen if we add elements 11, 21, 20, and 10 (in this order) to an (initially empty) binary search tree (no need to balance), print the elements of this tree in pre-, in-, and post-order, and then delete element 11.

























































11. For extra credit: prove that the worst-case complexity of a sorting algorithm cannot be smaller than O(n*log(n)).