15-112 Spring 2013 Homework
Due Monday, 4-Feb, at 9pm
Read these instructions first!
- Same rules as hw2 apply.
- There is no starter file, and no public autograder this week. You
may wish to pattern your file after the hw2.py file. In particular, be
sure to place your graphics code below the #ignore_rest line, which you must
add! Again, see the hw2.py file for details.
- This entire hw is COLLABORATIVE.
You will work in groups of up to 3 other students who are in this course
this semester (and then with nobody else except current CA's and
instructors). You may not split up the work -- everyone must work on every
problem. And you may not simply copy any code but rather truly work
- bonus/optional: Turkey Bonus!
- randomCircleFun [15 pts]
Write the function randomCircleFun that takes a canvas, and a left, top,
width, and height of a rectangular area of that canvas, and fills that
area with randomly-generated circles so that the image looks very much
like a reasonable variation of this image (ignoring the water mark):
Note that the image uses alpha transparency, and of course with Tkinter
you cannot, so don’t worry about that. But you should use roughly the
same size circles and the same color scheme. Hint: you will have to
import random and then you can use the function random.random() to get a
float between 0.0 and 1.0, or random.randint(lo,hi) to get a random
integer between lo and hi.
- nthPalindromicPrime [15 pts]
A palindromic prime number is a number that is both prime and a palindrome –
the same forwards as backwards. The first several palindromic primes are: 2,
3, 5, 7, 11, 101, 131, 151, 181, 191, 313,… With this in mind, write the
function nthPalindromicPrime(n) for non-negative int n.
- nthSmithNumber [15 pts]
Write the function nthSmithNumber that takes a non-negative int n and
returns the nth Smith number, where a Smith number is a composite
(non-prime) the sum of whose digits are the sum of the digits of its prime
factors (excluding 1). Note that if a prime number divides the Smith number
multiple times, its digit sum is counted that many times. For example, 4
equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith
Number. The first few Smith numbers are 4, 22, 27, 58, 85, 94, 121, ... You
may read more about Smith numbers
- findZeroWithBisection [15
Aside: as we will cover more carefully later in the course, a function may
take another function as an argument. For example, consider this code:
def f(g, x):
print f(h,3) # prints 16
Here, we define a function f whose first argument is another function.
On the last line, we call f providing the function h, which is bound in f to
the parameter g. Hence, calls to g in f are really calls to h. Play around
with the sample code to get the hang of this idea. Then, read the next
In mathematics, one way to numerically (as opposed to algebraically) find a
zero of a function f(x) is to use what amounts to binary search. To start,
we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1)
have different signs (so one is positive and the other is negative). Hence,
by the Intermediate Value Theorem, we know there is some value x in the
range [x0,x1] such that f(x)=0. It is that value of x that we are seeking.
How? First, try the value xmid, which is the midpoint between x0 and x1.
If f(xmid) is exactly 0, we are done! Otherwise, we can divide our range in
half as such: if f(xmid) and f(x0) are the same sign, use the range [xmid,
x1]. Otherwise, f(xmid) and f(x1) must share the same sign, so use the
range [x0, xmid]. We repeat this in a loop until x0 and x1 are within some
suitably small epsilon.
With this in mind, write the function findZeroWithBisection that takes a
function f, a float x0, a float x1, and a float epsilon, and returns an
approximate value x in [x0,x1] where f(x) is approximately zero. Your
function should stop when x0 and x1 are within epsilon, and at that time
should return the midpoint of that range. Note that if it is not true that
exactly one of f(x0) and f(x1) is negative, your function should return the
Python value None, signifying that the bisection method cannot be used on
the given range.
Let's see this in action! First, we'll use it to approximate the square
root of 2 without the ** operator:
print "use bisection to
def f1(x): return x*x - 2 # root at x=sqrt(2)
x = findZeroWithBisection(f1, 0, 2, 0.000000001)
print " x =", x # prints x = 1.41421356192
print " check: x**2 =", (x*x) # prints check: x**2 = 1.99999999871 (really
Next, let's use it to approximate phi (the
golden ratio), without using the closed-form solution ((1 + sqrt(5))/2),
instead using the interesting property of phi that adding one to it is the
same as squaring it. That is, ((phi + 1) == phi**2). How do use that?
Simple, convert it into an equation equal to 0: phi**2 - (phi + 1) == 0.
Now we're set! (Of course, we could just use the Quadratic Formula here,
but it's more interesting to use bisection, now that we have it!).
print "use bisection to
approximate phi (the golden ratio):"
def f2(x): return x**2 - (x + 1) # root at x=phi
x = findZeroWithBisection(f2, 0, 2, 0.000000001)
print " x =", x # prints x = 1.61803398887
phi = (1 + 5**0.5)/2 # the actual value (to within Python's
floating point accuracy)
print " check: x/phi =", (x/phi) # prints check: check: x/phi =
The previous two examples are nice, but simpler techniques than bisection
would have worked as well. So let's solve a problem that would be hard to
solve without bisection (or some other numeric approximation algorithm).
Specifically, find a number x such that x5 == 2x:
print "use bisection to
approximate x where x**5 == 2**x"
def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
x = findZeroWithBisection(f3, 1, 2, 0.000000001)
print " x =", x # prints x = 1.17727855081
print " check: x**5 - 2**x =", (x**5 - 2**x) # prints check: x**5 - 2**x =
Hopefully this bisection excursion helps you appreciate the awesome
computational power that about 10 lines of Python can have!
Background: A right-left route
cipher is a fairly simple way to encrypt a message. It takes two values,
some plaintext and a number of rows, and it first constructs a grid with
that number of rows and the minimum number of columns required, writing the
message in successive columns. For example, if the message is
WEATTACKATDAWN, with 4 rows, the grid would be:
W T A W
E A T N
A C D
T K A
We will assume the message only contains uppercase
letters. We'll fill in the missing grid entries with lowercase letters
starting from z and going in reverse (wrapping around if necessary), so we
W T A W
E A T N
A C D z
T K A y
Next, we encrypt the text by reading alternating rows first to the right ("WTAW"),
then to the left ("NTAE"), then back to the right ("ACDz"), and back to the
left ("yAKT"), until we finish all rows. We precede these values with the
number of rows itself in the string. So the encrypted value for the message
WEATTACKATDAWN with 4 rows is "4WTAWNTAEACDzyAKT".
With this in mind, write the function encodeRightLeftRouteCipher that takes
an all-uppercase message and a positive integer number of rows, and returns
the encoding as just described.
Write the function
decodeRightLeftRouteCipher, which takes an encoding from the previous
problem and runs it in reverse, returning the plaintext that generated the
encoding. For example, decodeRightLeftRouteCipher("4WTAWNTAEACDzyAKT")
- bonus/optional: Turkey Bonus! [up to
On last semester’s schedule, you can find some code I wrote to give everyone
a Thanksgiving message. For small points, figure out how it works, and
explain in plain English how it works. To actually generate the encoded
version of the message that’s in the Python code online, I wrote a second
program, not included there, that took my real message and converted it to
that form. Actually, I also used the output of a Linux program called
“banner”, and you may do the same. Your task is to write that second
program, the one that takes a plaintext English message and converts it into
one encoded like the one in the program. Place your solution to the bonus
problem at the very top of your submission, and include the free-response
English text in a comment there, too. Enjoy!
carpe diem - carpe
diem - carpe diem - carpe diem - carpe diem - carpe diem -
carpe diem - carpe diem - carpe diem