CS 2401 Test #3

Date: Tuesday, November 20, 2010.

Name: ___________________________________________________________________

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

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, 20, 201, and 0: 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 18 in the sorted list 0, 11, 20, and 201. 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, 20, 201, and 0 (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)).