' SI335: Finishing Merge Sort; lower bounds on sorting [HW]
Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)

Analogous to the tree we drew in class for insertion sort on three elements, draw the tree for selection sort on three elements. Please follow the same conventions!

Problem 1 (assessment: self_______ final_______)

Based on the tree you just drew and the tree for selection sort, how do the best and worst case number of comparisons for selection sort on three elements compare to the best and worst case number of comparisons for insertion sort on three elements? Describe another insteresting differences between these trees.