Week 3 Studio Sheet (Solutions)
Useful advice: The following solutions pertain to the theoretical problems given in the tutorial classes. You are strongly advised to attempt the problems thoroughly before looking at these solutions. Simply reading the solu- tions without thinking about the problems will rob you of the practice required to be able to solve complicated problems on your own. You will perform poorly on the exam if you simply attempt to memorise solutions to the tutorial problems. Thinking about a problem, even if you do not solve it will greatly increase your understanding of the underlying concepts. Solutions are typically not provided for Python implementation questions. In some cases, psuedocode may be provided where it illustrates a particular useful concept.
Weekly Implementation checklist
Assessed Preparation
Problem 1. Write a Python function that implements counting sort. Test your sorting function for sequences
with only small elements, then sequences with large elements and observe the performance difference.
Problem2. Showthestepstakenbyradixsortwhensortingtheintegers4329,5169,4321,3369,2121,2099. Solution
Step 1: 4321, 2121, 4329, 5169, 3369, 2099. Step 2: 4321, 2121, 4329, 5169, 3369, 2099. Step 3: 2029, 2121, 5161, 4321, 4329, 3369. Step 4: 2029, 2121, 3369, 4321, 4329, 5161.
Studio Problems
Problem 3. Show the steps taken by radix sort when sorting the strings baaa, aaab, aaaa, aaba, abab, abaa. Assume they are initially in the given order.
It will be most beneficial for your learning if you have completed this checklist before the studio.
By the end of week 3, write Python code for:
1. Countingsort(seeAssessedpreparationproblem1) 2. Radixsort(seeAssignment1)
Problem4. ConsiderthefollowingalgorithmthatreturnstheminimumelementofagivensequenceA.Identify a useful invariant that is true at the beginning of each iteration of the for loop. Prove that it holds, and use it to show that the algorithm is correct.
functionMINIMUM_ELEMENT(A[1..n]) min = A[1]
fori=2 to ndo
if A[i] < min then
min = A[i] end if
return min endfunction
A useful invariant is that at the start of every iteration, the value of min is the minimum element in the subarray A[1..i − 1].
Proof: At the start of the first iteration, for the invariant to hold we need min to be the minimum element of the subarray A[1..1]. This is just one element, namely A[1], and min is initialised to A[1], so the invariant holds at the start of the first iteration.
Suppose the invariant holds at the start of some iteration, namely, that min is the minimum element of the subarray A[1..i −1]. We want to show that the invariant still holds at the start of the next iteration, namely, that min is the minimum element of the subarray A[1..i ]. During each iteration, the algorithm compares A[i ] to min. If A[i ] < min, then we know that A[i ] is the minimum element of the subarray A[1..i ], since it is less than min and min is the minimum element of the subarray A[1..i − 1] by the invariant. So after we set min = A[i ], the invariant holds. If A[i ] is not less than min, then since min was already the minimum of the subarray A[1..i − 1] and A[i ] is not less than it, min is also the minimum element of the subarray A[1..i]. So we do not need to do any work to preserve the invariant, and indeed the algorithm does not modify anything in this case, so the invariant holds. Since we know the invariant holds at the start of the first loop, by induction it holds for all values of i , including at the termination of the loop when i = n + 1.
To prove the algorithm is correct, we need to show that at loop termination, min is the minimum element in A. The invariant tells us that min the minimum of the subarray A[1..i − 1], but at loop termination, i =n+1,soministheminimumelementinA[1..n]whichisallofA. Thereforethealgorithmiscorrect.
Problem 5. Describe a simple modification that can be made to any comparison-based sorting algorithm to make it stable. How much space and time overhead does this modification incur?
1: 2: 3: 4: 5: 6: 7: 8: 9:
Assume that the sequence is {a1,a2,···,an} where ai represents the element at ith position in the se- quence (e.g., element at index i in the array). To stabilise a comparison-based sorting algorithm, we canreplaceeachelementofthesequenceai withapair(ai,i).Sinceeachindexisunique,thepairsare unique. We can then apply any comparison-based sorting algorithm on these pairs where two pairs (ai , i ) and (aj , j) are first compared based on the values ai and aj and, if these values are equal (i.e., ai = aj ), they are then compared on their index positions i and j . Since these pairs are unique, any sorting algo- rithm will sort them correctly, and our comparison ensures that they will retain their relative order, i.e., ai alwaysappearsbeforeaj ifai =aj andi
For part (b), we make a slight adjustment to the algorithm in the lecture notes. We modify the binary search such that we maintain the following similar invariant, array[lo] < key and array[hi] ≥ key. To do so, we must change the initial values of lo and hi to 0 and n respectively, change the con- dition of the if statement appropriately and change the final check to array[hi] = key. This works because when the algorithm terminates, hi is now pointing to the first element that is at least as large as the key. This means that if there are multiple occurrences of key, hi will point to the first one. Here is some psuedocode for concreteness.
1: 2: 3: 4: 5: 6: 7: 8: 9:
functionBINARY_SEARCH(array[1..n],key) Setlo=0andhi=n whilelo
if array[hi] = key then return hi else return null
endfunction
Problem 10. A subroutine used by Mergesort is the merge routine, which takes two sorted lists and produces from them a single sorted list consisting of the elements from both original lists. In this problem, we want to design and analyse some algorithms for merging many lists, specifically k ≥ 2 lists.
(a) DesignanalgorithmformergingksortedlistsoftotalsizenthatrunsinO(nk)time
(b) DesignabetteralgorithmformergingksortedlistsoftotalsizenthatrunsinO(nlog(k))
(c) Isitpossibletowriteacomparison-basedalgorithmthatmergesksortedliststhatisfasterthanO(nlog(k))?
To solve part (a), we can just do the naive algorithm. For all n elements, let’s loop over all k of the lists and take the smallest element that we find. We must remember to keep track of where we are up to in each list.
1: 2: 3: 4: 5: 6: 7: 8: 9:
functionKWISE_MERGE(A[1..k][1..ni]) Set pos[1..k ] = 1
Set result[1..n]
fori=1ton do
Setmin=1 forj=1tokdo
if pos[j] ≤ n j and (pos[min] = n j + 1 or A[j][pos[j]] < A[min][pos[min]]) then min=j
end if end for
result[i ] = A[min][pos[min]]
12: 13: 14: 15:
pos[min] = pos[min] + 1 end for
return result endfunction
The value ni denotes the length of the i th list. This solution has complexity O (n k ) since there are n elements in total and we spend O (k ) time looking for the minimum each iteration. There are multiple ways to write a faster algorithm for part (b). Let’s have a look at two of them.
Option 1: Divide and Conquer
We can speed up the merge by doing divide and conquer. Given a sequence of k lists to merge, let’s recursively merge the first k /2 of them, the second k /2 of them and then merge the results together.
1: 2: 3: 4: 5: 6: 7: 8: 9:
functionKWISE_MERGE(A[1..k][1..ni]) ifk =1then
return A[1][1..n1] else
Set list1 = KWISE_MERGE(A[1..k /2][1..ni ])
Set list2 = KWISE_MERGE(A[k /2 + 1..k ][1..ni ])
return MERGE(list1, list2) // The ordinary 2-way merge algorithm from Mergesort
end if endfunction
We recurse to a depth of O (log(k )) and perform n work at each step by doing the usual 2-way merge. In total this algorithm runs in O (n log(k )) time.
Option 2: Use a priority queue
The second option is to speed up the naive algorithm by using a heap / priority queue. In the naive algorithm, we spend O (k ) time searching for the minimum element to add next. Let’s just do this step by maintaining a priority queue of the next values, so that this step takes O (log(k )) time.
1: functionKWISE_MERGE(A[1..k][1..ni])
2: Set pos[1..k ] = 1
3: Set result[1..n]
4: Set queue = PriorityQueue(1...k , key(j) = A[j][pos[j]])
5: fori=1ton do
6: Set min = queue.pop()
7: result[i ] = A[min][pos[min]]
8: pos[min] = pos[min] + 1
9: if pos[min] ≤ nmin then
10: queue.push(min, key = A[min][pos[min]])
11: end if
12: end for
13: return result
14: endfunction
This implementation is the same as the first one except that we now find the minimum element in O (log(k ))
time hence the total complexity is O (n log(k )).
Finally, we can not write an algorithm for k -wise merging that runs faster than O (n log(k )) in the com- parison model. Suppose that we have a sequence of length n and split it into n sequences of length 1 and merge them. This is just going to sort the list, which we know has a lower bound of Ω(n log(n )), and hence a merge algorithm than ran faster than O (n log(k )) with k = n would surpass this lower bound.
Supplementary Problems
Problem11. Considertheproblemoffindingatargetvalueinsequence(notnecessarilysorted).Givenbelowis psuedocode for a simple linear search that solves this problem. Identify a useful loop invariant of this algorithm and use it to prove that the algorithm is correct.
functionLINEAR_SEARCH(A[1..n],target) Set index = null
fori=1 to ndo
if A[i] = target then index = i
end if end for
return index endfunction
In this case, a useful loop invariant would be that at the end of iteration i , index is equal to the largest j ≤ i such that A[j] = target, or null if target is not in A[1..i]. In the last iteration of the loop, i = n and hence index is equal to some j such that A[j] = target, or null if target is not in A[1..n], which is correct.
Problem 12. Devise an algorithm that given a sorted sequence of distinct integers a1,a2,...,an determines whetherthereexistsanelementsuchthatai =i.YouralgorithmshouldruninO(log(n))time.
Since the elements of a are sorted and distinct, it is true that ai ≤ ai +1 − 1. We are seeking an element suchthatai =i,whichisequivalenttosearchingforanelementsuchthatai −i =0. Sinceai ≤ai+1 −1, the sequence (ai − i ) for all i is a non-decreasing sequence, because
ai −i ≤ai+1 −1−i =ai+1 −(i +1).
Therefore the problem becomes searching for zero in the non-decreasing sequence ai − i , which can be solved using binary search. See the psuedocode implementation below.
1: 2: 3: 4: 5: 6: 7: 8: 9:
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12:
functionVALUE_INDEX(a[1..n])
if a[1..n ] - 1 > 0 then return False
// Invariant: a[lo] – lo ≤ 0, a[hi] – hi > 0 Setlo=1,hi=n+1 whilelo