Question: Consider sorting n numbers stored in array A by first
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A. Then find the second smallest element of A, and exchange it with A . Continue in this manner for the first n - 1 elements of A. Write pseudo code for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n – 1 element’s rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ- notation.
Answer to relevant QuestionsUse mathematical induction to show that when n is an exact power of 2, the solution of the recurrenceHow can we modify almost any algorithm to have a good best-case running time?Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + cn, where c is a constant, is Ω(n lg n) by appealing to a recursion tree.Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray ...Illustrate the operation of MAX-HEAP-INSERT (A, 10) on the heap A = 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1. Use the heap of Figure 6.5 as a model for the HEAP-INCREASE-KEY call.
Post your question