COMP 3711 Design and Analysis of Algorithms
Tutorial 3: Divide and Conquer
Master Theorem: Quick Revision
Copyright By PowCoder代写 加微信 powcoder
Recall the version of the Master Theorem for equalities.
1’.If 2’.If 3’.If
be constants.
forsome
=>T => T
forsome
(*with an additional condition)
for some => T
. This can be replaced by
Master Theorem: Quick Revision
Recall the version of the Master Theorem for inequalities.
be constants.
forsome
forsome
=>T => T
Using the Master Theorem, give asymptotic tight bounds for .
=>T => T
1.If forsome 2.If
This is case 3 because
𝑓 𝑛 = 𝜃 𝑛
3.If forsome => T (*with an additional condition)
Using the Master Theorem, give asymptotic tight bounds for .
=>T => T
forsome
(*with an additional condition)
forsome
This is case 1 because . 𝑓𝑛 =𝜃𝑛
1’.If𝑘<𝑐=>T𝑛 =𝜃𝑛 2’.If𝑘=𝑐=>T𝑛 =𝜃𝑛log𝑛 3’.If𝑘>𝑐=>T𝑛 =𝜃𝑓(𝑛) =𝜃𝑛
Using the Master Theorem, give asymptotic tight bounds for
-> case 2
-> case 3
1’.If𝑘<𝑐=>T𝑛 =𝜃𝑛 2’.If𝑘=𝑐=>T𝑛 =𝜃𝑛log𝑛 3’.If𝑘>𝑐=>T𝑛 =𝜃𝑓(𝑛) =𝜃𝑛
Using the Master Theorem, give asymptotic tight bounds for . (f)
-> case 3
-> case 3
Using the Master Theorem, give asymptotic tight bounds for (i)
forsome
forsome
(*with an additional condition)
This is case 1.
Note: You cannot use this conclusion for
Question: Polynomial Evaluation
The input to this problem is a set of
coefficients: .
Define Example:
(a) Given value x, how can you evaluate multiplications and additions?
with at most Native solution: calculate each term and add them up.
Calculating takes multiplications. In total, it takes
multiplications.
=> No need to calculate multiple times.
Record the value of each and use them to derive .
In total, it takes multiplications and additions. (calculate all 𝑥,𝑖 > 0)(calculate 𝑎 𝑥,𝑖 > 0)
The requirement is still not satisfied.
Note that:
Solution (cont’d)
𝐴𝑥 =𝑎𝑥=𝑎 +𝑥(𝑎 +𝑥(𝑎 +𝑥(···(𝑎 +𝑥(𝑎+𝑥𝑎)···):
Set and, for
This permits evaluate
n additions and n multiplications.
using This method is known as Horner’s rule.
(b) Now suppose that evaluate using
Hint. evaluate using
Going Further
has at most k non-zero terms. How can you operations.
operations (how?)
Going Further
Any can be calculated with a series of .
Solution (cont’d)
Step-1: precompute and store the values , .
Step-2: calculate and use { } to evaluate Any can be calculated in
precomputed .
=> can be computed in a total
time using the
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com