=================================================================================================================

Computational Thinking - 21st Century Algebra

Michel Paul

pythonicmath@gmail.com

CMC-SS Conference Palm Springs

November 5, 2010

Equity in Mathematics:

Access, Achievement, Identity and Power

=================================================================================================================

In this presentation I would like to describe three things:

Computational Thinking
Python
SAGE

################################################### ## Yoda -- created from over 50,000 triangles. ## ################################################### from scipy import io x = io.loadmat(DATA + 'yodapose') from sage.plot.plot3d.index_face_set import IndexFaceSet V = x['V']; F3=x['F3']-1; F4=x['F4']-1 Y = IndexFaceSet(F3,V,color=Color('#00aa00')) + IndexFaceSet(F4,V,color=Color('#00aa00')) Y = Y.rotateX(-1.5) Y.show(aspect_ratio=[1,1,1], frame=False, figsize=5)

/home/sage/sage_install/sage-4.3.5/local/lib/python2.6/site-packages/sci\
py/io/matlab/mio.py:64: FutureWarning: Searching for mat files on python
system path will be removed in future versions of scipy
  full_name = find_mat_file(file_name, appendmat)
/home/sage/sage_install/sage-4.3.5/local/lib/python2.6/site-packages/sci\
py/io/matlab/mio.py:84: FutureWarning: Using struct_as_record default
value (False) This will change to True in future versions
  return MatFile5Reader(byte_stream, **kwargs)

/home/sage/sage_install/sage-4.3.5/local/lib/python2.6/site-packages/scipy/io/matlab/mio.py:64: FutureWarning: Searching for mat files on python system path will be removed in future versions of scipy
  full_name = find_mat_file(file_name, appendmat)
/home/sage/sage_install/sage-4.3.5/local/lib/python2.6/site-packages/scipy/io/matlab/mio.py:84: FutureWarning: Using struct_as_record default value (False) This will change to True in future versions
  return MatFile5Reader(byte_stream, **kwargs)

On the Interplay Between Math and Programming

Why is programming intrinsically an activity with a strong mathematical flavor? Well, mathematical assertions have three important characteristics.

Mathematical assertions are always general in the sense that they are applicable to many - often even infinitely many - cases: we prove something for all natural numbers or all nondegenerate Euclidean triangles.
Besides general, mathematical assertions are very precise. This is already an unusual combination, as in most other verbal activities generality is usually achieved by vagueness.
A tradition of more than twenty centuries has taught us to present these general and precise assertions with a convincing power that has no equal in any other intellectual discipline. This tradition is called Mathematics.

The typical program computes a function that is defined for an incredibly large number of different values of its argument; the assertion that such and such a program corresponds to such and such a function has therefore the generality referred to above.

Secondly: the specification of what a program can achieve for us must be pretty precise, if it is going to be a safe tool to use. Regarded as a tool its usage can only be justified by an appeal to its stated properties, and if those are not stated properly its usage cannot be justified properly. And here we have the second characteristic.

Thirdly: the assertion that such and such a program corresponds to such and such a function, although general and precise is not much good if it is wrong.

- Edsger W Dijkstra, EWD641

Computer science is no more about computers than astronomy is about telescopes.

- EWD

What is 'Computational Thinking'?

how computer scientists think

the kind of thinking that gave rise to computers in the first place

exists in the construction of the abacus which is the foundation of our number system

is about modeling ideas

is the "automation of abstractions"

is "procedural epistemology"

is a relatively new term that has struck a chord across a broad cross-section of academics

has resulted in new inter-disciplinary majors such as
- Computational Linguistics
- Computational Biology
- Computational Physics
- Computational Mathematics.

will become just as important to a well-educated person in the 21st century as reading and writing are today
- Jeanette Wing

Primary Statement

Behind all of the various forms of computational technology that surround us is computational language.

The kinds of computational tools we find in our environment constantly shift.

Computational languages also shift, but they shift more slowly and embody a history. A language is a culture.

The functional programming paradigm has a deep and robust mathematical history going back to the 1930's in the work of Alonzo Church,

and it will likely have a lot to do with the style of future programming.

It is also the kind of programming that is most essentially related to mathematics. It's all about functions.

Knowing how to use various tools to solve various kinds of problems provides one kind of technological understanding,

but learning how to express one's thoughts in computational terms provides quite another. Literacy is all about language.

