# MCS-178 Warmup Project (Spring 2010)

No report is needed for this ungraded warmup project. The directions assume you are using a computer in the MCS lab that is booted to Mac OS X. Log in using the same name and password as you use for Gustavus email. Here is a schedule for your work:

Tuesday, February 9: Part I and, to the extent you have time, Part II.
Thursday, February 11: Part III and, to the extent you have time, Part IV.

## I. Introduction to Python using TurtleWorld

We will start out our exploration of Python by using a nice graphical "playground" for experimenting with basic Python commands. The environment is called "TurtleWorld."  To work with TurtleWorld, first open a terminal window. The Terminal application is the one that looks like this:

Next, type the following command in the terminal window to start up TurtleWorld (hit "Enter" once the command is complete):

python ~mc28/www-docs/S2010/projects/warmup/TurtleWorld.py

A window labeled "TurtleWorld" should open, though you will probably need to use your mouse to bring it to the front.  In the lower right of this window is a text area where we will be typing in Python code. Right now, it has two lines of code "world.clear()" and "bob= Turtle(world)."  It is not so important at this point to understand the syntax of these lines, but to see what they do when interpreted by Python, click the "Run code" button.  A turtle should appear in the large white space inside the window.

Modify the code as follows and hit "Run code"

world.clear()bob = Turtle(world)for i in range(100):    fd(bob, i)    lt(bob, i)

In Python, spaces and tabs are used to indicate lines of code that are to be treated as a unit. Here we want the last two lines to be executed inside the "for" loop, so we indent them.  Note that the two commands fd(bob,i) and lt(bob,i) cause the turtle to move. How so?

The commands "fd, bk, lt, rt, pu, pd" control the turtle as follows:
fd(t, n) - move turtle named "t" forward n units
bk(t, n) - move turtle named "t" backward n units
lt(t, n) - turn turtle named "t" left n degrees
rt(t, n) - turn turtle named "t" right n degrees
pu(t) - lift the drawing pen up for turtle "t"
pd(t) - lower the drawing pen down for turtle "t"

In the previous example, bob moves i units and turns left i degrees, for each value of i in the range from 0 up to but not including 100.

If the turtle's pen is down, it will draw as it moves, otherwise no drawing will occur.  Try to create code that will do the following:

1) Make bob draw a square.
2) Have two turtles draw squares.
3) Make bob draw a hexagon.

Now, try the following code:

for i in range(4):     print 'Hello!'

When you run this, nothing happens in the turtle window.  This is because Python interprets the print command to mean "print to the terminal window."  If you go to that window, you will see the four lines of output.  The point of this example is that when we initially started Python by executing a shell command

python ~mc28/www-docs/S2010/projects/warmup/TurtleWorld.py

the command loaded in the Python file TurtleWorld.py and executed it. This file contains lots of Python code to create the Turtle Window, create turtles, handle drawing commands, etc. However, the simple command "print 'Hello!'" is interpreted directly by Python and the result of the command is sent directly to the terminal window.

## II. Playing in TurtleWorld some more

Chapter 4 of Think Python contains lots of activities based on TurtleWorld.  Choose some that look interesting and try them out. Actually, I'd also encourage you to do any other playing around with python, for example based on earlier chapters. For now, just type your code into the TurtleWorld window.  We will look at how to create individual Python files (like TurtleWorld.py) in an editing environment in the next part of this lab.

Note: If you want to install TurtleWorld on your own computer, you can get it as part of a package called "Swampy" that was created by the author of Think Python.  Go to http://thinkpython.com/swampy/install.html. You can use a terminal window to execute the wget, unzip, and cd commands that are shown there. Once you have done the cd command, you can enter the python command and it will be running in the Swampy directory. If you login again on a future day, you can skip the wget and unzip parts and start with the cd command.

## III. Editing and Running a Python Script to Find Combinations

Now we will leave the environment of TurtleWorld and look at how to create and edit programs (or "scripts") in Python.  Python scripts can be created using any general text editor and then run in a terminal window. However, it can be useful to use an integrated development environment (IDE) that includes both an editor and a python interpreter.  The editor will highlight Python syntax and automatically indent lines as you type.  We will use the IDE named "Idle" which is itself written in Python.  To start Idle, type

python -m idlelib.idle

in a terminal window.

A window titled "Python Shell" will open, though as with TurtleWorld, you may need to use your mouse to bring it to the front.  To edit a separate script, choose File->New Window.  In the script window that opens (the one titled "Untitled"), you can type in code without having it immediately run.

