- Previous Practice
Quizzes [10 pts]
First take the following quizzes under quiz conditions, and then using a computer as you wish (and CA's, office hours, etc, but still under the "solo" rules), write a solution set to each, placing those solutions in a triple-quoted string at the top of hw4.py that you submit. Do this for each of these: - Bitwise Operators [10 pts; 1 pt
for f0, 1.5 pts each for f1-f6]
Each of the following functions use bitwise operators (or, in one case, binary representations, which are of course quite similar) to compute an everyday function. For each function, very briefly explain what the function is computing in everyday English terms, and then explain why it works in general (do not just say what the function does line-by-line (which is obvious by looking at it), but why that works in general!). Place your solutions in the triple-quoted part of your hw4.py file just after your solutions to the previous exercise (the quizzes). Hint: more than one of these returns True if its argument is a power of 2. You should assume the parameters are always integer values.
Hints:
* Multiple assignments are done in parallel (so all the right-hand sides are computed first and then they are all assigned to the variables on the left-hand side). For example:
(x, y) = (4, 1)
(x, y) = (x+y, x-y)
print (x,y) # prints (5,3)
* For all values A and B:
* A & 1 == just the 1's bit of A == A%2
* A ^ 0 == A
* A ^ A == 0
* Putting the previous two together, A ^ B ^ A == ?
* -1 is 0b111...1111 (all 1's in binary, due to 2's complement representation)
* The high-order (leftmost) bit is the sign bit, 0 means positive, 1 means negative.def f0(x): return ~(~x - x) def f1(x, y): return (x ^ y) < 0 def f2(x, y): return y ^ ((x ^ y) & -(x < y)) def f3(x): return x and not (x & (x-1)) def f4(x): (result, y) = (0,x) while (y>0): (y,result)=(y>>1,result+(y&1)) return (x>0) and (((result-2) ^ result) < 0) def f5(x): return (x>0) and (bin(x).count("1") == 1) def f6(x,y): x ^= y y ^= x x ^= y return (x,y) - Efficiency:
Multiplication Functions [10 pts, 2.5 pts each]
Each of the following functions takes two integers x and y and returns the product x*y. Interestingly, none of them uses multiplication, instead accomplishing this using addition and bitwise operators. For each function first very briefly describe in a few words how the function works at a high level. Then, find the big-Oh number of steps (additions or bitwise operations) required to use the function to square the value N where N is a non-negative integer (so you would call f(N,N), which returns N*N). Place your solutions in the triple-quoted part of your hw4.py file.def h1(x, y): # interesting note: this is basically the ancient Egyptian multiplication algorithm! # And it only uses addition to multiply! Cool! assert((x>0) and (y>0)) (hi, lo) = (max(x,y), min(x,y)) (product, addend) = (0, hi) while (lo > 0): if (lo&1): product += addend addend += addend lo = lo >> 1 return product def h2(x, y): assert((x>0) and (y>0)) result = 0 for m in xrange(x): for n in xrange(y): result += 1 return result def h3(x, y): assert((x>0) and (y>0)) (hi, lo) = (max(x,y), min(x,y)) # hint: (x-m)(y-m) = xy - m(x+y) + m**2 result = 0 while (lo > 10): result += 10*(lo+hi) - 100 (lo, hi) = (lo-10, hi-10) while (lo > 0): (lo, result) = (lo-1, result+hi) return result def h4(x, y): assert((x>0) and (y>0)) (hi, lo) = (max(x,y), min(x,y)) product = 0 for i in xrange(lo.bit_length()): if (lo & (1<<i)): product += hi<<i return product
- encodeRightLeftRouteCipher
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 have:
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.
Hint: the grid is only conceptual. Your code will never actually construct a 2-dimensional grid (especially as you may not yet use lists!). Instead, you should use a clever scheme of indexing the message string where you translate a row and column into a single index into the message string.
- decodeRightLeftRouteCipher
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") returns "WEATTACKATDAWN".
-
findZeroWithBisection
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 h(n):
return n+5
def f(g, x):
return 2*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 preliminary topic...
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 approximate sqrt(2):"
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 close!)
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 = 1.00000000007 (nice!)
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 = 3.63570817896e-09 (great!)
Hopefully this bisection excursion helps you appreciate the awesome computational power that about 10 lines of Python can have!
- unboundedNumberGuessing
As we covered in class, guessing a number between 1 and N is a basic application of binary search. But what if you don't know the upper bound? Or even the lower bound? What if I asked you to guess the number I am thinking of, and I tell you nothing of its value. It might be 42, but it might be -42 quadrillion. Hmmm. To solve this, first guess 0. If it is right, you're done! Amazing luck! Otherwise, if it is too low, we know N is positive. In that case, we have to determine an upper bound for N. How? Try 1. If that is too low, double it to 2. And keep going until you find your upper bound. This is kind of like inverse binary search. Cool! Also note that you know your lower bound is the next-to-last value you tried. So if N==5, you would guess 1, then 2, then 4, then 8, and at that point you would know that N is between 4 and 8. Actually, since you'd know that 4 and 8 could not be N, you would know N is between 5 and 7 inclusively. Now, what if N is negative, and our first guess of 0 was too high? Then you would do the analogous operations to find the lower bound. In any case, once bounded above and below, this reduces to everyday binary search. With this in mind, write the function unboundedNumberGuessing(n) that takes an integer value n and returns a comma-separated string of all the values in order required to find the value n. Also, in a triple-quoted string just above the function, find the big-oh number of guesses this function requires to find an arbitrary value n. So, for example:
unboundedNumberGuessing(42) returns "0,1,2,4,8,16,32,64,48,40,44,42"
and
unboundedNumberGuessing(-13) returns "0,-1,-2,-4,-8,-16,-12,-14,-13"
- drawCircularPattern
Write the function drawCircularPattern(canvas, x0, y0, x1, y1, points, color). This function takes a canvas, four int values x0, y0, x1, y1, a non-negative integer number of points, and a color string (such as "blue"). The function first draws a black rectangle bounded by (x0,y0) and (x1,y1), and inside that rectangle at the top-left displays the number of points. The rest of the drawing is in the given color. Next, it draws the largest possible circle that is centered inside the given rectangle without extending beyond its borders. Now, think of there being points evenly distributed around the perimeter of the circle, with one of the points being on the vertical. The next step is to a draw a line connecting every pair of such points. That's it. Here is a sample test function:def testDrawCircularPattern(): print "Testing drawCircularPattern. See drawing to confirm this passed." root = Tk() canvas = Canvas(root, width=550, height=400) canvas.pack() # some simple examples drawCircularPattern(canvas, 50, 25, 250, 125, 3, "red") drawCircularPattern(canvas, 50, 150, 250, 250, 4, "black") drawCircularPattern(canvas, 50, 275, 250, 375, 5, "green") # and now a more interesting one drawCircularPattern(canvas, 300, 50, 500, 350, 20, "blue") root.mainloop()And when you run that function, you should see this window:
-
justifyText [5 pts]
Write the function justifyText that takes a string (which may be multi-line, or just one potentially very long line) and a width (which you may assume is a positive integer), and returns that same text as a multi-line string that is left- and right- justified to the given line width. For example, consider the following text:text = """\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""
WIth this text, a call to justifyText(text, 30) would return this text left- and right-justified with 30 characters per line, as such:
"""\ We hold these truths to be self-evident: that all men are created equal; that they are endowed by their Creator with certain unalienable rights; that among these are life, liberty, and the pursuit of happiness."""
Here are some specifics to keep in mind:- You should first replace all sequences of any length of whitespace (spaces, tabs, newlines) with a single space.
- Then, for each line except the last line, find the space as far to the right as possible while still allowing the line to remain under the given width restriction. That space will be replaced with a newline ("\n").
- What if a line has no such space, and instead it is solid non-spaces? This is unlikely, but we still have to deal with it. In this case, just insert a newline at the given line width. Do not add a hyphen in this case.
- Now, unless the line is a perfect fit in the given width (as in the second line above ), you will have to add some extra spaces to make it fit exactly. Consider the first line in the example above ("We hold these truths to be"). There are 5 total spaces (one between each word), and since the line is 26 characters long, it requires 4 more spaces to pad out to a width of 30. This is done by adding an extra space to each space from left-to-right. In this case the first 4 spaces are now 2 spaces, and the last space is still one space. This process works in general, so you may have to add more than one extra space of padding to each gap (such as the 3 total spaces between "certain" and "unalienable"), and there cannot be more than a 1-space difference between any two gaps on a line, and the extra spaces must all be on the left side of the line.
- The last row is not justified.