4.7. Exercises

4.7.1. Mandatory exercises

None

4.7.3. Exercise 1

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 inroduce an initial copy of an unmodified array to assert those statements.

4.7.4. Exercise 2

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

4.7.5. Exercise 3

Implement and check a precondition of the sort subrouting withint 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.7.6. Exercise 4

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.7.7. Exercise 5

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.7.8. Exercise 6

Prove, out of definitions that for ay two functions \(f(n)\) and :math:`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.7.9. Exercise 7

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.

4.7.10. Exercise 8

Change the implementation of Enhanced Bucket Sort, so it would not require to take the gues for a maximal key as a parameter, while retaining the same aymptotic complexity.

4.7.11. Exercise 9

Implement and test the invariant for the while-loop of Radix Sort.