Warm Up: Introduction to Python Tutorial¶
There are a few basic data types in Python including strings, ints, floats, lists, dictionaries. Uncomment and play around with these:
#type(5)
#type('bob')
#type(1.)
#type([])
#type({})
# This is a list of strings:
some_names = ['angie', 'kofi', 'sarah']
print some_names
# This is a dictionary of ages for each of the names above
the_crew = {'angie': 27, 'kofi': 30, 'sarah': 33}
print the_crew
# we can iterate over the list of strings with a for loop:
for name in some_names:
print name
# we can also iterate using the location of the element in the list to access each element:
for i in range(len(some_names)):
print some_names[i]
# let's say I don't like short names. I'll start out making an empty list to store the names I like.
names_I_like = []
# we can append to a list of names longer than say 4 letters as follows:
for name in some_names:
# check if the length of the name has 5 or more letters
if len(name) >= 5:
names_I_like.append(name)
print names_I_like
I can use LaTeX to typeset equations within the Notebook. Remember the dot product of two vectors? Let's say that $a = [a_1, a_2,\cdots, a_n]$ and $b = [b_1, b_2, \cdots, b_n]$ \begin{equation} a \cdot b = \sum\limits_{i=1}^{n}a_i\times b_i \end{equation}
Let's say that a = [2,2,3] and b = [4,-2,1.3] Can you compute their dot product here? Write a function that takes as input any vectors a and b, and returns their dot product.
To write a function that computes the dot product of two vectors, we'll need to understand the summation operator as corresponding to an iteration. We could use a for loop here:
def dotproduct(a,b):
c = 0
assert len(a) == len(b) # the lenths better be equal!
for i in range(len(a)):
# print i, a[i], b[i], a[i]*b[i] # uncomment me to make sure you understand what is happening here.
c += a[i]*b[i]
return c
# let's test it out... pretty basic huh?
a = [2,-2,3]
b = [4,1,4]
print dotproduct(a,b)
We also described the product between two arbitrary matrices A, B. Suppose A has n rows by k columns, B has k rows by m columns. Why do the rules of matrix multiplication exist? That is, why do we multiply the rows of A by the columns of B? Make sure that you understand this. The process can be described: \begin{equation} A \cdot B = (AB){ij} = \sum\limits{k=1}^{m}A{ik}B{kj} \end{equation} We discussed how the matrix product was repeating the dot product between the rows of A and the columns of B. Can you formalize this as an algorithm? In class we saw a correct algorithm but there was a typo in the implementation. Algorithms are closely related to data structures and data types and this deserves some unique attention...
One way to define matrices is with nested lists: Let's define a list A containing two lists inside of it, each representing A's rows:
A = [[2,1],[4,3]]
print A
We'll define a list B containing two lists inside of it, each representing B's rows:
B = [[3,-1,3], [2,-2,2]]
print B
# Uncomment below and run to make sure you understand what is going on here...
#print A
#print B
for row in A:
print row
Good story bro... How do we access the columns of A or B? We want to do this in a way that isn't tedious. One solution is to use the built in zip function:
print zip(*A)
print zip(*B)
# we can now access the columns of A or B as follows:
for col in zip(*B):
print col
We want to take the dot product of the rows in A and the columns in B. This gives us the components of C but we want to store them in the proper location of the new matrix C which we are defining using lists. Can you modify the code below to do this? Hint: how will you define C? It's a bit tricker given our choice of lists.
# Some code to get you started:
for row in A:
for col in zip(*B):
sum = dotproduct(row,col)
print sum
Using lists may not be the most natural way to work numerically using Python. We moved quickly to numpy, a library that supports a different object, the numpy array (or matrix).
import numpy as np
A = np.matrix(A)
B = np.matrix(B)
Uncomment this and play around with it to make sure you are familiar with numpy arrays.
print A
# checking the dimension of the object
#A.shape
# number of rows:
#A.shape[0]
# number of cols:
#A.shape[1]
# look at all rows for the 0th column
#A[:,0]
# look at all columns for the 0th row
#A[0,:]
# look at a specific component of the matrix indexed by row and column
#A[1,1]
We can index the rows or columns of A very naturally:
for i in range(A.shape[0]):
print A[i,:]
# let's look at the columns:
for j in range(B.shape[1]):
print B[:,j]
In class I gave you this code which was correct, although there was a typo in my implementation. Here it was:
def bad_mmult(A,B):
for i in range(len(A[:,0])):
for j in range(len(B[0,:])):
sum = 0
# here is where we apply the dot product
for k in range(len(A[0,:])):
sum += A[i,k]*B[k,j]
C[i,j] = sum
return C
Did you find the bug? We never defined the matrix C when we switched to numpy. Hiding in plain sight...
# The correct code should read:
def mmult(A,B):
C = np.zeros([A.shape[0],B.shape[1]])
for i in range(A.shape[0]):
for j in range(B.shape[1]):
sum = 0
# here is where we apply the dot product
for k in range(A.shape[1]):
sum += A[i,k]*B[k,j]
C[i,j] = sum
return C
Let's test it out:
C = mmult(A,B)
print C
Let's compare to the built-in function to verify our result is correct:
mmult(A,B) == np.dot(A,B)
We are interested in analyzing computation a bit more rigorously. How does the number of steps that an algorithm performs change as a function of the size of the input?
One way to characterize this is with Landau's notation. Before we introduce this, let's motivate the idea a bit more intuitively.
How does the number of steps that our multiplier performs change as a function of the size of the matrices A, and B? Let's time our code and run some experiments. Before we see the output, what kind of function do we expect to describe the relationship between input size and running time for our algorithm? (is it linear, quadratic, cubic? quartic?)
# define a variable for the size of the matrices.
size = 10
# Generate some random matrices to multiply (they can be square without loss of generality):
A = np.random.randn(size,size)
B = np.random.randn(size,size)
# print A, B
import timeit
start_time = timeit.default_timer()
C = mmult(A,B)
elapsed = timeit.default_timer() - start_time
print "that took ", elapsed, "seconds"
Can we iterate over many sizes? Define an empty list for the time it will take:
times = []
sizes = []
# let's try multiplying matrices from size 1x1 to 120x120
for i in range(120):
size = i+1
A = np.random.randn(size,size)
B = np.random.randn(size,size)
start_time = timeit.default_timer()
C = mmult(A,B)
elapsed = timeit.default_timer() - start_time
#print "size = ", size, "it took ", elapsed, "seconds"
times.append(elapsed)
sizes.append(size)
# let's import the matrix plotting library to plot some results
import matplotlib.pyplot as plt
# this lets us display figures nicely within the Notebook
%matplotlib inline
# here is how we plot
plt.scatter(sizes, times)
plt.plot(sizes, times)
# label the x and y axes
plt.ylabel("running time (seconds)")
plt.xlabel("input dimension of matrices")
plt.title("running time as a function of input size")
Based on what you know now, how can you describe the 'trick' we used to efficiently compute the Fibonnaci numbers?
\begin{equation} fib(n) = fib(n-2) + fib(n-1) \end{equation}def badfib(n):
if n == 1:
return 1
elif n == 0:
return 0
else:
return badfib(n-1) + badfib(n-2)
Why is this so slow? Exactly how slow is it? Will you grow old and die before the computer finishes?
n = 100
# print "the ", n,"th fibonacci number is: ", badfib(n)
fibTable = {1:1, 2:1}
def goodfib(n):
if n <= 2:
return 1
if n in fibTable:
return fibTable[n]
else:
fibTable[n] = goodfib(n-1) + goodfib(n-2)
return fibTable[n]
n = 200
print "the ", n,"th fibonacci number is: ", goodfib(n)