COMP 3711 – Design and Analysis of Algorithms 2022 Spring Semester – Written Assignment Solution # 1 Distributed: Feb 18 2022 – Due: March 4, 2022
Your solutions should contain (i) your name, (ii) your student ID #, and (iii) your email address Some Notes:
• Please write clearly and briefly.
• Please follow the guidelines on doing your own work and avoiding plagiarism as described in the class policies. You must acknowledge individuals who assisted you, or sources where you found solutions. Failure to do so will be considered plagiarism.
Copyright By PowCoder代写 加微信 powcoder
• All assignments must be submitted online via canvas. Hard copies will not be accepted. Email submissions will not be accepted. Late submissions will not accepted without prior approval.
• Please make a copy of your assignment before submitting it. If we can’t find your sub- mission, we will ask you to resubmit the copy.
• If your submission is a scan of a handwritten solution, make sure that it is of high enough resolution to be easily read. At least 300dpi and possibly denser.
Solution 1: [17 pts]
(a) A = Ω(B); (b) A = Θ(B); (c) A = O(B); (d) A = Ω(B); (e) A = O(B); (f) A = Ω(B); (g) A = Ω(B);
Solution 2: [17 pts] (a) O(n2 log n);
(b) O(n2);
Solution 3: [17 pts]
(b) Θ(n log2 n)
(d) Θ(nlogn)
(e) Θ(n2 log n) Solution 4: [21 pts]
Find(s, t)
m ← ⌊s+t⌋ 2
if A[m]
else if A[m] > A[m + 1] then Find(m+1, t)
Find(s, m)
Solution 5: [28 pts]
The recurrence is T (n) = 2T (n/2) + Θ(n), running time Θ(n log n)
Merge(leftSide, rightSide)
merged ← []
leftIndex ← 0
rightIndex ← 0
leftHeight ← 0
rightHeight ← 0
maxHeight ← 0
while leftIndex < leftSide.length AND rightIndex < rightSide.length do
if leftSide[leftIndex][0] < rightSide[rightIndex][0] then
x ← leftSide[leftIndex][0] leftHeight ← leftSide[leftIndex][1] leftIndex + +
x ← rightSide[rightIndex][0] rightHeight ← rightSide[rightIndex][1] rightIndex + +
nexMaxHeight ← max(leftHeight, rightHeight) if maxHeight ̸= newMaxHeight then
merged.append((x, newMaxHeight))
maxHeight ← newMaxHeight end if
if leftIndex = leftSide.length then
◃ Placeholder value
while rightIndex < rightSide.length do merged.append((rightSide[rightIndex][0], rightSide[rightIndex][1])) rightIndex + +
end while else
while leftIndex < leftSide.length do merged.append((leftSide[leftIndex][0], leftSide[leftIndex][1])) leftIndex + +
end while end if
return merged
if A.length = 0 then return []
if A.length = 1 then
return [(A[0][0], A[0][2]), (A[0][1], 0)] end if
m ← ⌊ p+q ⌋ 2
left ← Sil(p,m)
right ← Sil(m + 1, q) return Merge(left,right)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com