4. We often use a loop invariant to prove that an algorithm gives the correct answer. To use a loop invariant to prove correctness, we must show three things about it: 1)Initialization: It is true prior to the first iteration of the loop. 2) Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration. 3)Termination: When the loop terminates, the invariant (usually along with the reason that the loop terminated) gives us a useful property that helps show that the algorithm is correct. Let's take a look at the following Bubble sort algorithm. BUBBLESORT(A) outer: 1 for i = 1 to A. length - 1 inner: 2 for j = A.length downto i +1 3 if A[j] ...