2.

Introduction This programming assignment is meant for practicing recursion, and this document will guide you to the final solution.

Description of problem

Alice and Bob saw an interesting matrix of size n*n online, and they decide to play a game based on this matrix. The game has four rules:

1. They will start from [0,0]

2. They could only move straight up or to the upper right slots.

3. When they are in the top row(i.e. row n-1), the game ends.

4. They will add up the numbers along the way. The one who has the highest score wins the game In the above example, the possible paths for the would be {10, 2, 4, 5}, {10, 3, 6, 9}, {10, 3, 5, 1}... Bob doesnt know what a good strategy would be to win the game, so he asks you to write a program to print all distinct possible sums of the paths he could take from the first row to the top role

Table 1: Example Map

5	1	9	10
4	5	6	0
2	3	0	0
10	0	0	0

Analysis of the problem

Recurrence Relation When you saw this problem, you decided to write a program just to enumerate all possible paths that Bob could travel. Suddenly, you think you could use what you just learned in COMP550 about recurrences to solve this problem.

a. Suppose you are at position[0][0], what would be the next possible moves for you? And could these be generalized to any coordinates[i][j]?(i representing rows and j representing columns)

b. Based on your answer for part 1, what would be the upper bound for the distinct number of solutions? Briefly explain how you get the answer

c. How would you generate a recurrence formula based on your analysis in parts 1 and 2? (Hint: Deciding where to go next is in constant time (1))

d. Based on your recurrence formula, what would be the tight asymptotic bound? (Answer should be in notation)

e. Could your recurrence formula be solved by using the Master Theorem?

Since this problem has a recurrence relation, it is much easier to use recursion to solve the problem. Following are some hints for solving the problem.

1. What would be the terminal condition for your program? 2. Think about how the recurrence formula above could it help you write the recursion method.

Inversions and Insertion-Sort Consider the insertion-sort algorithm given below (from CLRS): INSERTION-SORT (A,n) 12345678fori=2tonkey=A[i]//InsertA[i]intothesortedsubarrayA[1:i1].j=i1whilej>0andA[j]>keyA[j+1]=A[j]j=j1A[j+1]=key Let A[1..n] be an array of n distinct numbers. If IA[j], then the pair (i,j) is called an inversion of A. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your