Divide and Conquer
Many divide and conquer algorithms like binary search do not require us to solve the problem on all the parts after dividing. These algorithms are sometimes called prune and search algorithms. In this lab you will solve two toy problems with prune and search.
Put both methods in a file called divide_and_conquer.py . Problem 1: finding a peak in a list
Assume a list L has the property that it can be broken into two parts so that the first part is sorted in ascending order and the second part is sorted in descending order. For example, L could be [1,4,6,9,5,2] . The peak of this list is 9 . It’s not hard to find this largest value by calling max or doing a linear-time iteration through the list. Instead, we want to do it with divide and conquer. The running time will be O(log n).
Call the method riseandfall . It takes a list L as a parameter. def riseandfall(L):
…
Problem 2: One is the lonliest number
Assume the list L is sorted and every item except one appears exactly two times. Your goal is to find the item that is not repeated.
It’s not hard to iterate through the list and find the unpaired item in O(n) time. Instead, we want to do it with divide and conquer. The running time will be O(log n).
Call the method unpaired . It takes a list L as a parameter.
def unpaired(L):
…
On Testing
In order to test if your code is efficient, I included another class called IntFunction in the skeleton. The problem was that I wanted to build a large list without taking the time to build it. The IntFunction class allows one to fake it. It behaves like a list in many respects, but it really just computed the value of a function each time someone requests an item at a given index. It can even be sliced. Look at the code and how this class is used in the tests.
Hints (if you really need them)
For riseandfall , you can look in the middle of the list and see if it’s rising or falling at the mid point. This should give an idea of which side to continue the search.
For unpaired , note that before the singleton, all the paired items are at an even index followed by an odd index. After the singleton, this is reversed. You should again be able to check the middle to see which half of the list contains the singleton.