You are playing a board game in which you move your pawn along a path of n fields. each field has a number l on it. in each move, if your field carries the number l, then you can choose to take any number of steps between 1 and l. you can only move forward, never back. your goal is to reach the last field in as few moves as possible. below we've written a recursive algorithm to find the optimal strategy for a given board layout. the input to the algorithms is an array board containing the numerical value in each field. the first field of the game corresponds to board [0] and the last to board [n-1]. here we use python or range so range(a, b) consists of integers from a to b-1 inclusively. recursive_moves (array board, int l, int n ): # board has length n and contains only positive integers. if l == n-1: return 0 min_so_far = float('inf') for i in range (l + 1, min(l + board [l] +1, n)): moves = recursive_moves (board, i, n) if (moves + 1 < min_so_far): min_so_far = moves + 1 return min_so_far 1.1. (1 pt.) run recursive moves (board, o, len(board)) with the input array (1,3,6, 3, 2, 3, 9,5). write down a list of all the distinct calls to the function (making sure to note the value of input l) and the return values. it's ok to "memoize" as you go. 1.2. (2 pts) show that the algorithm is correct. it will to formulate a claim of the form: "on input l, the algorithm correctly finds the number of moves needed to get from position x to position y of the board" (for some values of x and y that depend on l). 1.3. (1 pts.) show that the running time of recursive moves (board, 0, len(board)) (as written, with no memoization) on an input array of size n is 12(2"). 1.4. (1 pts) for how many distinct values of the inputs will the algorithm make recursive calls on inputs of size n? 1.5. (3 pts.) write pseudocode (or working code) for a memoized version of the recursive moves procedure that runs in polynomial time. 1.6. (3 pts.) write pseudocode (or working code) for a nonrecursive "bottom-up" version of the recursive moves procedure that runs in polynomial time. note that "bottom-up" here does not necessarily mean in increasing order of l; it means from the simplest subproblems to the most complicated ones. (hint: you might want to program your algorithms yourself to test them. they should be short and esay to code. 1.7. (1 pts.) analyze the asymptotic worst-case running time of your algorithms on input arrays of size n. (the two algorithms will probably be the same).