Questionnaire COT 5407 – Introduction to Algorithms Homework Assignment #1 8 points, Due Sept. 15 (Tuesday) (Type your answers, save your answers as a pdf file with a cover page, submit it via Canvas)...

1 answer below »

a

Questionnaire COT 5407 – Introduction to Algorithms Homework Assignment #1 8 points, Due Sept. 15 (Tuesday) (Type your answers, save your answers as a pdf file with a cover page, submit it via Canvas) Problem 1 (2 points) Solving Recurrence Relations Draw the recursion tree for ??(??) = 9??(??/3) + ????, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound using the substitution method. Problem 2 (2 points) Solving Recurrence Relations Give asymptotic upper and lower bounds for T(n) in each of the following recurrences: (1) ??(??) = 7??(??/3) + ??2, (2) ??(??) = ??(?? − 1) + ?????? Problem 3 (4 points) Heapsort (1) (2 points) Show the sorting process on the array A = <6, 11,="" 2,="" 15,="" 3,="" 12,="" 18,="" 9,="" 4=""> using Heapsort; (2) (2 points) We can build a heap by repeatedly calling Max-Heap-Insert to insert the elements into the heap. Consider the following variation on the Build-Max-Heap procedure: Build-Max-Heap+(A) 1 A.heap-size = 1 2 for i = 2 to A.length 3 Max-Heap-Insert(A, A[i]) a. Build a max-heap on the array A in (1) using Build-Max-Heap+; b. Show that in the worst case, Build-Max-Heap+ requires Θ(n lg n) time to build an n-element heap.

hw1-1-otxbn1c1.pdf

Answered Same DaySep 04, 2021

Answer To: Questionnaire COT 5407 – Introduction to Algorithms Homework Assignment #1 8 points, Due Sept. 15...

Neha answered on Sep 13 2021

140 Votes

Question 1
Relation: T(n) = 9T(n/3) +cn
N
n/3 n/3 ….9 times…… n/3
n/9 …..9 times n/9 …..9 times n/9 …..9 times
.
.
1
Summation
∑log n-1 i=0 C X 9
i X n/3i
 C ∑log m-1 i=0 3i X n
Assume log = log3
 N X C ∑log m-1 i=0 3i
 N X C (3 log m-1+1 -1) / (3-1)
 N X C X 3log m -1/ 2
 N X C X (n-1) / 2
 CN2 – CN / 2
Assume K = C/2
K (N2 - N)
 O (N2)
, K is constant
Question 2
Question 2.1
Relation: T(n) = 7T (n/3) + n2
By master theorem
T(n) = aT (n/b) + f(n) with a>=1 and b>1
So, a = 7, b=3
Check f(n) = Ω (n log b
a + E)
n2 >= cnlog3
7 + E
n2 >= cn1.77 + E
For all E>1, This holds true assuming positive C
Check regularity condition
af(n/b) <= cf (n)
 a n2/ 9 <= cn2
 Holds true
Thus T(n) = O (f(n))
 O(n2)
Question 2.2
Relation: T(n) = T(n-1) + log n
n -> n-1 …… T (1)
Summation:
∑n i=1 Log i
 Log (1) + log (2) + …… log (n)
 Log (n X (n-1) X … X 1)
 Log (n!)
 O (log (n!))
Using striling approx.,
 O (nlogn)
Question 3.1 Heap Sort
6
/ \
11 2
/ \ / \
15 3 12 18
/ \
9 4

Algo: for( i = A.length()/2; i >=1; i--;)
Shiftdown();

6 6 6
/ \ / \ / \
11 2 11 18 15 18
/ \ / \ => / \ / \ => / \ / \
15 3 12 18 15 3 12 2 11 3 12 2
/ \ / \ / \
9 4 9 ...

SOLUTION.PDF

Questionnaire COT 5407 – Introduction to Algorithms Homework Assignment #1 8 points, Due Sept. 15 (Tuesday) (Type your answers, save your answers as a pdf file with a cover page, submit it via Canvas)...

Answer To: Questionnaire COT 5407 – Introduction to Algorithms Homework Assignment #1 8 points, Due Sept. 15...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment