Afifah Mazhar

Homework 3
CS 6363.0U2

1.
a)
Because all elements are equal, randomized quick-sort will always return q = r.
2
We get T(n) = T(n -1) + Θ(𝑛)= Θ(𝑛 ) for the recurrence.
b)
Partition` (A, p, r)
high = p
low = p
x=A[p]
for i = p + 1 to r
if A [ i ] < x
y=A[i]
A [ i ] = A [ high + 1 ]
A [ high + 1 ] = A [ low ]
A [ low ] = y
low = low + 1
high = high + 1
else if A [ i ] == x
exchange A [ high + 1 ] with A [ i ]
high = high + 1
return (low, high)
c)
Quicksort` (A, p, r)
if p < r
(low, high) = Randomized-partition` (A, p, r)
Quicksort` (A, p, low - 1)
Quicksort` (A, high + 1, r)
d)
Because we don’t recurse elements equal to the pivot, the subproblem sizes with
Quicksort` aren’t larger than the subproblem sizes with Quicksort (when all of the
elements are distinct).
2.
Assume we have to construct a binary decision tree to represent the comparisons.
Because the length of each sub sequence is k. There are (k!)^n/k possible permutations. So, to
compute the height h of the decision tree, we need to have (k!)^n/k <= 2^h. Taking the logs on
𝑛 𝑛 𝑘 𝑙𝑛 𝑘 −𝑘 𝑛 𝑙𝑛 𝑘 − 𝑛
both sides we get that ℎ ≥ 𝑘
× 𝑙𝑔 (𝑘!) ≥ 𝑘
× ( 𝑙𝑛 2
) = 𝑙𝑛 2
= Ω (𝑛 𝑙𝑔 𝑘)

This study source was downloaded by 100000889799406 from CourseHero.com on 09-08-2024 10:15:55 GMT -05:00

https://www.coursehero.com/file/99650973/Homework-3pdf/
 3.
Bottom Up Approach:
BottomUp(n):
T0 = 0
T1 = 0
T2 = 1
a = T0
b = T1
c = T2
print(a)
print(b)
print(c)
for(i = 4 to n):
d = a+b+c
print(d)
a=b
b=c
c=d

Top Down Approach:

TopDown(n):
ArrayT[0...n]
T[0] = 0
T[1] = 0
T[2] = 1
for (t = N tp 0):
if ( T[i] == NULL):
Calculate(T[i])
print(T[i])
else:
print(T[i])

Calculate(n):
if (n == 0):
return 0
if(n == 1):
return 0
if(n == 2):
return 1
return Calculate(n -1) + Calculate(n-2) + Calculate(n-3)

This study source was downloaded by 100000889799406 from CourseHero.com on 09-08-2024 10:15:55 GMT -05:00

https://www.coursehero.com/file/99650973/Homework-3pdf/
Powered by TCPDF (www.tcpdf.org)