Use a loop invariant to prove that the following algorithm correctly identifies the location of the minimum value in the array data.
Input: data: array of integers
Input: n: size of data
Output: index min such that data[min] <= data[i] for any i from 1 to n
Algorithm: FindMin
min = 1;
for i = 2 to n do
if data[i] < data[min] then
min = i;
end
end
return min
******************************************************************************************
Please Upvote the answer as it matters to me a lot :)
*****************************************************************************************
As per HomeworkLib expert answering guidelines,Experts are supposed to
answer only certain number of questions/sub-parts in a post.Please
raise the remaining as a new question as per HomeworkLib
guidelines.
******************************************************************************************
Loop invariant :
before the loop, the array has only one element and it is the minimum value of the array till the 1st element so true.
Inside the for loop if the value of the element is less than the minimum element then we reassign the minimum value to the current element. At the end of each iteration, min has the correct index of the minimum value.
After the loop, min has the correct index of the minimum value of all the elements of the array.
Use a loop invariant to prove that the following algorithm correctly identifies the location of the...
(a) Prove the following loop invariant by induction on the number of loop iterations: Loop Invariant: After the kth iteration of the for loop, total = a1 + a2 + · · · + ak and L contains all elements from a1 , a2 , . . . , ak that are greater than the sum of all previous terms of the sequence. (b) Use the loop invariant to prove that the algorithm is correct, i.e., that it returns a...
(15 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an earray A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A i=j-1 while i > 0 and A[i] > key do Ali + 1] = Ai i=i-1 7: A[i+1] = key (a) Follow this algorithm for A[1..4) =< 7,9,6,8 >. Specifically, please indicate the contents of the array after each iteration of the outer...
Question 1. Below is the pseudo code for a divide and conquer algorithm that finds the minimum value in an array. Suppose that the input array, A, is of size n, analyze the computational cost of this algorithm in the form of Tin) and prove your conclusion findMin (A, left, right) if (left == right) return Alleft) center - (left + right) / 2 return min (findMin (A, left, center), findMin (A, center + 1, right)
Analyze the time complexity of the following algorithm. You may assume that the floor function in line 2 takes Theta (1) time. Please show your work. Input: data: array of integers Input: n: size of data Output: median of data 1 Algorithm: MedianSelect 2 lim = [n/2] + 1 3 min = - infinity 4 for i = 1 to lim do 5 prev = min 6 min = infinity 7 for j = 1 to n do 8 if...
Loop Invariants. I need help on the 15 point question. The 10 point question is the "procedure" from the previous question. 2: (10 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an array A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A[j] i=j-1 while i > 0) and A[i] > key do A[i+1] = A[i] i=i-1 A[i+1] = key 3: 4: 5: 6:...
Written in Java By maintaining the invariant that the elements in the priority queue are sorted in non-increasing order (that is, the largest item is first, the smallest is last), you can implement both findMin and delete Min in constant time. However, insert is expensive. Do the following: b. What is the Big-Oh running time for insert? c. Write an implementation that uses these algorithms. Algorithm “insert": l/Algorithm insert insert(key, priority) //Check condition if (size == Capacity) //Call the method...
no other details are given, its asking for the invariant programming language: Java Question 3. [15 marks in total Consider the following code fragment with missing statements at ????. Assume that A is a nonempty array of integers and has length N. Assume that it has already been initialised. Refer to this code in parts (a-e) below. A [0] int count 1; int i- 1 while (i< NI1 count> N/2 ) if (xAi]) count++ int x else ???? i+ if...
For this pseudocode present a loop invariant and prove it, n >= 0. i <= 0; s <=2; while i < n do i <= i + 1 s <= s * s
Problem Description proving program correctness Consider the following program specification: Input: An integer n > 0 and an array A[0..(n - 1)] of n integers. Output: The smallest index s such that A[s] is the largest value in A[0..(n - 1)]. For example, if n = 9 and A = [ 4, 8, 1, 3, 8, 5, 4, 7, 2 ] (so A[0] = 4, A[1] = 8, etc.), then the program would return 1, since the largest value in...
Explain why the following algorithm is complete, correct, and finite. Input: a list of n distinct integers a0 to an-1 ordered from least to greatest and an integer x Output: the index in the list at which x is found, or -1 if x is not found Procedure: i = 0 while (i <= n-1 and x != ai) i = i + 1 if i < n then location = i else location = -1 return location