CSE 2320 - Homework 5

CSE 2320 - Homework 5 
Total points: 100 Topics: Recurrences , solved with methods: Master Theorem, Tree, Substitution (induction)
𝐶𝑜𝑛𝑣𝑒𝑛𝑡𝑖𝑜𝑛: ⌈ ⌉ 𝑚𝑒𝑎𝑛𝑠 𝑟𝑜𝑢𝑛𝑑𝑒𝑑 𝑢𝑝 𝑎𝑛𝑑 ⌊ ⌋ 𝑚𝑒𝑎𝑛𝑠 𝑟𝑜𝑢𝑛𝑑𝑒𝑑 𝑑𝑜𝑤𝑛.
P1. (23 points) Use the tree and table method to compute the Θ time complexity for
 
3 T(N) 5T( N / 4 )  2N .
Assume T(0) = 1 and T(1) = 1. Fill in the table below and finish the computations outside of it:
Level Argument/
Problem size
Cost of one
node
Nodes per
level
Cost of whole level
0
1
2
i
k=
Leaf level.
Write k as a
function of N.

Total tree cost calculation: ……………………………………………………………….
T(N) = Θ(…………………)
Draw the tree. Show levels 0,1,2 and the leaves level. Show the problem size T(…) as a label next to the node and inside
the node show the local cost (cost of one node) as done in class. For the leaf level and level 2 it suffices to show a few
nodes.
P2. (23 points) Use the tree and table method to compute the Θ time complexity for 𝑇(𝑁) = 4𝑇(𝑁 − 5) + 7. Assume
T(N) = 1 for all 0≤N≤4. Assume N is a convenient value for your computations.
Fill in the table below and finish the computations outside of it:
Level Argument/
Problem
size
Cost of one
node
Nodes per
level
Cost of whole level
0
1
2
i
k=
Leaf level.
Write k as a
function of N.

Total tree cost calculation: ……………………………………………………………….
T(N) = Θ(…………………)
Draw the tree. Show levels 0,1,2 and the leaves level. Show the problem size T(…) as a label next to the node and inside
the node show the local cost (cost of one node) as done in class. For the leaf level and level 2 it suffices to show a few
nodes.
P3. (36 points) Can you use the Master Theorem to solve the recurrences below? If yes, solve it with this method, if no,
show why you cannot use it.
a)
 
3 T(N) 5T( N / 4 )  2N
. Assume T(0) = 1 and T(1) = 1.
b)
T(N) 4T(N / 4)  d
, for some constant d0. Assume T(0) = 1 and T(1) = 1.
c) 𝑇(𝑁) = 6𝑇(𝑁/6) + 5𝑁, Assume T(0) = 1 and T(1) = 1.
d) 𝑇(𝑁) = 8𝑇(𝑁/2) + 𝑐𝑁
3
𝑙𝑔𝑁 , Assume T(0) = 1, and T(1) = 1 .
P4. (4 points) Go to the Wikipedia webpage https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) .
See section “Inadmissible equations” and list the equation and the reason why it does not satisfy the Master Theorem
requirements.
P5. (14 points) Show that
T(N) 5T( / 4) 2 ( )
3 3
 N  N   N
by showing that it is
( )
3 O N
and also
( )
3  N
. Assume
T(0) = 1 and T(1) = 1
a) (9 points) Use the induction method to show O(N3
). As done in class, start with the inductive step and then
check and refine for enough low values of N until the inductive step can be applied (See lecture from Wed, Oct
11).
b) (5 points) Use just the definition with c and n0 to show that it is Ω(N3
). Assume that T(N)≥0, for all N≥0. You
should not need to use induction. (It is easier without induction.)
Write your answers in a document called 2320_H5.pdf. It can be hand-written and scanned, but it must be uploaded
electronically. Submit just the 2320_H5.pdf.
Remember to include your name at the top.