15-110 Spring 2011 Homework 6
Due Monday, 28-Mar, at 10pm

Same basic directions as hw5, so read those carefully (replacing "hw5" with "hw6", where appropriate, of course).

Additional notes:

• We are not providing you with starter files this week.  Name your files correctly (exactly as specified), and place them in a folder named hw6, zip that folder into hw6.zip, and submit hw6.zip in Autolab.
• Reminder:  portions marked SOLO must be solved entirely on your own (you may discuss with course staff, but not with each other or any outside sources).  See syllabus for details.
• There are no more restrictions on what you may use -- "if" statements (conditionals), "for" or "while" statements (loops), lists, recursion, or any other collections (dictionaries, sets, etc).
• Note that the points (without bonus) total to 90/100.  The remaining 10/100 points are for style.
• Also note:  From this assignment on, we will be using the autograding feature on Autolab to give you early feedback and scores on some parts of the assignment (though on this particular assignment that will basically be limited to checking that you uploaded the correct files). The autograder is started as soon as you submit a zipfile, and will update the score and feedback fields on the appropriate questions once it has finished (which can take from a few seconds to a minute, depending on the current load on the server); you can see them by clicking on 'View Scores' on the assignment page. Please check your autograded feedback after submitting to make sure that your files were uploaded properly!
• Note:  As of the release date of this homework, you will have to use IDLE rather than CLEESE for Tkinter.  If you do not know how to run IDLE, you should be able to get it installed and running by visiting python.org, but if you still have trouble, you should see a CA or instructor asap!  In particular, if you are having trouble getting IDLE working on a Mac, you might try installing an earlier version, specifically version 2.6.4 from here.
  

---

1. SOLO Vicsek Fractal (Recursive Graphics)  [15 pts]
   In recitation last week, we studied this program that uses recursion and Tkinter graphics to draw a Sierpinski Triangle, where the depth of the recursion is determined by the user pressing a digit key.  In the file hw6.1-solo.py, write a Tkinter program based on this approach that draws Vicsek fractals that fill a 400x400 window, where a Vicsek fractal is like so (where the depth is determined each time the user presses a digit key):
   
   
   
2. SOLO Basic Graphics and Animations  [25 pts]
   
1. Click in the circle! [10 pts]
   In the file hw6.2a-solo.py, write a Tkinter program in which a blue circle of radius 10 moves horizontally from left to right along the vertical center of a 300x300 window.  As the circle exits the right-hand side, it should reappear on the left-hand side.  You should display a score, initially 0, in an 18-point font centered horizontally near the top of the window.  Each time the user presses the mouse, if it is in the circle, they score 1 point, and if it is outside the circle, they lose a point (unless they would score negative points, in which case they remain at 0).  Finally, try different speeds (by storing the speed in a well-named variable), and submit what you think is the speed that makes this the most fun to play, along with a brief explanation in a comment at the top of your file as to why that speed is preferred.
   
   
2. Optical Illusion: Stroboscopic Alternative Motion (SAM) [15 pts]
   In the file hw6.2b-solo.py, write a Tkinter program which demonstrates the Stroboscopic Alternative Motion as shown in the animation on this page (with some minor changes so we don't require GUI elements like buttons and such).  Specifically, make the window about the same size as that animation, and draw the blue circles at about the same size.  Initially, they should update 2 times per second.  If the user presses "h", hide the vertical bar if it was visible, and then toggle the visibility of the horizontal bar (so if it is visible, hide it, and vice versa,).  If the user presses "v", hide the horizontal bar if it was visible, and then toggle the visibility of the vertical bar.  Each time the user presses a digit from 1 to 9, change the speed to update that many times per second (so if the user presses "6", your circles should switch positions 6 times per second).
   
   
3. SOLO Reasoning About Code (Mystery Functions)  [15 pts; 3 pts each]
   In just a few words of plain English (in your hw6.doc file), state what each of the following functions does in general.  You will receive no credit for describing the line-by-line low-level behavior of the code.   For example:
   def mystery(list):
       count = 0
       for value in list:
           if (value == 0):
               count += 1
       return count
   Correct answer:  "This function returns the number of 0's in the given list."  Or, if you prefer to be succinct, just:  "number of 0's".
   Incorrect answer (no points):  "This function sets count to 0, then sets value to each element in list in turn, and for each value, if it is 0, it adds one to count, and then returns count".  This is all true, but completely misses the high-level behavior of the function, and so would receive zero points.
1. def f(n):
      # assume n is a non-negative integer
      if (n < 10):
         return 1
      else:
         return 1 + f(n/10)
   
   
2. def f(a):
      # assume a is a list of strings
      if (len(a) == 0):
         return ""
      else:
         x = f(a[1:])
         if (len(x) > len(a[0])):
            return x
         else:
            return a[0]
   
   
3. def f(a):
      # assume a is a list of integers
      if (len(a) == 0):
         return 0
      elif (len(a) == 1):
         return (a[0] % 2)
      else:
         i = len(a)/2
         return f(a[:i]) + f(a[i:])
   
   
4. def f(n):
      # assume n is a non-negative integer
      if (n == 0):
         return 1
      else:
         return 2*f(n-1)
   
   
5. def f(n):
      # assume n is a non-negative integer
      if (n == 0):
         return 0
      else:
         return f(n-1) + 2*n - 1
   # Hint: you may want to try this function with a few sample values.
   # The answer should quickly become apparent, though you may wish to
   # think about why the answer is in fact what it is.
   
   
4. Collaborative Bitmap Editor  [15 pts]
   Note:  You may only collaborate on this problem with up to 2 other students, both of whom must be enrolled in 15-110 this semester.  If you do collaborate, you must list the students with whom you collaborated in a comment at the top of your file.
   In the file hw6.4-collab.py, write a Tkinter program in which the user can edit a simple bitmap.  At the start, your program should display a 16x16 grid (in a 400x400 window) of blank white squares with a black outline.  If the user clicks in a square, it should change from white to black, or if clicked again, from black to white.  If the user presses "s", you should save the bitmap in a file on the desktop named "hw6-bitmap.txt".  You can use whatever file format you wish.  If the user presses "l" (lowercase "L"), you should load the bitmap from the "hw6-bitmap.txt" file that you stored on the desktop.  You are not responsible if the file is not present or is not saved by your own program.
   
   
5. SOLO Readings in Computational Thinking  [20 pts]
1. SOLO Programming Maxims
   There are numerous websites dedicated to programming humor and/or clever quotes.  For example, back in his CMU teaching days, Rich Pattis built up this list:
   http://www.cs.cmu.edu/~pattis/quotations.html
   
   Read these, then briefly explain each of the following:
1. There are only 10 different kinds of people in the world: those who know binary and those who don't.  (Anonymous)
2. Why do programmers always get Christmas and Halloween mixed up? Because DEC 25 == OCT 31.  (Anonymous)
   Hint: in programming, OCT is sometimes a shorthand for "octal", which is base 8.
   
3. Weeks of programming can save you hours of planning..  (Anonymous)
4. Testing can show the presence of errors, but not their absence.  (E. Dijkstra)
5. “Measuring programming progress by lines of code is like measuring aircraft building progress by weight.”
   (Bill Gates)
   
6. Google the term "recursion", then briefly explain the joke Google is making.
2. SOLO Golan Levin's Art that Looks Back at You
   First, watch the video Golan Levin makes art that looks back at you.  Then, answer these questions:
   
1. For each of the following, briefly state both its artistic goal and at least one technical/programming challenge that Golan faced in creating it:
1. Interstitial Fragment Processor
2. re:MARK
3. Snout
2. Which interactive piece in Golan's video uses recursion in an interesting way?  Explain (briefly).
6. Bonus/Optional: More Optical Illusions [10 pts]
1. SOLO Bonus/Optional: Biological Motion  [4 pts]
   In the file hw6.6a-solo-bonus.py, write a Tkinter program which demonstrates the Biological Motion as shown in the animation on this page (again with some minor changes so we don't require GUI elements like buttons and such).  Specifically, make the window about the same size as that animation, and draw the white circles in about the same size and locations.  Your animation should initially be paused, but each time the user presses "p" this should toggle.  When playing, the motion of each circle should match (fairly closely, if not exactly) the motion of the corresponding circle in the example, thus producing the effect of "biological motion" in your program.
   
2. Collaborative Bonus/Optional: Motion Aftereffect  [6 pts]
   Note:  You may only collaborate on this problem with up to 2 other students, both of whom must be enrolled in 15-110 this semester.  If you do collaborate, you must list the students with whom you collaborated in a comment at the top of your file.
   In the file hw6.6b-collab-bonus.py, write a Tkinter program which demonstrates the Motion Aftereffect as shown in the animation on this page Actually, you are only responsible for the motion in the circle, and not for displaying the image (the Buddha).  You also do not need any buttons or to respond to any keypresses -- just play the animation.  You may wish to look into the canvas.create_arc method.