Loop Invariant Proofs (20 points) Consider the pseudocode below for the unranking algorithm presented in lecture 9. rI'he input is P: the rank or position of the string that we would like to unrank, n: the length of the string, and k: the number of ones or density of the binary string. The output is a list of distinct integers pk, pk_1, . . . 392, p1 in decreasing order, such that P : 2:621 (19') n and la: are both positive integers with k g n, and P is 2' R an integer between D and (k) 1, inclusive. procedure Unrank(P: rank or position string, n: length of string, k: number of ones (density)) 1. r : P / / remainder term 2. i = k: 3. 5r. : n 4. pTE'UIHOlBLI' : n + 1 5. p : vector of size k f/initialized to 1s 6. While (if > 0) 7. p-re'UI-ndex : :r f/index of previous 1 in string, or k if no ls have been placed 8. :r. 2 largest integer such that (:7) g r 9. p[i] : a: 10. r : r i (if) 11. i = 2' 1 12. return p A {-'D \\_J (5 points) Use induction to prove the following loop invariant, where T, is the remainder term after t iterations: After 16 iterations, (b) (C) (d) (5 points) Use induction to prove the following loop invariant: After t iterations, rt