fori:- 1 toj COT 3100 Intro. To Discrete Structures Homework #8 Statements in the body of the inner loop, none containing branching statements that lead outside the loop] next i Problem 1: Assume that n is a positive integer. For each of the following algorithm segments, how many times will the innermost loop be iterated when the algorithm segment is implemented and run? (5 points for each) 1. for k 1 to n next j next k forj:- 1 tok 6. for k:-1 to n Statements in the body of the inner loop, none containing branching statements that lead outside the loop) forj:1 to k-1 fori: 1 toj-1 next [Statements in the body of the inner loop, none containing branching statements that lead outside the loop] next k 2. fork1 to n-1 next i forj1 to k+1 next next k Statements in the body of the inner loop, none containing branching statements that lead outside the loop) Problem 2 (10 points): Suppose a sequence satisfies the below given recurrence relation and initial conditions sequence next . Find an explicit formula for the next k 3. for k- 1 ton-1 ak 2ak-1 +3ak-3 for all integers k2 2 forj:k+1 to n Statements in the body of the inner loop, none containing branching statements that lead outside the loop] Problem 3 (10 points): Suppose a sequence satisfies the below given recurrence relation and initial conditions. Find an explicit formula for the sequence next a,-69-1-9ak-2 for all integers k 2 next k 4 fork:-1 ton-1 forj:k to n Statements in the body of the inner loop, none containing branching statements that lead outside the loop] Submission Requirements The following requirements are for electronic submission via Canvas. ? Your solutions must be in a single file with a file name yourname-hw8. next Upload the file by following the link where you download the homework description on Canas. next k If scanned from hand-written copies, then the writing must be legible, or loss 5. for k- 1 to n of credits may occur Only submissions via the link on Canvas where this description is downloaded forj:1 to k are graded. Submissions to any other locations on Canvas will be ignored