4.6. Exercises

4.6.1. Exercise 1

Modify binary_search in a way that it does not test the equality of fst arr.(mid) = k and does not exclude the middle element, but rather considers it as a part of one of the recursively processed array subparts.

4.6.2. Exercise 2

Implement a version of merge sort that splits the sub-arrays into three parts and then combines them together. Compare its performance to the ordinary 2-way merge sort.

4.6.3. Exercise 3

Develop and implement a version of merge sort that does not rearrange the input array arr, but returns an array perm of type int array, such that perm.(i) is the index in arr of the entry with i th smallest key in the array.

4.6.4. Exercise 4

Implement and check the loop invariants (described in the text) of the partition procedure from Section Partitioning an array, as well as as the procedure’s postcondition. The assertions should relate the initial array, the final array and returned i. You might need to introduce an initial copy of an unmodified array to assert those statements.

4.6.5. Exercise 5

Change the procedure partition from Section Partitioning an array so it would take as pivot the first element of an array.

4.6.6. Exercise 6

Implement and check a precondition of the sort subrouting within quick_sort from Section Partitioning an array. It should relate the initial array, and the sub-arrays, obtained as results of partitioning, stating something about the arrangement of elements in them wrt. element at the position mid and others.

4.6.7. Exercise 7

Solve, by means of changing a variable, the following recurrence relation:

\[\begin{split}\begin{align*} f(1) &= 1 \\ f(n) &= 4 f(n/2) + n^2, \text{if}~n > 1 \end{align*}\end{split}\]

4.6.8. Exercise 8

What is the worst-case complexity of Quicksort? Obtain it by stating and solving the corresponding recurrence relations. Give an example of an array when the worst-case complexity is achieved (hint: think of a case insert sort does its best).

4.6.9. Exercise 9

Prove, out of definitions that for ay two functions \(f(n)\) and \(g(n)\), one has \(f(n) \in \Theta(g(n))\) if and only if \(f(n) \in O(g(n))\) and \(f(n) \in \Omega(g(n))\).

4.6.10. Exercise 10

Enhance A functor for sorting Sorting, so it would also take an instance of a signature Printable that provides an implementation for printing elements of an array. With that Sorting should also feature a second version of sorting, sort_print, which will print a sorting trace using the machinery imported from Printable.