== 1 ==
Use INSERTION-SORT to sort the sequence <31, 41, 59, 26, 41, 58>.
For each iteration of the for-loop, show the values of the variables and the content of the array.
Iteration j = 2
A = <31, 41, 59, 26, 41, 58>
key = 41
i = 1
Iteration j = 3
A = <31, 41, 59, 26, 41, 58>
key = 59
i = 2
Iteration j = 4 and while loop: i = 3
A = <31, 41, 59, 26, 41, 58> becomes <31, 41, 59, 59, 41, 58>
key = 26
i = 3 becomes 2
Iteration j = 4 and while loop: i = 2
A = <31, 41, 59, 59, 41, 58> becomes <31, 41, 41, 59, 41, 58>
key = 26
i = 2 becomes 1
Iteration j = 4 and while loop: i = 1
A = <31, 41, 41, 59, 41, 58> becomes <31, 31, 41, 59, 41, 58>
key = 26
i = 1 becomes 0
Iteration j = 4 and no while loop
A = <31, 31, 41, 59, 41, 58> becomes <26, 31, 41, 59, 41, 58>
key = 26
i = 0
Iteration j = 5 and while loop: i = 4
A = <26, 31, 41, 59, 41, 58> becomes <26, 31, 41, 59, 59, 58>
key = 41
i = 4 becomes 3
Iteration j = 5 and and no while loop (because it is not the case that 41 > 41)
A = <26, 31, 41, 59, 59, 58> becomes <26, 31, 41, 41, 59, 58>
key = 41
i = 3
Iteration j = 6 and while loop: i = 5
A = <26, 31, 41, 41, 59, 58> becomes <26, 31, 41, 41, 59, 59>
key = 58
i = 5 becomes 4
Iteration j = 6 and no while loop
A = <26, 31, 41, 41, 59, 59> becomes <26, 31, 41, 41, 58, 59>
key = 58
i = 4
== 2 ==
LINEAR SEARCH:
Write the pseudo-code for an algorithm that takes in input two arguments: an array of numbers and a number v.
And returns a number i, if the first occurrence of v in the array is at position i, or 0 otherwise.
LINEAR-SEARCH(A,v)
for j = 1 to A.length
if A[j] == v
return j
return 0
== 3 ==
Consider the problem of finding the maximal number in a sequence of numbers.
Describe the problem in a mathematical way based on Input - Output as the Textbook does for the sorting problem at the beginning of Section 2.1.
Problem: finding the maximal number in a sequence of numbers
Input: a sequence of numbers.
Output: a_i with 1 <= i <= n, such that a_j <= a_i for all j s.t. 1 <= j <= n
FIND-MAX:
Write the pseudo-code for an algorithm that takes in input an array of numbers and returns the maximal element.
FIND-MAX(A)
answer = A[1]
for j = 2 to A.length
if A[j] > answer
answer = A[j]
return answer
== 4 ==
Correctness of FIND-MAX:
Argue for the correctness of the algorithm of Exercise 3 (FIND-MAX) by providing an invariant for the loop you have used,
and informally explaining why the properties Initialization, Maintenance, and Termination (page 19 of the Textbook) hold when applied to your algorithm and that loop invariant.
Loop Invariant: At the start of the iteration j of the loop, the variable answer contains the max of all numbers in subarray A[1 ... j-1].
Initialization: when j = 2, the subarray A[1 ... j-1] is subarray A[1 ... 1], that is the array with the only element A[1]. Since answer = A[1] the Loop Invariant holds.
Maintenance: answer contains the max of all numbers of the subarray A[1 ... j-1]. If A[j] <= answer, then we have that answer is the max of all numbers of the subarray A[1 ... j], which is the subarray that the next iteration will work with. If A[j] > answer then the algorithm sets answer to be A[j]. As A[j] > answer we have that A[j] is greater than all the numbers in A[1 ... j-1] because answer was, and A[j] > answer. As we have A[j] >= A[j], then if we take the subarray A[1 ... j] we have that A[j] is the max of that subarray.
Termination: At the end of the loop, we have j = (A.length + 1). Therefore, we know that Loop Invariant holds for the subarray A[1 ... (A.length +1 -1)], that is A[1 ... A.length]. But that is the array in input, and since the Loop Invariant holds for that array it means that the variable answer contains the max of all numbers of the array in input.