Algorithms Exercise 2

Imports



In [11]:

    
%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 [12]:

    
def find_peaks(a):
    """Find the indices of the local maxima in a sequence."""
    maxima = []
    for x in range(0, len(a)):
        if(x==len(a)-1 or a[x]>a[x+1]) and a[x]>a[x-1]:
            maxima.append(x)
    return np.array(maxima)



In [13]:

    
a = [1,3,6,4,5,1]
find_peaks(a)









    Out[13]:





array([2, 4])



In [14]:

    
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]))

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 [15]:

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



In [20]:

    
q = pi_digits_str
r = []
for p in q:
    r.append(int(p))
a = np.array(r)
m = find_peaks(a)
m = find_peaks(a)
s = np.diff(m)
plt.hist(s,bins=50)









    Out[20]:





(array([  1.06700000e+03,   0.00000000e+00,   0.00000000e+00,
          8.35000000e+02,   0.00000000e+00,   0.00000000e+00,
          4.31000000e+02,   0.00000000e+00,   0.00000000e+00,
          2.34000000e+02,   0.00000000e+00,   0.00000000e+00,
          1.31000000e+02,   0.00000000e+00,   0.00000000e+00,
          9.20000000e+01,   0.00000000e+00,   0.00000000e+00,
          3.40000000e+01,   0.00000000e+00,   0.00000000e+00,
          3.00000000e+01,   0.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   1.90000000e+01,   0.00000000e+00,
          0.00000000e+00,   1.30000000e+01,   0.00000000e+00,
          0.00000000e+00,   4.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   5.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   1.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   1.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
          0.00000000e+00,   1.00000000e+00]),
 array([  2.  ,   2.32,   2.64,   2.96,   3.28,   3.6 ,   3.92,   4.24,
          4.56,   4.88,   5.2 ,   5.52,   5.84,   6.16,   6.48,   6.8 ,
          7.12,   7.44,   7.76,   8.08,   8.4 ,   8.72,   9.04,   9.36,
          9.68,  10.  ,  10.32,  10.64,  10.96,  11.28,  11.6 ,  11.92,
         12.24,  12.56,  12.88,  13.2 ,  13.52,  13.84,  14.16,  14.48,
         14.8 ,  15.12,  15.44,  15.76,  16.08,  16.4 ,  16.72,  17.04,
         17.36,  17.68,  18.  ]),
 <a list of 50 Patch objects>)



In [35]:

    
?np.split



In [ ]:

    
assert True # use this for grading the pi digits histogram