# MATH 3600

## Introduction to Computational Mathematics III

### Daniel D. Warner

Understanding how to effectively use a computer as a tool in doing mathematics is the subject of Computational Mathematics.

The first step is to learn how to program, and for this class we will use today's most powerful "platform" for programming in mathematics.

## WWW.SAGEMATH.ORG

Sage is a platform that brings together many powerful open source software packages for doing computational mathematics, and we talk to these packages using the Python programming language.

Python is a high-level scripting language that is particularly well suited for supporting the exploratory nature of Computational Mathematics.

In Part II we introduced functions and used them to do some preliminary explorations of mathematical sequences, in particular, arithmetic sequences, geometric sequences, and the Hailstone sequences.  Two fundamental approaches to defining a sequence are (1) to provide a function that directly calculates the value of the $n$-th term from the value of $n$, and (2) to provide a recurrence relation that defines the $n$-th term in terms of preceding terms and the necessary initial values of the sequence.  We saw that we can easily define the arithmetic and geometric sequences using either of these approaches.  The sequence of Fibonacci numbers and the sequence of Lucas numbers were defined using the recurrence relation  $f_{n+1} = f_n + f_{n-1}$ with $f_0$ and $f_1$ given.  The Hailstone sequences were defined by the Collatz function and we do not have a simple recurrence relation.

The next four blocks provide a quick review of these ideas.

# Consider an arithmetic sequence specified by alpha and beta alpha = -5 beta = 2 N = 18 # Compute the arithmetic sequence using the recurrence relation A1 = [alpha] while len(A1) < N: A1.append(A1[-1]+beta) print A1 # Compute the arithmetic sequence using the explicit formula def arith_seq(n): return (alpha + beta*n) A2 = [alpha+beta*n for n in range(N)] print A2
# Consider a geometric sequence specified by alpha and beta alpha = 3 beta = -2 N = 18 # Compute the geometric sequence using the recurrence relation G1 = [alpha] while len(G1) < N: G1.append(G1[-1]*beta) print G1 # Compute the geometric sequence using the explicit formula def geometric(n): return alpha*beta^n G2 = [geometric(n) for n in range(N)] print G2
# Generate the first N terms of the Fibonacci numbers N = 18 Fib = [0, 1] while len(Fib) < N: Fib.append(Fib[-1]+Fib[-2]) print Fib # Generate the first N terms of the Lucas numbers Lucas = [2, 1] while len(Lucas) < N: Lucas.append(Lucas[-1]+Lucas[-2]) print Lucas
# Generate the Hailstone sequence starting at alpha and ending when it reaches 4. alpha = 27 def Collatz(n): if n<1: return None if n%2==0: return n/2 else: return 3*n+1 H = [alpha] while H[-1] != 4: H.append(Collatz(H[-1])) print H

This completes a quick review of Part II.

# Part III - Tuples, Sets, and Dictionaries

As noted in Part I, one of the important data structures provided by Python is the List, which is an ordered, dynamic, inhomogeneous collection of objects. Three other key Python data structures are Tuples, Sets, and Dictionaries

First, a little more on ListsWe have already explored lists in some detail.  As we have seen, a list in Python is entered and displayed with square brackets.  When Python indexes into a list it starts at 0, and the index is specified with square brackets.  When indexing into a 2-dimensional list, Python uses two separate indices.  The first index indicates which list in the list of lists, and the second index indicates which element in that list.

A = [2, [4, 6, 8], 'who', 'do', 'we', 'appreciate'] print type(A) print A
A[0] = 5 print A
B = [[1,2,3],[4,5,6]] for item in B: print item B[0][2] = 13 print B

Python provides a number of "slicing" operations

print A[1:3] print A[:3] print A[2:] print A[:] print A[-2:]

Python does not deal directly with matrices, although Sage definitely does.  In Python adding two lists is just concatenation.

print A print B print A+B

In the last example  A+B  is a list consisting of 8 elements. The first element is a number. The second element is a list of 3 numbers. The next 4 elements are strings, and the last two elements are lists.

Lists in Python are very general collections.  In Python we can walk through a list in 3 different ways.

for item in A: print item

The expression range(len(A)) generates a list of integers.  The number of integers is the same as the number of items in A, and the list starts with 0.  In other words this generates the list of indices for A.  This is a somewhat "old fashioned" way to walk through a list.

for k in range(len(A)): print A[k]

Using the enumerate function we can retrieve the index and the item at the same time.  This can be very handy sometimes.

for k,item in enumerate(A): print k,item

