T-Th 9:05
T-Th 11:15
in Olin 155

CS 1110: Introduction to Computing Using Python

Spring 2014

Assignment 2:
Frame and Object Notation

Due IN CLASS on Tuesday, March 4th

Authors: S. Marschner, L. Lee, W. White, D. Gries


One-shot Submission From Now On

This assignment, and all subsequent ones unless otherwise noted, will receive a single grade; there is no revise-and-resubmit like there was for Assignment 1.

Collaboration Policy

You may do this assignment in groups of size one up to four. If you are going to work together, then form your group on CMS as soon as possible. This must be completed before you submit the assignment, even though you are handing the assignment in on paper. It takes actions on CMS from all parties to form the group. You can have different groups for each assignment.

You may not collaborate with anyone other than your CMS-registered partners. You should actively collaborate with all your group members because you, individually, need to know this stuff cold for the exams.

Learning Objectives (Which Have Grading Implications)

The purpose of this assignment is to give you practice executing Python code on paper using the notation we have introduced in class. You need to be able to do this quickly and confidently—uncertainty about what to draw is a sign that you don't really understand what the programs you write are going to do.

The importance of the notation we have introduced in class is that it gives us a precise visual language for describing and understanding exactly what Python is doing when it executes code. In this assignment, you will use this notation to demonstrate your understanding of what happens during the execution of a given sequence of statements, and on exams you will likewise use this same language to prove your understanding. In complex coding situations, we use these kinds of diagrams ourselves to figure out what's going on.

Concepts tested:

  • What statements create variables or change the values of what variables (including global variables, local variables, and object attributes).
  • That the result of a constructor expression is the ID of the new object that is created.
  • That frames summarize the state of the process of executing a function call. The variables they contain store information local to the corresponding function, and indicate what that function can affect; the program counter records what line number should be executed next.
    • Parameters are local variables that serve the purpose of holding the input values that the function is supplied when called.
    • Arguments are the input values that are supplied to a function when the function is called, and are assigned to the corresponding parameter variables.
  • Which statements of an if-statement are executed in a given setting.
Given these learning objectives, some seemingly minor but actually tragic mistakes you can expect to lose points for committing are:
  • Drawing fewer objects in your drawing than the number of constructor expressions that are evaluated during execution.
  • In the frame for a call to a function, not drawing a correspondingly named box for each parameter in that function's header.
  • Drawing non-existent variables (indicating that you believe in their existence).
Some seemingly minor notational mistakes that could indicate deeper misunderstandings and thus risk point deductions are:
  • Writing the name of a variable, say x, inside of the box for another variable, say a box named y, instead of a value [The problem: if x's value is subsequently changed, you would predict the wrong value for y].
  • Writing a variable name on the tab of an object instead of a value [The problem: if the variable's value changes, you would incorrectly predict that the object's ID changes too].
  • Not having the correct sequence of crossed-out line numbers in the frame's program counter [The problem: you might be misunderstanding where the flow of execution goes next].
Additionally, it would be silly if the final values of the variables on your paper are not the same as the ones that result when you actually run the code on your computer using Python itself.

Getting Help

If you do not know where to start, if you do not understand how function calls work, or if you feel completely lost, please talk to someone immediately. This could be an instructor, a TA, or a consultant. Do not wait until the last minute! See the staff page for drop-in office hours and other contact information.

Notational Conventions

Most of our notational conventions for this assignment follow the lecture notes. There's a one-slide summary of “How to Draw Things” on the Lecture 6 handout. When you are using the frames-and-objects notation on paper:

  • Do not erase any values, objects, or frames. For values that are changed, the old value should be neatly crossed out such that we can see what the old value was; and the new value should be written next to it. Similarly, frames should be crossed out rather than erased, and objects should never be removed.
  • When function execution ends, cross out the final value of the program counter. The series of crossed-out program counter values is a record of which lines were executed during the function call.
  • If a function call returns some value v, write “Return: v” just below or to the right of the crossed-out frame. For example, “Return: 3” for a function call that returned the integer value 3. (Be sure you are writing a value, not a variable name.)
  • Place your frames so that their position reflects the order in which they were created; we recommend starting at the top and drawing each frame below the previous one.
In this assignment you don't need to bother with the module name in the function frames, since there is only one module involved.

Depicting the Creation of New Objects

Since we haven't covered class definitions in detail yet, assume that the creation of a new object and initialization of its attributes happen in one step. (That is, don't worry about the __init__ function in the class Point2 or draw a frame for it. Later on in the course we will worry about this function.)

Worked Example

To help you with this assignment, we are providing a worked example. The code is a2_example.py. Here are two diagrams of the execution of the example code: one by Prof Lee and one by Prof Marschner. We give two solutions to give an idea about variations in notation we don't care about, like whether or not you draw a box around the class name in the upper-right of an object.

The Code to Execute

Below, and also in the file a2.py, is the code you are to work with. Your submission should consist of a diagram, compliant with the notational conventions discussed above, showing what happens during the execution of lines 44-50 when you run this script by typing “python a2.py”. Don't draw the class object for Point2 or the function objects for the five function definitions.

The class definition for Point2 in lines 5-9 below means that a constructor call like Point2(100,200) creates a new Point2 object with an x attribute holding the value 100.0 and a y attribute holding the value 200.0.

Employing our notation correctly is a way of proving that you know what a, b, c, h1, and h2 store or refer to, and that you know whether or not each function does what its specification claims it does. We'll tell you that our solution depicts 5 global variables, between 2 and 8 objects (inclusive), and between 5 and 8 crossed-out frames (inclusive). Our solution also indicates to us that at least one of the function specifications is actually incorrect.

1	# a2.py
2	# Steve Marschner (SRM2) and Lillian Lee (LJL2)
3	# Feb 24, 2014
5	class Point2(object):
6	    """A class representing points in a 2D plane."""
7	    def __init__(self,x,y):
8	        self.x = float(x)
9	        self.y = float(y)
11	def midpoint(p,q):
12	    """Return: a new point at the midpoint of the points p and q."""
13	    mx = (p.x + q.x) / 2
14	    my = (p.y + q.y) / 2
15	    mp = Point2(mx, my)
16	    return mp
18	def move_to_mid(p, q):
19	    """Move p to the midpoint of p and q."""
20	    p = midpoint(p,q)
22	def min_max(p, q):
23	    """Move p to bottom left and q to upper right of the rectangle they define."""
24	    if q.x < p.x:
25            t = p.x
26	      p.x = q.x
27	      q.x = t
28	    if q.y < p.y:
29	      t = p.y
30	      p.y = q.y
31	      q.y = t
33	def dist_sqr(p,q):
34	    """The squared distance between the points p and q."""
35	    dx = p.x - q.x
36	    dy = p.y - q.y
37	    return dx**2 + dy**2
39	def half_dist_sqr(p,q):
40	    """The square of half the distance from p to q."""
41	    mp = midpoint(p,q)
42	    return dist_sqr(mp, p)
44	a = Point2(1, 2)
45	b = Point2(5, 0)
46	c = midpoint(a, b)
47	min_max(c, a)
48	h1 = half_dist_sqr(a, b)
49	move_to_mid(a, b)
50	h2 = dist_sqr(a, b)

Using Python Tutor

You should definitely run this code on your computer, and add some print statements at the end to show you what values ended up where. You can catch most mistakes you might make by comparing your on-paper results to the results of actual execution.

You are also highly encouraged to use Python Tutor to step through the code above line by line and thus get a clearer picture of what Python does during execution. If you want to use Python Tutor, copy the contents of the file a2.py into it. (Don't copy from this web page, because you don't want to include the line numbers in Python Tutor.) You may want to change Python Tutor's “draw references using arrows” option to “use text labels for references”.

Be aware that some of Python Tutor's notational and display conventions differ from what we use in this class and are expecting on this assignment. Examples: it removes “lost” objects, which we don't; we are not including class folders or function objects (unless necessary—and it's not necessary in this assignment); Python Tutor produces a frame for __init__ whereas we're not asking you to do this for this assignment.

And note that on exams, you will need to understand what objects, frames, and variables are created and altered without having Python Tutor by your side. Just as an accomplished violinist can perform a concerto without the score and a neurosurgeon can identify the hippocampus without referring to a diagram, a proficient programmer can understand code by reading it, without having to try it out to see what it does. The ability to flawlessly predict the execution of programs just by looking at them will tell you (and us!) that you truly know how Python programs work.

Moreover, as we've often mentioned with respect to iClicker questions in class, you often learn more from making mistakes and being corrected than from being right the first time. We thus recommend that you try doing this assignment a bit at a time by hand, each time checking your partial answers against what Python Tutor produces.

Turning in the Assignment

When you finish the assignment, put the names and netids of all group members, last names in ALL CAPS, first names not in all caps, at the top of the page (your entire group should collectively submit just one sheet of paper). Otherwise, we will not know that the assignment is yours, and we cannot give you credit for your work; and if we can't tell your first name(s) from your last name(s), we may misfile your work or your grade. Remember whose name you put first; that is whose (last) name we will alphabetize the (single) group submission by, and you'll need to know this in order to pick up the grading feedback.

We highly recommend that before submission, you double-check your answers against the learning-objectives remarks made above.

Bring the assignment to class on the day it is due, Tuesday, March 4th, to hand it in. We will start grading this immediately in order to get you feedback significantly before the first prelim, so please make sure the assignment is turned in on time.

Course Material Authors: D. Gries, L. Lee, S. Marschner, & W. White (over the years)