1. The idea of Bubblesort is that it makes n passes for an n-sized array A. After the k-th pass, A[1...k] contains the smallest k elements of A in the increasing order, and in the (k+1)-th pass, the minimum element from {A[k+1] ... A[n]} is "bubbled" (series of swaps between elements and their neighbours) to A[k+1].

Consider this algorithm:
// bubble min{A[j] … A[n]} to A[j]
// requires: A[1...j-1] to be correct
bubble(j): 
    if j >= n: return
    else:
	bubble(j+1)
	if A[j] > A[j+1] : swap A[j] & A[j+1]

and this one:

BubbleSort(A):
    for i = 1 ... length(A): 	
	bubble(i)

(a) Prove that bubble(j) correctly puts min{A[j] … A[n]} to A[j] when A[1...j-1] is correctly sorted at the beginning of the algorithm.

(b) Prove that BubbleSort(A) correctly sorts the array A.

(c) Let T(k) denote the worst-case time complexity of bubble(n-k). Write a recurrence relation for T(k) and solve it.

(d) Explain the complexity of BubbleSort.

(e) Note that the proof of correctness of bubble() and BubbleSort() did not use the fact that bubble() required to bubble a value to its right position. Propose an alternative implementation of bubble() that does not involve any bubbling, and not any more inefficient compared to the above implementation.

(f) Consider the above implementation of bubble(). Propose an optimization for BubbleSort() by keeping track of the number of swaps during bubble(j). Note that the alternative implementation in (e) is no longer applicable. Hint: What happens if there are zero swaps during bubble(j) ?

(g) Consider the implementation in (f). Propose an even better optimization for BubbleSort() by keeping track of the smallest pair of indices involved in swapping? Hint: What if you are told that during bubble(10), A[15]-A[16] were swapped and no A[j]-A[j+1] were swapped for j < 15?

(i) Analyse the asymptotic complexity of the algorithms in (f) and (g).

2. Recall the Merge() subroutine involved in MergeSort(). 

// A and B are sorted
// C is for storing the result after merging
def Merge(A[1...n], B[1...n], C[1... 2n]):
    return MergeRecursive(A, B, C, ...) // add other parameters as needed

// Recursively merge A and B and put the result in C
// Assume that A and B are sorted
def MergeRecursive(A, B, C, ...): // add other parameters as needed
    ??? Add code

(a) Finish the signature of the MergeRecursive() subroutine and write its pseudocode.

(b) Write a recurrence relation for the time complexity of MergeRecursive. Use the relation to deduce the worst-case time complexity of MergeRecursive(A[1...n], B[1...n], C[1... 2n]).