Python has a very flexible initialization construction, called list comprehension.  It mirrors the way we typically define a set in mathematics.

X = [0 for k in range(5)] print X Y = [1 for k in range(5)] print Y Z = [(k+1)^2 for k in range(5)] print Z

Even trickier constructions are possible by adding a conditional phrase.

small_primes = [ p for p in range(100) if is_prime(p)] print small_primes

Tuple is an ordered, inhomogeneous collection of objects, but it is not dynamic.  In fact, tuples are immutable.  Once created they can not be changed.  A tuple is a collection of objects separated by commas and enclosed with parentheses.  The following blocks provide a few demonstrations about tuples.

# Basic Tuple T = (2, [4, 6, 8], 'who', 'do', 'we', 'appreciate') print type(T),T for index in [2,..,4]: print T[index]
L[4] = 'you' print L
T[4] = 'you' print T

Note:  If an item in a tuple is mutable, then that item can be changed, but the tuple itself cannot be changed.

T[1][2] = 32 print T
# A very round about way to do the preceding L1 = T[1] L1[2] = 17 print T

Note:  Use tab completion on T and notice that tuples have only two methods, while lists have 9 methods.

T. L.

In many cases a tuple can be constructed implicitly and "unpacked" implicitly. This can be particularly convenient in blocks of assignment statements. The first and last statements in the following block implicitly construct the tuple on the right, assign it to the implicit tuple on the left, and then unpack the implicit tuple.  The subsequent block writes this out explicitly. The third block shows that a collection returned by a function is actually packaged as a tuple.

a,b,c = 0,1,1 while c<100: print a,'+',b,'=',c a,b,c = b,c,b+c
T = 0,1,1 print T a,b,c = T while c<100: print a,'+',b,'=',c T = b,c,b+c a,b,c = T
def pythag(a,b): return a,b,sqrt(a^2+b^2) print pythag(3,4) a,b,h = pythag(3,4) print a,b,h

It may be surprising, but in Python numbers and strings are immutable objects as well as tuples.  This guarantees that there is only one copy of each of these objects when your program is running, and this allows Python to exploit a powerful technique called hashing.  In Python each immutable object has almost unique 64 bit hash code.

While a tuple is an immutable collection of arbitrary objects, in Python a Set is an unordereddynamic collection of immutable objects.  A set is an object that is defined using the statement set, followed by a collection of zero or more immutable objects enclosed in parentheses. The next several blocks illustrate the features of the set data structure.

S1 = set([2,3,5,7]) print type(S1) print S1
S2 = set((3,'a','b')) print S2 for item in S2: print item

Use tab completion to check out the many methods available to a set. In particular, the methods include the union and intersection operations that we commonly associate with a set.  However, the more important feature of a set is the fact that the immutability requirement enables the "in" operation to be implemented much faster than possible for the ordered collections - list and tuple.

S1.
S3 = S1.union(S2) print S3 S3.remove(5) print S3
S1.intersection(S2)

A Dictionary is a collection that consists of ordered pairs of objects.  The first object must be an immutable object and is called the key.  The second object can be an arbitrary object and is called the value.   The key:value pairs are written with a colon separating them.  The dictionary can be defined by a collection of key:value pairs separated by commas and enclosed in curly braces.

D = {'a':[1,2,3], 17:'a nice prime',(3,4):5} print type(D) print D

A value is retrieved from a dictionary by "indexing" with the key. This "indexing" notation can be used to change the values in the dictionary and to add new key:value pairs.

print D[17] print D['a'] print D[(3,4)]
# Change the value associated with key, 'a'. D['a'] = [2,4,6,8] # Add a key:value pair D[16] = 'not a prime!' for key in D: print key,'\t',D[key]
# Use tab completion to check out the methods for a dictionary. D.
# Keeping a little information about your friends D = {} D['Jones'] = ['John', '6 ft 5 in', 210, 19] D['Smith'] = ['Jane', '5 ft 2 in', 125, 21] print D
# A dictionary of dictionaries to keep information about your employees. DB = {} DB['C12357'] = {'Last Name':'Jones', 'First Name':'John', 'height':'6 ft 5 in', 'weight':210, 'age':19} DB['C22439'] = {'Last Name':'Smith', 'First Name':'Jane', 'height':'5 ft 2 in', 'weight':125, 'age':21} for k in DB: D = DB[k] print k,'\t',D['Last Name'],D['First Name'] print '\t',D['height'], D['weight'], D['age']

Note that the keys of a dictionary form a set and sets are not ordered.