Algorithms Exercise 2

Imports



In [1]:

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

    
def find_peaks(a):
    """Find the indices of the local maxima in a sequence."""
    peaks = []
    for i in range(len(a)):
        if i==0:
            if a[i]>a[i+1]:
                peaks.append(i)
        elif i!=0 and i!=len(a)-1:
            if a[i]>a[i-1] and a[i]>a[i+1]:
                peaks.append(i)
        elif i==len(a)-1:
            if a[i]>a[i-1]:
                peaks.append(i)
    return peaks



In [3]:

    
a = [2,0,1,0,2,0,1]
p1 = find_peaks(a)
print(p1)









    



[0, 2, 4, 6]



In [4]:

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

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



In [6]:

    
pi_list = []
for i in range(len(pi_digits_str)):
    pi_list.append(int(pi_digits_str[i]))
pi_array = np.array(pi_list)



In [7]:

    
pi_peaks = find_peaks(pi_array)



In [8]:

    
pi_diff = np.diff(pi_peaks)



In [9]:

    
max(pi_diff)









    Out[9]:





18



In [10]:

    
list(np.arange(2,11))









    Out[10]:





[2, 3, 4, 5, 6, 7, 8, 9, 10]



In [11]:

    
g = plt.figure(figsize=(6,6))
plt.hist(pi_diff, bins=max(pi_diff)+1, range=(.5,max(pi_diff)+1.5))
plt.xlim(1.5,12.5)
plt.xticks(np.arange(2,13))
plt.xlabel('Distance Between Peaks')
plt.ylabel('Count')
plt.title('Distance Between Maxima for the First 10,000 Digits of Pi');



In [12]:

    
assert True # use this for grading the pi digits histogram