Chapter 2 Section 1 Exercises Intro to Algorithms CLRS (3rd)

2.1-1 Using figure 2.2 as a model, illustrate the operation of insertion sort on the array A=<31,41,59,26,41,58>. Solution: Check <31,41,59,26,41,58> Continue. Check <31,41,59,26,41,58> Continue. Check <31,41,59,26,41,58> Swap/Check <31,41,26,59,41,58> Swap/Check <31,26,41,59,41,58> Swap/Check <26,31,41,59,41,58> Continue. Check <26,31,41,59,41,58> Swap/Check <26,31,41,41,59,58> Continue. Check <26,31,41,41,59,58> Swap/Check <26,31,41,41,58,59> End.

2.1-2 Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order. Solution: 
2.1-3 Consider the searching problem: 
Input: A sequence of n numbers in a list A and a value v.
Output: An index i such that v=A[i] or the special value NIL if v does not appear in A. Write linear search, which scans through the sequence looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
Solution: At the start of each iteration of the loop, the value has not appeared for the checked values in the subarray A[1,..,j]. This is our loop invariant.

2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C.

Solution: