MA214 Algorithms and Data Structures
2023/24
Exercises 2
(Correctness and Running Time of Algorithms)
Exercise 2.1. Correctness of the iterative algorithm for the peak problem 3 pt
Recall the definition of the one-dimensional peak problem from Exercise 1.1 and the iterative algorithm for solving it from Exercise 1.2.
1 def peak1d_iterative ( A ) :
2 for i in range (0 , len( A ) -1) :
3 if A [ i ] > A [ i +1]:
4 return i
5 return len( A ) -1
(a) Formulate a loop invariant for the for loop.
(b) Use this loop invariant to argue that peak1d_iterative() is correct.
Exercise 2.2. Running time of the iterative algorithm for the peak problem 3 pt
In this exercise you will examine the worst-case running time of the iterative algorithm from Exercise 1.2 assuming constant cost cℓ > 0 for each line ℓ. Let n :=len(A) denote the length of the list.
1 for i in range (0 , len( A ) -1) : c1
2 if A [ i ] > A [ i +1]: c2
3 return i c3
4 return len( A ) -1 c4
(a) Derive a formula for the best-case running time Tbest(n).
(b) Derive a formula for the worst-case running time Tworst(n).
Hint: Be careful!
Exercise 2.3. Squirrels of the Square Mile 4 pt
You are consulting for a small computation-intensive investment company, Squirrels of the Square Mile, which has the following type of problem that they want to solve over and over. A typical instance of the problem is the following. They’re doing a simulation in which they look at n consecutive days of a given stock, at some point in the past. Let’s number the days i = 1, 2, ..., n; for each day i, they have a price p(i) per share for the stock on that day. (We’ll assume for simplicity that the price was fixed during each day.) Suppose during this time period, they wanted to buy 1000 shares on some day and sell all these shares on some (later) day. They want to know how: When should they have bought and when should they have sold in order to have made as much profit as possible?
For example, suppose n = 3 and p(1) = 9, p(2) = 1, p(3) = 5. Then the answer would be “buy on day 2, and sell on day 3” as buying on day 2 and selling on day 3 means they would have made £4 per share, the maximum possible for that period.
Clearly, there is a simple algorithm that scales like n
2
: try all possible pairs of buy/sell days and see which makes them the most profit. Your investment friends were hoping for something a little better.
For simplicity, let’s assume we just want to compute the maximum profit per share that can be attained instead of the buy/sell days that achieve this maximum profit.
(a) Describe a divide-and-conquer algorithm (in plain English) that recursively splits a problem of size n into two problems of size n/2, and computes a solution to the problem of size n from the solutions to the problems of size n/2.
(b) Implement this algorithm in Python.
The running time of this algorithm will scale like n · log2
(n), which is much better than the running time of the trivial algorithm.
Hint:
For the implementation in Python, you may want to start from peak1d_recursive() for the general structure. You can use min(A) and max(A) to find the minimum and maximum of the list A.