提供高质量的essay代写,Paper代写,留学作业代写-天才代写

首頁 > > 詳細

program編程代寫、c++,Python程序代做、代寫algorithm編程代做R語言編程|代寫Python編程

Homework 9
(Maximum 50 points)
Due 11:59 pm Friday April 9, 2021
Show the steps of deriving your answers. Points will be deducted for answers without adequate
steps discussed. Submit your homework via Blackboard as one PDF or Word document.
1. (25) [Fibonacci: memoization] The objective of this exercise is to run through a “full course”
of implementing a recursive function that, when evaluated, incurs significant overlapping
intermediate computations (typical of an optimal substructure in dynamic programming);
specifically, we will first remove redundant overlapping computations via memoization and then
remove the overhead of recursion via iteration. Let’s go!
Consider the Fibonacci sequence defined as a recursive mathematical function as follows:
??(??) = {
0 if ?? = 0
1 if ?? = 1
??(?? − 1) + ??(?? − 2) if ?? ≥ 2
a) Write a recursive program function, “Fib(i)”, which, given an input integer i, computes a
Fibonacci number according to the mathematical definition above (by calling Fib(n)).
b) Write a recurrence relation that expresses the run-time T(n) of evaluating Fib(n), and solve it
to show that T(n) is exponential with n. A formal proof of run-time complexity is not
necessary. Hints: (1) the Fibonacci number can be approximated as ??(??) ≈
[????]
√5
= Θ(??
??
)
where ? is the golden ratio (= 1+√5
2
= 1.61803…) and [·] denotes rounding to the nearest
integer; you can take advantage of this fact to derive that T(n) is exponential with n without
actually solving he recurrence relation; (2) the specific values of constants in the base cases
of a recurrence relation have no effect on the resulting big-O solution, so can be set to
arbitrary values as convenient for our purpose.
c) Rewrite the recursive program function Fib(i) from the exercise a by introducing
memoization array M[0..n]. Name the resulting function MFib (we call MFIb(n)).
d) Write your analysis of the run-time of MFib(n) from the exercise c and state the resulting
run-time complexity in the asymptotic big-O function of n. We do not need a recurrence
relation for this analysis. Hint: see the run-time analysis of the memorized recursive function
of Weighted Interval Scheduling in the lecture slide.
e) Rewrite the memoized recursive program function MFib(i) as a memoized iterative function.
Name the resulting function IFib; we call IFib(n)
2. (25) [Weighted Interval Scheduling: algorithm tracing] Consider the dynamic
programming algorithm we discussed for the weighted interval scheduling problem. Run the
bottom-up (i.e., iterative) implementation of the algorithm on the problem instance shown below.
Show the algorithm trace in the same manner as in Figure 6.5(a) and (b) (page 260) of the
textbook -- specifically, show in your answer:
a) The plot of sorted jobs.
b) The list of values of p(i) for each job i (i=1..8). (Note the job numbers here are the numbers
after the sorting.)
c) The memorization table (array) filled in after each iteration of the algorithm, with arrows
pointing to the array entries containing solutions to the two subproblems.
d) The set of jobs selected as a result. (There are two alternative sets of jobs that are optimal;
either one can be given as the answer.)
Last modified: April 1, 2021

聯系我們
  • QQ:1067665373
  • 郵箱:1067665373@qq.com
  • 工作時間:8:00-23:00
  • 微信:Badgeniuscs
熱點文章
程序代寫更多圖片

聯系我們 - QQ: 1067665373 微信:Badgeniuscs
? 2021 uk-essays.net
程序代寫網!

在線客服

售前咨詢
售后咨詢
微信號
Essay_Cheery
微信
全优代写 - 北美Essay代写,Report代写,留学生论文代写作业代写 北美顶级代写|加拿大美国论文作业代写服务-最靠谱价格低-CoursePass 论文代写等留学生作业代做服务,北美网课代修领导者AssignmentBack 北美最专业的线上写作专家:网课代修,网课代做,CS代写,程序代写 代码代写,CS编程代写,java代写北美最好的一站式学术代写服务机构 美国essay代写,作业代写,✔美国网课代上-最靠谱最低价 美国代写服务,作业代写,CS编程代写,java代写,python代写,c++/c代写 代写essay,作业代写,金融代写,business代写-留学生代写平台 北美代写,美国作业代写,网课代修,Assignment代写-100%原创 北美作业代写,【essay代写】,作业【assignment代写】,网课代上代考