We will create a Python script to compute the number of ways to choose k objects from a set of n objects. This number is sometimes called "n choose k"  or the number of combinations of k things from n things.  It is also called a "binomial coefficient."

Given a non-negative integer n and an integer k, the number of combinations, C(n, k), is defined as

${n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)} {k \cdot (k-1) \cdots 1} = \frac{n!}{k!(n-k)!} \quad \mbox{if}\ 0\leq k\leq n \qquad (1)$

and

${n \choose k} = 0 \quad \mbox{if } k < 0 \mbox{ or } k>n$

The first formula shows that the numerator is a product of factors that range from n down to nk+1 and the denominator is a product of factors that range from k down to 1. It is tempting to compute these two products and then divide, or even use the second version, where we start by computing n! and then divide by two other factorials. The problem with this simple approach is that the products can grow unnecessarily large. Python can handle integers of arbitrary size, but calculations with such large values can be quite slow.

A better algorithm for computing C(n, k) doesn't wait until it has multiplied all the numerator factors together before it starts dividing by the denominator factors. Instead, the algorithm goes through a loop, each time updating its answer to incorporate both one more factor from the numerator and one more factor from the denominator. The answer gets multiplied by the numerator factor and divided by the denominator factor. The divisions keep the answer from growing unnecessarily large.

If we process the factors in the order they are listed, we'd start with n in the numerator and k in the denominator. The only problem is that n may not be divisible by k, so we'd have to leave the nice clean world of integers. A better approach processes the denominator factors in the reverse order, from 1 up to k. That way, after one trip through the loop the answer is n/1, after a second trip through the loop the answer is n*(n−1)/(1*2), etc. Each of these answers is definitely an integer, because they are C(n, 1), C(n, 2), etc. Here is the code:

def c(n, k):
if k > n:
return 0
if k < 0:
return 0
for denominatorFactor in range(1, k+1):
numeratorFactor = n + 1 - denominatorFactor
answer = answer * numeratorFactor / denominatorFactor


In this code, we are using some new constructs. We saw the for loop in the TurtleWorld example, but here we use a slightly different form of the range expression.  The expression range(1, k+1) means that the loop will start at 1 and end just before reaching k+1. Each time through the loop, a numerator factor is calculated to go along with the denominator factor and then a new version of the answer is calculated by updating the old version.

We are also using if statements. This construction should be self-explanatory. It is also described in Chapter 5.

Enter the code into the editor window in Idle.  To evaluate the procedure, choose Run->Run Module from the menu bar or hit the F5 key. Whenever you evaluate code, Idle will ask you to save it first. This can be a bit annoying, but that is the way Idle is set up.

In the Python Shell window, the prompt will switch to a new line, indicating that the code was evaluated successfully.  To test the code type
c(11,4)
at the last prompt (>>>) in the Python Shell window and hit return.  You should get the same answer as for 11*10*9*8/(4*3*2*1).

Notice that this procedure does not print anything out; instead, it returns a value. When you evaluate c(11,4) in the Python Shell, the value gets printed out, but that is just because the value of any expression you enter gets printed, not because the procedure itself is doing the printing. If you enter a different expression, such as 7+c(11,4), you will see a different value that does not come directly from the procedure.

Having the procedure return its value makes it useful as part of other computations. However, during debugging you might find some printing useful as a way of understanding what the procedure is doing. Try adding the following as a third line inside the for loop:
print denominatorFactor, numeratorFactor, answer
Run the modified procedure and make sure you understand the printed values.

The correct value of c(11,0) is 1, because there is only one way to choose zero items. Can you explain how the procedure gets this case right?

Suppose that k isn't so large that it is greater than n, but is large enough that 2*k > n. In this case, the computation can be made faster, without changing its result, by using n-k in place of k. Add a third if statement to accomplish this optimization and check that it works.

Once you are done understanding and modifying the procedure, you can save it away as a tool that may be useful in the future. But first you should turn the print statement into a comment so that the output doesn't show up every time the procedure is used. You can do this by putting a # character at the beginning of the line.

## IV. Binomial Formula

A nice formula for the sum of binomial coefficients is

$\sum_{k=0}^n \tbinom n k = 2^n, \qquad\qquad(5)$

Create a procedure, binom_sum(n) that sums up the combinations C(n, k) from k=0 to k=n and verify that you do indeed get 2n. (In Python, the power of two can be calculated as 2**n.)

If you have extra time, create a procedure to verify the following formula:

$\sum_{k=1}^n k \tbinom n k = n 2^{n-1} \qquad(6)$