MA214 Algorithms and Data Structures
2023/24
Exercises 4
(Master Theorem, Heap Sort, Binary Search)
Exercise 4.1. Master Theorem 3 pts
Use the Master Theorem to find solutions to the following recurrences. Make sure that you state and justify which case of the Master Theorem you use.
(a) T(n) = 3 · T(n/4) + n log2
(n)
(b) T(n) = 3 · T(n/2) + n
(c) T(n) = 3 · T(n/3) + n/2
Exercise 4.2. Heap Sort 1 pts
In the lectures last week, we saw the Heap Sort algorithm, which sorts a list in place and in worst-case time O(n · log2
(n)). Using the figures from the lecture as a model, illustrate the operation of BuildMaxHeap on the list
A = [5, 3, 17, 10, 84, 19, 6, 22, 9] .
Exercise 4.3. Randomised algorithms 3 pts
Suppose your are given a list A of even length, len(A) = n, and you know that n/2 of the entries are equal to x, and the other n/2 entries are equal to y = x. You want to find x and y.
A simple deterministic algorithm (not relying on randomisation) for this problem that is guaranteed to find x and y proceeds as follows. First it sets x = A[0]. It then goes through the elements at positions i = 2, . . . , n − 1. As soon as A[i] = x, the algorithm sets y = A[i] and outputs x and y.
(a) Implement this algorithm in Python, and analyse its running time using big Θ- notation.
Now consider the following randomised algorithm for this problem. Repeatedly draw a random entry (with replacement, so you may draw the same entry more than once) until you have seen two distinct numbers for the first time.
(b) Implement this algorithm in Python.
(c) What is the expected number of random draws performed by this algorithm?
(d) Use your answer to (c) to analyse the expected running time of this algorithm using big O-notation.
(e) Is this a Monte Carlo or a Las Vegas algorithm?
Hint: For part (c) it may be useful to consider the random variable Y which counts the number of random draws, and compute the probability that Pr[Y > k].
Exercise 4.4. Binary Search 3 pts
Given an arbitrary list, an algorithm searching for a specific target value in the list cannot do much better than scanning the list elements one by one, which requires Ω(n) time in the worst case. On the other hand, if the algorithm is guaranteed to be given a sorted list (say, in non-decreasing order), it is possible to do drastically better. An algorithm, with a single comparison, can eliminate half of the entries of the list as possible locations. This is the idea underlying the “Binary Search” algorithm.
(a) Implement a recursive Python function that searches for value x in the list A, which is sorted in non-decreasing order. Your function should return an index i, where A [i]=x (or the special Python value None if no such i exists) and have time com-plexity O(log n), where n is the length of the input list. (Do not use slicing, as it is a linear-time operation.)
(b) Implement an iterative version of the binary search in Python, BinarySearch(A,x), where A, x, and the time complexity are the same as above.
(c) Give a loop invariant for your algorithm in part (b). Prove the correctness of that algorithm using your loop invariant.