For example, a tuple, an ordered list (x, y), might represent a point, a fraction, or a vector.

What distinguishes the type of ordered list we're dealing with is the set of functions we use to describe its behavior.

Adding fractions is not the same thing as adding vectors.

Contemporary programming is about describing the behavior of and the functional relations between various kinds of objects.

How we organize these functions and objects varies according to different schools of thought in computer science; however,

the entire secondary mathematics curriculum could be usefully described in terms of functional relations between numbers, tuples, and lists of tuples.

Teaching students to reason and articulate their thoughts in these terms would give them a relevant foundation in both mathematical and computational literacy.

I believe that we can and should integrate computational thinking into the math curriculum.

Why? What is the rationale?

China

this is the 21st century.

this is how math and science are done these days.
- the 3 pillars of science are now theory, experiment, and computational modeling

students don't understand our number system.
- they don't understand place value!
- they don't understand division!

research indicates that the activity of programming can help in the formation of mathematical concepts

we talk a lot about writing in the math curriculum - and that's what programming is.

we talk a lot about integrating technology into the curriculum - what better way than to show students how technology is language?

the ACM (Association for Computing Machinery) is very concerned that technological literacy
- is usually understood as familiarity with various popular software applications.
- is often considered as an elective literacy rather than as a core literacy.

In The Final Report of the National Mathematics Advisory Panel published in 2008 by the US Department of Education there is the following statement:

Research indicates that learning to write computer programs improves students’ performance compared to conventional instruction, with the greatest effects on understanding of concepts and applications.

Recommendation: The Panel recommends that computer programming be considered as an effective tool for developing specific mathematics concepts and applications, and mathematical problem- solving abilities. Effects are larger if the computer programming language is designed for learning (e.g., Logo) and if students’ programming is carefully guided by teachers so as to explicitly teach students to achieve specific mathematical goals.

Just prior to this, in the same document, is another recommendation:

A review of 11 studies that met the Panel’s rigorous criteria found limited or no impact of calculators on calculation skills, problem solving, or conceptual development over periods of up to 1 year.

Recommendation: The Panel recommends that high-quality research on particular uses of calculators be pursued, including both their short- and long-term effects on computation, problem solving, and conceptual understanding.

It is worth noting that though the use of calculators in math classes has become the status quo,

further research on calculator use is recommended but as of this document has been inconclusive.

However, research regarding the use of programming in math is conclusive.

So ... why aren't we doing this?

"It is said that a concept is demonstrated to have been learned the best when one explains that concept to others.

Programming is precisely that - using an expressive language to unambiguously describe all the steps involved in problem solving of a certain type."

- Tony Targonski

"It goes against the grain of modern education to teach children to program.

What fun is there in making plans, acquiring discipline in organizing thoughts,

devoting attention to detail,

and learning to be self-critical?"

- Alan Perlis

"Computation is the principle; the computer is the tool."

- Peter Denning

"Computer science is the new mathematics."

- Dr. Christos Papadimitriou

"You may say I'm a dreamer, but I'm not the only one."

- John Lennon

Why Python?

just as easy to learn to use as a calculator

a respected and general purpose language used at places including Google, NASA, JPL, YouTube, Industrial Light and Magic, among others

often referred to as 'pseudo-code that runs'

becoming an increasingly popular educational language

free to everyone and runs on all platforms

an excellent language for expressing mathematics (Scipy, SAGE)

Math for the Digital Age

Kirby Urner was one of the first people to start calling out for integrating Python into math classes.

xkcd

(Note >>> import antigravity is a fun Easter Egg.)

Python can be used just as easily as a calculator:

2+3

2*3

2**3

2**1000

42%12

42//12

divmod(42, 12)

Variables:

a = 5 b = 7 a+b

phi = (1+sqrt(5))/2 phi

show(phi)

Functions:

f(x) = 3x + 5

def f(x): return 3*x + 5

f(100)

f(200)

for x in range(10): (x, f(x))

Lists:

dreidel = ['gimmel', 'shin', 'hey', 'nun'] choice(dreidel)

choice(dreidel)

Loops:

for spin in range(11): choice(dreidel)

List Comprehension

List comprehension is a method of creating new lists from previous lists.

It is a recent kind of programming technique used in several functional languages.

It is based on mathematical set builder notation.

Students are able to understand it.

range(10)

range(1, 11)

range(1, 20, 2)

A range is an interval.

