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.
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):
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
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.
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
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
and
The first formula shows that the numerator is a product of factors that range from n down to n−k+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
answer = 1
for denominatorFactor in range(1, k+1):
numeratorFactor = n + 1 - denominatorFactor
answer = answer * numeratorFactor / denominatorFactor
return answer
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.
A nice formula for the sum of binomial coefficients is
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:
