{ "key_pair_value_system": true, "answer_rating_count": "", "question_feedback_html": { "html_star": "", "html_star_feedback": "" }, "answer_average_rating_value": "", "answer_date_js": "2024-09-13T00:08:35-04:00", "answer_date": "2024-09-13 00:08:35", "is_docs_available": "", "is_excel_available": "", "is_pdf_available": "", "count_file_available": 0, "main_page": "student_question_view", "question_id": "10523967", "url": "\/study-help\/questions\/introduction-in-class-we-have-been-introduced-to-dynamic-programming-10523967", "question_creation_date_js": "2024-09-13T00:08:35-04:00", "question_creation_date": "Sep 13, 2024 12:08 AM", "meta_title": "[Solved] Introduction In class we have been introd | SolutionInn", "meta_description": "Answer of - Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing probl | SolutionInn", "meta_keywords": "introduction,class,introduced,dynamic,programming,solving,problems,subdividing,subproblems,similar,structure,original", "question_title_h1": "Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing problems into subproblems similar in structure to", "question_title": "Introduction In class we have been introduced to dynamic programming as a", "question_title_for_js_snippet": "Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing problems into subproblems similar in structure to the original problem In addition to this standard property, subproblems must 1) overlap and 2) have optimal sub structure The basic idea of dynamic programming is to obtain the optimal problem by exploiting the fact that it can be obtained from optimal solutions to subproblems and that we can save time by keeping track of subproblems we have already solved Problem 1 The Fibonacci Numbers There are many problems that can benefit from the ideas that go into dynamic programming, even if they are not naturally dynamic programming problems Consider the Fibonacci numbers, defined by the recurrence F F 1 F 2 n 2,3, , F F 1 3 1 Lab 3 Dynamic Programming February 10, 2020 As discussed in class, this problem has overlapping subproblems It does not, however, have optimal substructure because calculating the Fibonacci numbers is not an optimization problem Nevertheless, the concept of memoization can be applied to this problem with dramatic effects on performance Functions A) Implement a function called recursiveFibonacci that, given an integer n, evaluates and returns F recursively without memoization) B) Implement a function called memoizedFibonacci that, given an integer n, evaluates and returns Frecursively with memoization You may add whatever arguments you require, or a wrapper function as necessary, to make the memoized version of the function work to your liking C) Implement a function called bottomupFibonacci that, given an integer n evaluates and returns F in a bottom up manner Main Program Write a main program Lab 3 Problem 1 that specifies an array of values of n and collects the running times for your three functions A, B, and C for computing the Fibonacci numbers as a function of n Data Collection and Analysis Once you have completed writing your functions and main program you need to Call your main program on appropriate values of n to get the general trends of the computational costs of each method for computing the nth Fibonacci number Determine the best Big O notation fit for each of the three approaches Show your work Remember that operation counting and order of growth is always a possibility For each of the three approaches, plot the analytic and measured costs times and the output of the main program in one figure, producing 3 total plots Scale the curves appropriately and provide details in the legend Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing problems into subproblems similar in structure to the original problem In addition to this standard property, subproblems must 1) overlap and 2) have optimal sub structure The basic idea of dynamic programming is to obtain the optimal problem by exploiting the fact that it can be obtained from optimal solutions to subproblems and that we can save time by keeping track of subproblems we have already solved Problem 1 The Fibonacci Numbers There are many problems that can benefit from the ideas that go into dynamic programming, even if they are not naturally dynamic programming problems Consider the Fibonacci numbers, defined by the recurrence F F 1 F 2 n 2,3, , F F 1 3 1 Lab 3 Dynamic Programming February 10, 2020 As discussed in class, this problem has overlapping subproblems It does not, however, have optimal substructure because calculating the Fibonacci numbers is not an optimization problem Nevertheless, the concept of memoization can be applied to this problem with dramatic effects on performance Functions A) Implement a function called recursiveFibonacci that, given an integer n, evaluates and returns F recursively without memoization) B) Implement a function called memoizedFibonacci that, given an integer n, evaluates and returns Frecursively with memoization You may add whatever arguments you require, or a wrapper function as necessary, to make the memoized version of the function work to your liking C) Implement a function called bottomupFibonacci that, given an integer n evaluates and returns F in a bottom up manner Main Program Write a main program Lab 3 Problem 1 that specifies an array of values of n and collects the running times for your three functions A, B, and C for computing the Fibonacci numbers as a function of n Data Collection and Analysis Once you have completed writing your functions and main program you need to Call your main program on appropriate values of n to get the general trends of the computational costs of each method for computing the nth Fibonacci number Determine the best Big O notation fit for each of the three approaches Show your work Remember that operation counting and order of growth is always a possibility For each of the three approaches, plot the analytic and measured costs times and the output of the main program in one figure, producing 3 total plots Scale the curves appropriately and provide details in the legend", "question_description": "