odds = range(1, 100, 2) odds

sum(odds)

squares = [x**2 for x in odds] squares

sum(squares)

A deck of cards is a set of ordered pairs:

suits = ['C', 'D', 'H', 'S'] ranks = ['A', 2, 3, 4, 5, 6, 7, 8, 9, 10, 'J', 'Q', 'K'] deck = [(rank, suit) for rank in ranks for suit in suits] deck

shuffle(deck) deck

hands = [[], [], [], []] for card in range(5): for hand in hands: hand.append(deck.pop()) for hand in hands: hand

Why shouldn't this be part of math class?

Here is a function that computes a list of the factors of n:

def factors(n): return [x for x in range(1, n+1) if n%x == 0]

factors(1000)

factors(60000)

What is the definition of a prime number?

def is_prime(n): return len(factors(n)) == 2

is_prime(1)

is_prime(0)

is_prime(2)

primes = [x for x in range(1, 1001) if is_prime(x)] primes

And here is a function that computes a list of the factor pairs of n:

def factor_pairs(n): return [(x, n//x) for x in range(1, int(sqrt(n))+1) if n%x == 0]

factor_pairs(600)

factor_pairs(126377594805)

Programming is not merely 'telling a machine what to do'.

Programming is also a way to

organize ideas
communicate with other humans (your future self)
organize conceptual maps of a topic

Here is a statistical concept outline that also runs. It does what it says:

Mean: \frac{\sum^{n}_{i=1}x_i}{n}

def mean(L): return sum(L)/len(L)

A = [randint(10, 99) for i in range(10)] B = [randint(10, 99) for i in range(10)] C = [randint(10, 99) for i in range(10)] A; B; C

mean(A); mean(B); mean(C)

Variance: \frac{\sum_{i=1}^{n}(x_i - \mu)^2}{n}

def deviations(L): return [x - mean(L) for x in L] def variance(L): return mean([d**2 for d in deviations(L)]) variance(A); variance(B); variance(C)

Standard Deviation: \sqrt{\frac{\sum_{i=1}^{n}(x_i - \mu)^2}{n}}

def stdev(L): return sqrt(variance(L))

fibonaccis = [1, 1, 2, 3, 5, 8, 13, 21] primes = [2, 3, 5, 7, 11, 13, 17, 19] triangular = [1, 3, 6, 10, 15, 21, 28, 36]

mean(fibonaccis); stdev(fibonaccis)

mean(primes); stdev(primes)

mean(triangular); stdev(triangular)

I have had students exclaim after seeing this that they finally understood \sum notation for the first time:

\sum_{x=a}^{b}f(x) ---> sum([f(x) for x in range(a, b+1)])

def sigma(f,a,b): return sum([f(x) for x in range(a, b+1)])

def f(x): return 2**x

sigma(f, 0, 10)

Dictionaries

capital = {'Mississippi': 'Jackson', 'Oklahoma': 'Oklahoma City', 'Delaware': 'Dover', 'Minnesota': 'St. Paul', 'Illinois': 'Springfield', 'Arkansas': 'Little Rock', 'New Mexico': 'Santa Fe', 'Indiana': 'Indianapolis', 'Maryland': 'Annapolis', 'Louisiana': 'Baton Rouge', 'Idaho': 'Boise', 'Wyoming': 'Cheyenne', 'Tennessee': 'Nashville', 'Arizona': 'Phoenix', 'Iowa': 'Des Moines', 'Michigan': 'Lansing', 'Kansas': 'Topeka', 'Utah': 'Salt Lake City', 'Virginia': 'Richmond', 'Oregon': 'Salem', 'Connecticut': 'Hartford', 'Montana': 'Helena', 'California': 'Sacramento', 'Massachusetts': 'Boston', 'West Virginia': 'Charleston', 'South Carolina': 'Columbia', 'New Hampshire': 'Concord', 'Wisconsin': 'Madison', 'Vermont': 'Montpelier', 'Georgia': 'Atlanta', 'North Dakota': 'Bismarck', 'Pennsylvania': 'Harrisburg', 'Florida': 'Tallahassee', 'Alaska': 'Juneau', 'Kentucky': 'Frankfort', 'Hawaii': 'Honolulu', 'Nebraska': 'Lincoln', 'Missouri': 'Jefferson City', 'Ohio': 'Columbus', 'Alabama': 'Montgomery', 'Rhode Island': 'Providence', 'South Dakota': 'Pierre', 'Colorado': 'Denver', 'New Jersey': 'Trenton', 'Washington': 'Olympia', 'North Carolina': 'Raleigh', 'New York': 'Albany', 'Texas': 'Austin', 'Nevada': 'Carson City', 'Maine': 'Augusta'}

capital['California']

Sets

fibonaccis; set(fibonaccis)

set(fibonaccis).intersection(set(primes))

set(fibonaccis).union(set(primes))

Euclid's Algorithm

One of the most beautiful examples of computational thinking is Euclid's Algorithm.

It is a procedure for finding the greatest common factor of two numbers.

To find the greatest common factor of a and b:

If a is equal to b, then you have found it.
If a is greater than b, then find the greatest common factor of a-b and b.
If a is less than b, then find the greatest common factor of a and b-a.

This is the oldest recorded algorithm in history and is still used today. It is very important in number theory and is a key element for encryption.

An Algebra student should be capable of tracing through the behavior of this algorithm given two postive integers.

def gcf(a, b): if a == b: return a if a > b: return gcf(a-b, b) if a < b: return gcf(a, b-a)

gcf(884, 3009)

gcf(120, 340)

Here is a slightly more efficient version using the mod operator:

def gcf(a, b): r = a%b while r != 0: a, b = b, r r = a%b return b

gcf(884, 3009)

gcf(120, 340)

Here is an even more pythonic version:

def gcf(a, b): while b: a, b = b, a%b return a

gcf(884, 3009)

gcf(120, 340)

And here is a purely functional version utilizing recursion:

def gcf(a, b): if b==0: return a return gcf(b, a%b)

gcf(884, 3009)

gcf(120, 340)

Now, the gcf() function already exists in Sage as gcd():

gcd(120,340)

One might wonder why we're bothering to program what already exists right here in this environment.

Well, that's how you learn! That's what's so great about this environment. You can use it in all kinds of ways.

unitnames = 'zero one two three four five six seven eight nine'.split() teennames = 'ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'.split() tensnames = 'None None twenty thirty forty fifty sixty seventy eighty ninety'.split() powernames = 'hundred thousand million billion trillion quadrillion quintillion sextillion septillion octillion nonillion decillion'.split() def name(n): if n < 0: return 'negative ' + name(-n) if n < 10: return unitnames[n] if n < 20: return teennames[n%10] if n < 100: if n%10 == 0: return tensnames[n//10] return tensnames[n//10] + ' ' + name(n%10) if n < 1000: if n%100 == 0: return unitnames[n//100] + ' hundred' return unitnames[n//100] + ' hundred ' + name(n%100) power = int(log(n, 1000)) group = 1000**power if n%group == 0: return name(n//group) + ' ' + powernames[power] else: return name(n//group) + ' ' + powernames[power] + ', ' + name(n%group)

name(42)

Since Python is a general purpose language, students who have learned how to express their thoughts using it will have other doors opened to them, not just mathematical.

Dear Mr Paul,

It's Sofia Canales, I had your FST class last year. I am going to the Pratt Institute in Brooklyn, and guess what, my scripting for Animation course is in PYTHON!! I thought that would be fun for you to hear, and now I have the advantage in the class for already having some experience with it!
Anyway, I hope things are looking up for you and your innovative intentions for upgrading my old high school.

Sincerely,

Sofia Canales

Another door that knowing a little Python opens is:

Symbolic Algebra Geometry Explorer

Sage is

a set of mathematical libraries bundled with Python creating a free and open source version of something like Mathematica.
a state of the art CAS (Computer Algebra System).
used by mathematicians and scientists to write papers and books.

This file you are reading is a SAGE file.

SAGE can run in simple console I/O (like a calculator), or it can run in a browser (as you now see it).
This environment fluidly integrates computational cells, graphics, mathematical formulae, and ordinary text.
It is possible to use SAGE without knowing Python, but someone who knows Python will be able to use SAGE much more effectively.
Some university math departments using things like Mathematica, Matlab, or Maple have recently begun to switch to Python and SAGE, as these are free and open-source. No licensing issues to worry about!

Following are some examples of the kinds of things you can do with SAGE:

icosahedron()

var('x y') saddle = plot3d(x^2 - y^2, (x,-2,2), (y,-2,2)) sphere((0,0,1), color='red', opacity=0.5, aspect_ratio=[1,1,1]) + saddle

show(pi); pi.n(digits = 1000)

show(sqrt(2)); sqrt(2).n(digits = 500)

SAGE turns the various mathematical classes of number into programmable data types. This is significant.

pi in RR

pi in QQ

pi in CC

Exact values are preserved in all calculations unless otherwise specified.

sqrt(48)

show(sqrt(48))

x = sqrt(48) + sqrt(60) show(x)

x.n(digits = 50)

x = 2*pi + 3*pi show(x)

x.n(digits = 50)

Sage provides interval notation instead of always having to use range():

[x^2 for x in [1..100]]

\sum_{x=1}^{100}x^2

sum([x^2 for x in [1..100]])

f(x) = x^2 - 25

f(x) = x^2 - 25 plot(f, -10, 10)

parabola = [(x, f(x)) for x in [-10..10]] parabola show(points(parabola))

var('x') solve(f, x)

var('a b c') f(x) = a*x^2 + b*x + c show(f)

solve(f(x) == 0, x)

show(_)

@interact def _(a = (-5..5), b = (-5..5), c = (-5..5)): f(x) = a*x^2 + b*x + c show(f) show(plot(f, -5, 5))

Click to the left again to hide and once more to show the dynamic interactive window

y = a·f(x-h)+k

f(x) = x^2 @interact def _(a = (-5, 5), h = (-5, 5), k = (-5, 5)): g(x) = a*f(x-h) + k show(g) show(plot(f(x), -10, 10, linestyle = '--') + \ plot(g(x), -10, 10, color = 'red'), \ ymax = 25, ymin = -25, aspect_ratio = 1)

Click to the left again to hide and once more to show the dynamic interactive window

An alternate derivation of the geometric series formula:

var('r') (r-1)/(r-1)

factor((r^2-1)/(r-1))

factor((r^3-1)/(r-1))

factor((r^4-1)/(r-1))

expand(factor((r^4-1)/(r-1)))

for i in [1..10]: show(expand(factor((r^i-1)/(r-1))))

Matrices

A matrix is a list of lists.

row1 = [2, 9, 4] row2 = [7, 5, 3] row3 = [6, 1, 8] magic = [row1, row2, row3] magic

for row in magic: row

magic[1]

magic[1][1]

Though this is a matrix, it's kind of a dumb matrix.

It doesn't know how to do matrixy kinds of things.

Teaching it how to do those things would make a very good programming project.

Meanwhile, Sage lets you turn your list of lists into a matrix object:

magic = matrix([row1, row2, row3]) magic

magic.determinant()

magic.transpose()

magic.row(2)

magic.column(2)

sum(magic.row(0))

sum(magic.column(0))

var('theta x y') def R(theta): return matrix([[cos(theta), sin(theta)], [-sin(theta), cos(theta)]]) def P(x, y): return matrix([[x], [y]])

show(R(theta))

show(P(x, y))

R(theta)*P(x, y)

show(R(theta)*P(x, y))

R(pi/4)*P(3, 4)

show(R(pi/4)*P(3, 4))

e(x) = (1+1/x)^x

plot(e, 0, 20)

lim(e, x=oo)

f(x) = x^2 f; derivative(f, x)

f; integral(f, x)

plot(f, -5, 5)+plot(derivative(f), -5, 5, color = 'red')+plot(integral(f), -5, 5, color = 'green')

plot(derivative(f), -5, 5)

2010 CMC-SS Palm Springs Conference

566 days ago by mpaul

Computational Thinking - 21st Century Algebra

Michel Paul

CMC-SS Conference Palm Springs

November 5, 2010

Equity in Mathematics:

Access, Achievement, Identity and Power

On the Interplay Between Math and Programming

Primary Statement

List Comprehension

Mean: \frac{\sum^{n}_{i=1}x_i}{n}

Variance: \frac{\sum_{i=1}^{n}(x_i - \mu)^2}{n}

Standard Deviation: \sqrt{\frac{\sum_{i=1}^{n}(x_i - \mu)^2}{n}}

\sum_{x=a}^{b}f(x) ---> sum([f(x) for x in range(a, b+1)])

Dictionaries

Sets

Euclid's Algorithm

Symbolic Algebra Geometry Explorer

Click to the left again to hide and once more to show the dynamic interactive window

Click to the left again to hide and once more to show the dynamic interactive window

Matrices