Exam (elaborations)

CMPUT204: Introduction to Algorithms Final Exam

118 views 0 purchase

Course
CMPUT 204

Institution
University Of Alberta (UofA)

[Show more]

Preview 2 out of 11 pages

View example

Uploaded on January 16, 2023
Number of pages 11
Written in 2022/2023
Type Exam (elaborations)
Contains Questions & answers

university of alberta
cmput204 introduction to algorithms final exam

Abbyy01 Member since 2 year 35 documents sold

CA$16.69

Added

Add to cart Add to wishlist

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

CMPUT204: Introduction to Algorithms
Final Exam
Instructions.
• This exam has 5 problems, each is worth 25pts.
• You may answer all 5 problems, but your grade will be composed of the best 4 answers.
• Closed books.
• You may use a scientific calculator.
• Collaborations of any kind are strictly forbidden.
• Note: All logarithms are in base 2 unless specified otherwise.
n
P 1
• You can use the fact that H(n) = i = ln n + O(1) without proving it.
i=1

1

, Problem 1. (25 pts)
(i) (15 pts) Below is the description of the MergeSort algorithm for sorting n pairwise-comparable elements
given in an array A.

1. Prove the correctness of the MergeSort algorithm.

2. Derive the suitable recurrence relation representing the runtime of MergeSort.

3. Solve the recurrence relation to derive its runtime.

procedure Mergesort(A, l, h) ** Sorts the subarray A[l, ..., h]
if (l < h) then
m ← b l+h
2 c
MergeSort(A, l, m)
MergeSort(A, m + 1, h)
Merge(A, l, m, h)
You may assume that you are given a function Merge(A, p, q, r) whose input is an array of elements
A such that A[p, ..., q] is sorted and A[q + 1, ...r] is sorted; and that permutes the element of A so that
when Merge halts the elements in A[p, ..., r] are all sorted. This Merge function is given to you — so
you can use it, the fact that it makes at most p − r Key-Comparisons, and the fact that its runtime
is Θ(r − p) without specifying how it work, without proving its correctness and without analyzing its
runtime.
Answer.

Correctness. We prove correctness of MergeSort using full/complete induction on n, the number of
elements in the array, where n = h − l + 1.
In the base cases the array is either empty or contains a single element. Here MergeSort does nothing
as the array is ordered to begin with.
Fix n ≥ 2. Assuming MergeSort is correct for any array of any size < n, we argue MergeSort is correct
for any array of size n.
First, we claim that m < h and that m + 1 > l. This is true since if n ≥ 2 we must have l < h and so

m = b h+l
2 c≤
h+l
2 ≤ h+h
2 =h

and similarly
m + 1 = b h+l h+l
2 c+1≥d 2 e≥
h+l
2 ≥ l+l
2 =l
Now, the fact that m < h implies that m−l +1 < h−l +1 = n so the first recursive call in MergeSort is
over an array with < n elements. Similarly, the fact that m+1 > l implies that h−(m+1)+1 < h−l+1 = n,
so the second recursive call in MergeSort is also over an array with < n elements. By the IH, both calls
results in a sorted subarray.
Hence, when we invoke Merge(), both subarrays A[l, m] and A[m + 1, h] are sorted. By the correctness
of Merge(), it returns A fully sorted. The induction step is now complete.

Runtime. Clearly, for inputs of size ≤ 1 or algorithm’s runtime is some constant (checks that l ≮ h and
aborts). Hence, T (1) = O(1). For a general size input, we have that one subarray we recurse on is of size
b n2 c and the other subarray we recurse on is of size d n2 e, and then we invoke Merge() which runs in time
O(n). This gives a recurrence relation of

T (n) = T (b n2 c) + T (d n2 e) + Θ(n)

2

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller Abbyy01. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for CA$16.69. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

79223 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling

Exam (elaborations)

CMPUT204: Introduction to Algorithms Final Exam

Document information

Subjects

Written for

Seller

Reviews received

Content preview