First Slide:

Second Slide:

Argue the correctness of heap_increase_key (see this slide) using the following loop invariant: 1 I am using pythonic convention here, the last element in the range is not included A[0:10] array contains 10 elements - not 11 3 At the start of each iteration of the while loop in line 7 , the array A [0:heap_size] satisfies the max-heap property, except that there may be one violation: A [i] may be larger than parent (i). Recall that for the proof you must show three things, as listed on this slide of Lecture 8. HEAP-INCREASE-KEY A useful tool for proving correctness is loop invariants. Three things must be shown about a loop invariant - Initialization: Invariant is true before first iteration of loop Maintenance: If invariant is true before iteration i, it is also true before iteration i+1 (for any i ) Termination: When the loop terminates, the invariant gives a property which can be used to show the algorithm is correct