Loop Invariant

COMP 3270 – Homework 2Due: 09/09/2024 on Canvas
Algorithm Correctness and Loop invariant
1. Prove the correctness of the below given algorithm.
procedure CountingSort(arr):
# Find the maximum and minimum values in the input
array
max_val = findMax(arr)
min_val = findMin(arr)
# Create an array to store the count of each element in
the input array
count = array of size (max_val – min_val + 1)
initialized with 0
# Count the occurrences of each element in the input
array
for num in arr:
count[num – min_val] += 1
# Update the count array to store the cumulative count
for i from 1 to length(count) – 1:
count[i] += count[i – 1]
# Create the output array
output = array of size length(arr)
# Build the output array using the count array
for num in reverse(arr):
output[count[num – min_val] – 1] = num
count[num – min_val] -= 1
return output
2. For the algorithm given below,
Input: an array, ‘arr’ of length n
Output: reversed array, ‘arr’
def reverse_array(arr):
left, right = 0, len(arr) – 1
while left < right: arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 a. State the loop invariant. b. Use the invariant to prove that the postcondition is satisfied. c. Show that the algorithm terminates. 3. Prove that sum = i2 after every iteration of the for loop below: