Consider the problem of converting an array A of n elements into a single linked list, where the head of the list points to A(1). 1 Write a recursive solution for the above problem 2 Write a non-recursive solution using loops. Identify the loop invariant (LI) = condition that is true at the beginning of each loop 3 Prove correctness of the recursive solution using induction. Clearly state the claim, base case and the induction step

In pseudocode like below and word description

procedure Find(L; x) if (L =nil) then return nil else if (L.data = x) then return L else return Find(L.next; x)

procedure InsertHead(L; x) ** inserts a new node whose ** data = x as L's new head new new node new.data x new.next head head new

example:

Step 2: Proving Loop Invariants Example #1 procedure FindSum(A, n) sum A[1] 2 while (j