For exercises 2 and 3, you can use the keyword "return" in pseudo-code, which ends the procedure and returns a result.
== 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.
== 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.
== 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.
FIND-MAX:
Write the pseudo-code for an algorithm that takes in input an array of numbers and returns the maximal element.
== 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.