- Important notes on HW#1
September 23, 2009 05:13PM - Here are notes on the homework. Please read them carefully.
1. (Problem 1.a) Don't forget to show the correctness of your algorithm using loop invariant method (page 18 in the book)
2. (Problem 1.c) please make sure that you understand what the code lines 5-7 in the insertion sort do. When replacing them by the binary search code, make sure that the sort algorithm works as intended and then analyze the complexity. Your answer should include an argument for why or why not the replacement of the code can (or can't) improve the performance of the OVERALL algorithm.
3. (Problem 2.c) Do what the question directly asks for. Consider the the running time of insertion sort on a specific input (array) and the number of inversions in an the same array as two different issues (measurements) and write down the relationship between them. You may want to talk about the worst case, best case, and average case in insertion sort versus the largest number of inversions, smallest number of inversions, and average number of inversions and correlate them to the status of the input each time.
4. (Problem 2.d) Write down why your design take n log n (i.e., analyze your algorithm) as well.
Posted from Diigo. The rest of my favorite links are here.
