Question: In this assignment, you have to implement a Dynamic Programming solution to find the n_th terms value of the following recurrence relation. Recurrence relation will

In this assignment, you have to implement a Dynamic Programming solution to find the n_th terms value of the following recurrence relation. Recurrence relation will depend on YOUR ROLL NUMBER. Your recurrence relation will use the first four digits of your roll number. Suppose your roll number is 181014036. Eg. f(n) = 1*f(n-1) + 8*f(n-2) + 1*f(n-3) + 0*f(n-4) Base cases will be the reversed four digits of roll number. Eg. f(0) = 6, f(1) = 3, f(2) = 0, f(3) = 4 You will be provided with a sample code. Edit the functions of the sample code file.

QUESTION

Implement a Top-Down (Recursion + Memoization/Caching) solution [You can use a Map/Array/other data structure for caching purpose] [10] ** Complete the recursiveTopDown(int n) function

Edit your functions so that your code can be runnable for recurrence relation, when used with any roll number.

What is the time and space complexity of the recursiveTopDown(n) code ?

SAMPLE CODE

#include  #include  #include  using namespace std; // map cache; // you can use other data structures as well for caching. int recursiveTopDown(int n){ // base cases // Check if already exists in cache/result array -> simply return // recursion // insert into cache/result array before returning the ans return -1; // return answer here, instead of -1 } int bottomUp(int n){ return -1; // return answer here, instead of -1 } int bottomUpOptimizedSpace(int n){ return -1; // return answer here, instead of -1 } //////////////////////// MAIN FUNCTION FOR TESTING \\\\\\\\\\\\\\\\\\\\\\\\\\\\\ int main() { int n = 20; int ans; ans = recursiveTopDown(n); cout << "recursiveTopDown, n = " << n << ", ans = " << ans << endl; ans = bottomUp(n); cout << "bottomUp, n = " << n << ", ans = " << ans << endl; ans = bottomUpOptimizedSpace(n); cout << "bottomUpOptimizedSpace, n = " << n << ", ans = " << ans << endl; }

Please use cpp language and please explain line by line whole code

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Provide runnable(Also provide screenshots of running those code as proof) 2 different C++ code of this below Question. also Implement these 2 roll number for those 2 codes. Roll number: 201014071,...

In this assignment, you have to implement a Dynamic Programming solution to find the n_th term's value of the following recurrence relation. Recurrence relation will depend on YOUR ROLL NUMBER Your...

CSE 306 FALL-2021 Assignment-3 In this assignment, you have to implement a Dynamic Programming solution to find the n_th term's value of the following recurrence relation. Recurrence relation will...

Depreciation information for Corales Company is given in BE10-3. Assuming the declining-balance depreciation rate is double the straight-line rate, compute annual depreciation for the first and...

The following general ledger accounts are taken from the books of the Hynes Corporation at the end of its fiscal year, December 31, 2016: Required: 1. Label the debit and credit amounts that...

Suppose a ten - year, $ 1 comma 0 0 0 $ 1 , 0 0 0 bond with an 8 . 5 % 8 . 5 % coupon rate and semiannual coupons is trading for $ 1 comma 0 3 4 . 0 4 $ 1 , 0 3 4 . 0 4 . a . What is the bond's yield...

2. During a trip to the beach at 1atm, a car runs out of gasoline, and it becomes necessary to siphon gasoline out of the car of a Good Samaritan (FIGURE Q2). The siphon is a small-diameter hose and...

How do Data Types perform data validation?

How does Referential Integrity work?

What are Dimensional Relational Databases designed to hold primarily?