(20%) Dymamic Programming: You are given an exam with questions numbered 1,2,3,...,n. Each question i is...

Transcribed Image Text:

(20%) Dymamic Programming: You are given an exam with questions numbered 1,2,3,...,n. Each question i is worth p, points. You must answer the questions in order, but you may choose to skip some questions. The reason you might choose to do this is that even though you can solve any individual question i and obtain the p, points, some questions are so frustrating that after solving them you will be unable to solve any of the following f. questions. Suppose that you are given the p, and f, values for all the questions as input. Your goal is to score the maximum amount of points (assume that if you answer a question, your answer is always correct and you score the full p.). (a) (5%) Show the optimal solution for the following set of questions. Indicate the number of points you score and the questions you choose to answer. For any question fill in Y or N in the table below. depending on whether you solve it or not. 1 2 3 4 10 0 Question Pi f Solved? (Y/N) 5 30 20 15 25 1 2 1 0 Total number of points you score: (b) (5%) Devise a recursive (later to become DP) formula to select the optimal score. Notice that it is rather similar to a question in HW4 - for each i, define OPT(i) as the optimal number of points you score for questions 1, 2,...i. When calculating OPT(i) you may either select a question i or not. If so collect the points and optimize on the remaining questions, skipping f. Otherwise, optimize starting from i+1. Notice that the recursion goes from 1 to n, so in the end you return OPT(1). if i>n (boundary) SOPT(i)= max(- -), Otherwise (c) (5%) Write the OPT(i) for the example below. Use the table for your convenience: Question 1 2 3 4 5 Pi 10 30 20 15 25 0 1 2 1 0 OPT(1) (d) (5%) What is the runtime of the DP algorithm as a function of n, the number of questions? Explain briefly. (20%) Dymamic Programming: You are given an exam with questions numbered 1,2,3,...,n. Each question i is worth p, points. You must answer the questions in order, but you may choose to skip some questions. The reason you might choose to do this is that even though you can solve any individual question i and obtain the p, points, some questions are so frustrating that after solving them you will be unable to solve any of the following f. questions. Suppose that you are given the p, and f, values for all the questions as input. Your goal is to score the maximum amount of points (assume that if you answer a question, your answer is always correct and you score the full p.). (a) (5%) Show the optimal solution for the following set of questions. Indicate the number of points you score and the questions you choose to answer. For any question fill in Y or N in the table below. depending on whether you solve it or not. 1 2 3 4 10 0 Question Pi f Solved? (Y/N) 5 30 20 15 25 1 2 1 0 Total number of points you score: (b) (5%) Devise a recursive (later to become DP) formula to select the optimal score. Notice that it is rather similar to a question in HW4 - for each i, define OPT(i) as the optimal number of points you score for questions 1, 2,...i. When calculating OPT(i) you may either select a question i or not. If so collect the points and optimize on the remaining questions, skipping f. Otherwise, optimize starting from i+1. Notice that the recursion goes from 1 to n, so in the end you return OPT(1). if i>n (boundary) SOPT(i)= max(- -), Otherwise (c) (5%) Write the OPT(i) for the example below. Use the table for your convenience: Question 1 2 3 4 5 Pi 10 30 20 15 25 0 1 2 1 0 OPT(1) (d) (5%) What is the runtime of the DP algorithm as a function of n, the number of questions? Explain briefly.

Answer rating: 100% (QA)

To Design an O n algorithm for choosing set of questions to answer that maximizes your total points for the given problem To solve this problem we can use a dynamic programming approach Lets define th... View the full answer