Sale!

# Assignment: Dynamic Programming solution

\$30.00

Assignment: Dynamic Programming
1. Solve Dynamic Programming Problem and Compare with Naïve approach
You are playing a puzzle. A random number N will be given, you have blocks of length 1 unit
and 2 units. You need to arrange the blocks back to back such that you get a total length of N
units. In how many distinct ways can you arrange the blocks for given N.
a. Write a description of approach to solve it using Dynamic Programming paradigm
b. Implement a function blockpuzzle_dp(N) that solves this problem using Dynamic
Programming using either top-down or bottom-up approach
c. Write pseudocode for the brute force approach

Category:

## Description

5/5 - (1 vote)

Assignment: Dynamic Programming
1. Solve Dynamic Programming Problem and Compare with Naïve approach
You are playing a puzzle. A random number N will be given, you have blocks of length 1 unit
and 2 units. You need to arrange the blocks back to back such that you get a total length of N
units. In how many distinct ways can you arrange the blocks for given N.
a. Write a description of approach to solve it using Dynamic Programming paradigm
b. Implement a function blockpuzzle_dp(N) that solves this problem using Dynamic
Programming using either top-down or bottom-up approach
c. Write pseudocode for the brute force approach
d. Compare the time complexity of both the approaches
e. Write the recurrence formula for the problem
Example 1:
Input: N=2, Result: 2
Explanation: There are two ways. (1+1 , 2)
Example 2:
Input: N=3, Result: 3
Explanation: There are three ways (1+1+1, 1+2, 2+1)
2. Solve a problem using top-down and bottom-up approaches of Dynamic Programming
technique
Two players A & B are playing a game. The rules of the game are:
At the start one number N will be given. The player who starts would have to pick a
number i such that 0<i<N, the condition is that N%i == 0. The second player would pick a
number j from N-i, satisfying the condition 0<j<(N-i). And the game goes on until there is no
more possibility of making any selection. Each player would play in turns, and A always starts
the game. Assume both players play optimally.
Given a number N return if A would win the game or not.
Example 1:
Input: N=2, Result: True
Explanation: A choses 1, and B has no more numbers to chose
Example 2:
Input: N=3, Result: False
Explanation: A choses 1, B choses 1, and A has no more numbers to chose
a. Implement a solution to this problem using Top-down Approach of Dynamic
b. Implement a solution to this problem using Bottom-up Approach of Dynamic