2. Getting Started

Exercises

2.1-1

2.1-2

Available in the latest revision of the IM.

2.1-3

Available in the latest revision of the IM.

2.1-4

Available in the latest revision of the IM.

2.1-5

Available in the latest revision of the IM.

2.2-1

Available in the latest revision of the IM.

2.2-2

Available in the latest revision of the IM.

2.2-3

Available in the latest revision of the IM.

2.2-4

Available in the latest revision of the IM.

2.3-1

2.3-2

Available in the latest revision of the IM.

Here is an alternative proof that relies on the properties of the divide step, as explained in the book on page 38. Initially, we have $p \le r$. Any call with this condition satisfied cannot lead to a subsequent recursive call with $p>r$ for the following reasons:

• If $p=r$, then the procedure returns without making any further calls.

• Otherwise $p < r$ and the divide step computes the index $q$ that partitions $A[p:r]$ into two adjacent subarrays containing $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$ elements, respectively. None of these will be empty, since $n=r-p+1 \ge 2$. Consequently, both recursive calls will happen with $p \le r$.

2.3-3

Available in the latest revision of the IM.

2.3-4

Available in the latest revision of the IM.

2.3-5

Available in the latest revision of the IM.

2.3-6

Available in the latest revision of the IM.

2.3-7

Available in the latest revision of the IM.

2.3-8

Available in the latest revision of the IM.

Problems

2-1 Insertion sort on small arrays in merge sort

Available in the latest revision of the IM.

Timsort is a superb case study, that illuminates many of the intricacies in developing a hybrid sorting algorithm, derived from merge sort and insertion sort.

2-2 Correctness of bubblesort

Available in the latest revision of the IM.

2-3 Correctness of Horner’s rule

Available in the latest revision of the IM.

2-4 Inversions

Available in the latest revision of the IM.