I will post the codes to work with at the end of the qestions. Use PYTHON programing. Thank you!

starterfile.py

# PART A def factorial(n): """ Recursive factorial function. """ pass

def C(n,k): """ Calculates binomial coefficient from formula (2). """ pass

# PART B def DC(n,k): """ Divide-and-Conquer recursive binomial coefficient (formula (3)). """ pass

# PART C def DP(n, k): """ Dynamic Programming binomial coefficient using a list of lists to store rows of Pascal's triangle. """

# Initial two rows of Pascal's triangle pascalsTriangle = [[1], [1,1]]

for row in range (2,n+1) : nextRow = [1] # 1 in column 0

# Inner for-loop to calculate the middle portion of the next row for c in range (1,row): pass # COMPLETE THIS LINE OF CODE

nextRow.append(1) # 1 along diagonal

# Add nextRow to pascalsTriangle pascalsTriangle.append(nextRow) # COMPLETE THE RETURN STATEMENT BY RETURNING THE C(n, k) ITEM REQUESTED return

finonnaci.py

def fib(n): """ Recursive divide-and-conquer algorithm. """ if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2)

def fib_DP(n): """Dynamic programming solution to find the nth number in the Fibonacci seq."""

# List to hold the solutions to the smaller problems fibonacci = []

# Step 1: Store base case solutions fibonacci.append(0) fibonacci.append(1)

# Step 2: Loop from base cases to biggest problem of interest for position in range(2, n+1): fibonacci.append(fibonacci[position-1] + fibonacci[position-2])

# return nth number in the Fibonacci sequence return fibonacci[n]

def fib_DP2(n): """Dynamic programming solution to find the nth number in the Fibonacci seq. that uses minimal storage.""" if n

return next

Part A: We've seen several recursive divide-and-conquer" algorithms: fibonacci and coin-change problem. The general idea of divide-and-conquer algorithms is * dividing the original problem it into small problem(s) (e.g., fib(n-1) and fib(n-2) * solving the smaller problem(s) recursively . combine the solution(s) to smaller problem(s) to solve the original problem (e.g., return fib(n-1) + fib(n-2)) Mathematics has several simple recursively defined functions. For example, the factorial function can be recursively defined as: n! = n * (n- 1)! for n 21, and Implement a recursive factorial (n) function using this recursive definition and test it with several small examples (e.g., 3-3*2! = 3*2*1 ! = 3*2*1#0! = 3*2*1*1 = 6, and 5! = 5*4*3*2*1*1 = 120) In Discrete Structures (CS 1800) you used (or will use) the binomial coefficient formula: C(n, k) = k!(n-k)! to calculate the number of combinations of "n choose k, i.e., the number of ways to choose k objects from n objects. For example, when calculating the number of unique 5-card hands from a standard 52-card deck (e.g. C(52, 5)) we need to calculate 521/ 5:47! = 2,598,960 Implement the function C(n, k) using formula (2) above and your recursive factorial function. PartB: One problem with using formula (2) in most languages is that n! grows very fast and overflows the integer representation before you can do the division to bring the value back to a value that can be represented. (NOTE: Python does not suffer from this problem, but lets pretend that it does.) For example, when calculating C(52, 5) we need to calculate 52! /5! 47!. However, the value of 52 80,658, I 75. I 70,943,878,571 .660,636,856,403 ,766,975,289,505,440,883,277,824,000,000,000,000 is much, much bigger than can fit into a 64-bit integer representation. Fortunately, another way to view C(52, 5) is recursively by splitting the problem into two smaller problems by focusing on the hands containing a specific card, say the ace of clubs, and the hands that do not contain the ace of clubs For those hands that do contain the ace of clubs, we need to choose 4 more cards from the remaining 51 cards, i.e., C(51,4). For those hands that do not contain the ace of clubs, we need to choose 5 cards from the remaining 51 cards, i.e., C(51, 5). Therefore, C(52, 5)-C(51, 4) + C(51, 5) In general, (NOTE: When implementing your recursive code, be sure to use DC for the recursive calls) Cin. k) = C(n-1 , k-l ) + C(n-1 , k) C(n, k)= 1 for 1sks (n 1), and for k 0 or k =n Implement the recursive "divide-and-conquer" binomial coefficient function using equation (3). Call your function DC (n, k) for "divide-and-conquer". Notice the difference in run-time between calculating the binomial coefficient using C(24, 12) vs. DC(24, 12), C(26, 13) vs. DC(26, 13), and C(28, 14) vs. DC(28, 14) Part C: Much of the slowness of your "divide-and-conquer" binomial coefficient function, DC(n, k), is due to redundant calculations performed due to the recursive calls. For example, the recursive calls associated with DC(5, 3)10 would be: Part A: We've seen several recursive divide-and-conquer" algorithms: fibonacci and coin-change problem. The general idea of divide-and-conquer algorithms is * dividing the original problem it into small problem(s) (e.g., fib(n-1) and fib(n-2) * solving the smaller problem(s) recursively . combine the solution(s) to smaller problem(s) to solve the original problem (e.g., return fib(n-1) + fib(n-2)) Mathematics has several simple recursively defined functions. For example, the factorial function can be recursively defined as: n! = n * (n- 1)! for n 21, and Implement a recursive factorial (n) function using this recursive definition and test it with several small examples (e.g., 3-3*2! = 3*2*1 ! = 3*2*1#0! = 3*2*1*1 = 6, and 5! = 5*4*3*2*1*1 = 120) In Discrete Structures (CS 1800) you used (or will use) the binomial coefficient formula: C(n, k) = k!(n-k)! to calculate the number of combinations of "n choose k, i.e., the number of ways to choose k objects from n objects. For example, when calculating the number of unique 5-card hands from a standard 52-card deck (e.g. C(52, 5)) we need to calculate 521/ 5:47! = 2,598,960 Implement the function C(n, k) using formula (2) above and your recursive factorial function. PartB: One problem with using formula (2) in most languages is that n! grows very fast and overflows the integer representation before you can do the division to bring the value back to a value that can be represented. (NOTE: Python does not suffer from this problem, but lets pretend that it does.) For example, when calculating C(52, 5) we need to calculate 52! /5! 47!. However, the value of 52 80,658, I 75. I 70,943,878,571 .660,636,856,403 ,766,975,289,505,440,883,277,824,000,000,000,000 is much, much bigger than can fit into a 64-bit integer representation. Fortunately, another way to view C(52, 5) is recursively by splitting the problem into two smaller problems by focusing on the hands containing a specific card, say the ace of clubs, and the hands that do not contain the ace of clubs For those hands that do contain the ace of clubs, we need to choose 4 more cards from the remaining 51 cards, i.e., C(51,4). For those hands that do not contain the ace of clubs, we need to choose 5 cards from the remaining 51 cards, i.e., C(51, 5). Therefore, C(52, 5)-C(51, 4) + C(51, 5) In general, (NOTE: When implementing your recursive code, be sure to use DC for the recursive calls) Cin. k) = C(n-1 , k-l ) + C(n-1 , k) C(n, k)= 1 for 1sks (n 1), and for k 0 or k =n Implement the recursive "divide-and-conquer" binomial coefficient function using equation (3). Call your function DC (n, k) for "divide-and-conquer". Notice the difference in run-time between calculating the binomial coefficient using C(24, 12) vs. DC(24, 12), C(26, 13) vs. DC(26, 13), and C(28, 14) vs. DC(28, 14) Part C: Much of the slowness of your "divide-and-conquer" binomial coefficient function, DC(n, k), is due to redundant calculations performed due to the recursive calls. For example, the recursive calls associated with DC(5, 3)10 would be