Algorithms Exercise 2

Imports



In [2]:

    
%matplotlib inline
from matplotlib import pyplot as plt
import seaborn as sns
import numpy as np

Peak finding

Write a function find_peaks that finds and returns the indices of the local maxima in a sequence. Your function should:

Properly handle local maxima at the endpoints of the input array.
Return a Numpy array of integer indices.
Handle any Python iterable as input.



In [3]:

    
def find_peaks(a):
    """Find the indices of the local maxima in a sequence."""
    # local maxima defined as being greater than the one adjacent cell on either side
    max_ind = []
    for i in range(len(a)):
        if i == 0:
            if a[i] > a[i + 1]:
                max_ind.append(i)
        elif i == (len(a) - 1):
            if a[i] > a[i - 1]:
                max_ind.append(i)
        else:
            if a[i] > a[i - 1] and a[i] > a[i + 1]:
                max_ind.append(i)
    return(max_ind)
    #raise NotImplementedError()



In [5]:

    
p1 = find_peaks([2,0,1,0,2,0,1])
assert np.allclose(p1, np.array([0,2,4,6]))
p2 = find_peaks(np.array([0,1,2,3]))
assert np.allclose(p2, np.array([3]))
p3 = find_peaks([3,2,1,0])
assert np.allclose(p3, np.array([0]))









    Out[5]:





[0, 5, 7]

Here is a string with the first 10000 digits of $\pi$ (after the decimal). Write code to perform the following:

Convert that string to a Numpy array of integers.
Find the indices of the local maxima in the digits of $\pi$.
Use np.diff to find the distances between consequtive local maxima.
Visualize that distribution using an appropriately customized histogram.



In [4]:

    
from sympy import pi, N
pi_digits_str = str(N(pi, 10001))[2:]



In [8]:

    
pi_spaced = ' '.join(pi_digits_str)
pi_dig = np.array([int(x) for x in pi_spaced.split(' ')])
inds = find_peaks(pi_dig)
dists = np.diff(inds)

plt.hist(dists)
#raise NotImplementedError()









    Out[8]:





(array([  1.90200000e+03,   6.65000000e+02,   1.31000000e+02,
          1.26000000e+02,   3.00000000e+01,   3.20000000e+01,
          9.00000000e+00,   1.00000000e+00,   1.00000000e+00,
          1.00000000e+00]),
 array([  2. ,   3.6,   5.2,   6.8,   8.4,  10. ,  11.6,  13.2,  14.8,
         16.4,  18. ]),
 <a list of 10 Patch objects>)



In [ ]:

    
assert True # use this for grading the pi digits histogram