[ answers in web view ]
Name: _______________________________ K E Y
Student ID: _______________________________

Unless otherwise specified, all questions pertain to Python.
Total points: 110
  1. Name the five steps to top-down problem solving as described in the text. (It's okay if you can't remember the exact wording; the concepts are more important.) [5]

    Write, Apprehend, Design, Execute, Scrutinize
    ___________ ___________ ___________ ___________ ___________
  2. Describe the five software control/flow abstractions mentioned in the text. For each one, also name a corresponding Python language construct. [5]

    Sequence (newlines in Python), Selection (if/elif/else), Repetition (while/for), Composition (def/functions), Parallelism
    ___________ ___________ ___________ ___________ ___________


  3. Fill in the blank: [18]
    1. "Computers are tools__________, and computing scientists are toolsmiths________________."
    2. The Python keyword used to introduce an exception handler clause is except__________
    3. Convert 110011101 from binary to hexadecimal: 0x19D_________
    4. What word describes functions which invoke themselves? recursion_______
    5. A requirement imposed by a function upon its parameters, such that the correctness of the result is not guaranteed if the requirement is not met, is called a precondition________________
    6. What is the type of the Python expression 2*[False] ? list________
    7. What special method name does Python use for the constructor/initializer method? __init__()____________
    8. Name the two Python program control constructs we learned which correspond to repetition: while, for________ __________
    9. In statically-typed languages, before we can use the value of a variable for the first time in
      a program, we need to ______________declare and ________________initialize it.
    10. An HSDPA cell-phone connection runs at 7.2Mb/s. Assuming full utilization of the bandwidth (which never happens in reality), how long would it take to download a 1.44GB file? Assume SI (decimal) units. It is okay to express your answer in seconds. 1600 seconds, or 26 mins 40 seconds_____________
    11. What method returns a list of all the indices in a dictionary? keys()________
    12. The Python method on file objects that returns current location in the file is called tell()__________
    13. What English part of speech should a function name be? verb___________
    14. What operator is used to indicate bitwise AND? &_______
    15. In Python, when a list is passed as a parameter to a function, the formal parameter becomes not a copy but an alias of the actual parameter. This semantics of parameter passing is called call by reference___________________________.
  4. Evaluate each of the following Python expressions exactly as given, or if it produces an error, describe the error. Assume each expression is independent of the others. Assume all necessary imports have been done. For all expressions, assume only the following initialization: [14] 
    	myPear = "Red Delicious"
	from math import pi
    1. 2 + 1>4 and (5/0 < 1) False
    2. 0x1e 30
    3. 10 | 6 14
    4. 12 % 3 0
    5. 2 * [2, 4, 6] [2, 4, 6, 2, 4, 6]
    6. "%03d%s" % (15.189, 'pears') '015pears'
    7. "%07.2f" % 3.1415926535 '0003.14'
    8. string.upper(Fuji) NameError: Bosc
    9. range(myPear) TypeError
    10. myPear[2:5] 'd D'
    11. 'b' + 'e' 'be'
    12. ord('b') - ord('e') -3
    13. 'b' - 'e' TypeError
    14. 'b' + 2*'e' + 'p' 'beep'

  5. List at least eight built-in Python types we learned. [4]
    int, long, float, str, bool, list, tuple, set, dict, complex


  6. Modula-2 and C have no built-in string type. What is a string in Modula-2 or C? Declare a string variable in either M2 or C. [4]
    In M2 and C, strings are just arrays of characters, terminated by a null. In M2:
    VAR
	m2Str : ARRAY [0..255] OF CHAR;
    In C:
    	char cStr[256];




  7. What is a namespace? Tell me everything you know about scope rules and namespaces in Python. [5]
    A namespace is a mapping (dictionary) from identifiers (names) to objects (values). There are three kinds of namespaces: the local namespace within a function/class/block, the global namespace for each module/file, and the default built-in namespace for all of Python. The scoping rules resolve names by moving outward from the local namespace, to any enclosing function/class definitions, to the global namespace for the file, to the default namespace.









  8. Consider the following Python expression:
    -2 + x * n ** 5 // (3 - y) > numApples % 2 and not 3 in range(0, 10, 2).
    1. Draw an expression tree for the expression. [4]













    2. What is the depth of your tree? [1]
      6
    3. Now rewrite the expression in postfix (Reverse Polish) notation: i.e., do a post-order traversal of the expression tree. (This will not be valid Python code.)[2]
      2, -, x, n, 5, **, *, 3, y, -, //, +, numApples, 2, %, >, 3, range(0, 10, 2), in, not, and



  9. Define or describe each of the following object-oriented terms: [7]
    1. Class: a user-defined container type
    2. Instance: an object; instances are to classes as variables are to types
    3. Attribute: a variable or method belonging to an object
    4. Method: a function/procedure belonging to an object
    5. Constructor/initializer: the special method which is called when an object is instantiated
    6. Interface: a set of messages that an object can receive
    7. Overloading: giving multiple definitions to a function/method/operator depending on the type of its parameters/operands




  10. Describe all the differences between Python lists and C arrays. [4]
    Python lists can change length (can insert/delete), can have items of differing type, can have items which change type (due to Python's dynamic typing), and have various operators/functions defined on them, such as del, len(), negative indexing, list slicing, etc.









  11. We wish to demonstrate the differences between alias, shallow copy, and deep copy. Come up with your own situation using records that might illustrate this. Define the record types in Python, create a sample record, then create an alias, a shallow copy, and a deep copy. [6]
    See separate Python code.





    1. Declare a Python class for a node of a doubly-linked list. [3] 
      class DoublyLinkedNode:
	def __init__(self, d=None, p=None, n=None):
		self.data = d
		self.prev = p
		self.next = n
      Optionally, also define a class for the list as a whole:
      class DoublyLinkedList:
	def __init__(self):
		self.head = None




    2. Using your class declaration above, create a doubly-linked list with three nodes. (You can put whatever you like in the data fields.) [3] 
      listLength = 3
myList = DoublyLinkedNode(0)
cursor = myList
for idx in range(1,listLength):
	cursor.next = DoublyLinkedNode(idx, cursor)
	cursor = cursor.next







    3. We wish to design a Python function to delete a node from a given doubly-linked list at a given position (index). List the parameters needed for such a function. What preconditions are there? What are the types of the parameters? What is the return type of the function? [4] 
      # This goes in the class definition for a DoublyLinkedList
def delete(self, pos):
	"""Insert a new entry into the current linked-list (self).
	pos: integer >= 0: 0 means insert at head of list.
	Does not return anything, but modifies current list (self)."""








    4. Now write a complete Python function to delete a node from a doubly-linked list. Docstring and preconditions are not required (that was the point of the last part of this question). Remember to clean up your "garbage". [5] 
      # This goes in the class definition for a DoublyLinkedList
def delete(self, pos):
	# Special case: delete head
	if pos == 0:
		trash = self.head
		self.head = self.head.next
		del trash
		return

	# Move cursor to just before the node to delete
	cursor = self.head
	for idx in range(pos-1):
		cursor = cursor.next

	# Skip over the deleted node and trash it
	trash = cursor.next
	cursor.next = cursor.next.next		# still ok even at the tail
	del trash









  13. Tell me everything you know about exceptions in Python. [4]
    Exceptions are a way of breaking out of the normal flow of execution in a Python program. Exceptions are raised/thrown by built-in and standard library functions when errors happen. Exceptions may also be raised programmatically via the raise command. A try keyword delimits a block wherein an exception is expected to be raised. If an exception is raised anywhere within that try block, control jumps to the corresponding except block (the exception handler). The except clause may catch all exceptions (discouraged), or it may specify which exceptions it will handle. Any unhandled exceptions will continue looking for a handler down the call stack. The programmer may also define custom exceptions by subclassing the built-in class Exception.









  14. Write a Python program to read in text from the file "input.txt", translate all characters to their numeric ASCII codes, separated by spaces, and write the result to the file "output.txt". Docstring, pseudocode are not required, but may be helpful for partial credit if your code isn't right. [6]










  15. One (very slow) way to calculate the value of pi is to compare the area of the unit quarter-circle with the area of the unit square. We can estimate this by generating random points in the unit square, and counting how many lie within the quarter-circle. The ratio should approximate pi/4 as the number of points increases.

    Write a function circle_pi(count, freq) that uses count points to estimate pi, printing out estimates every freq iterations (to show its progress). You may use the random standard Python library. (Hint: Pythagoras' theorem states that for any right triangle with legs a and b and hypotenuse c, a**2 + b**2 = c**2.) [6]

    Write a testbed program that calls your function, but saves the printed output to a file instead of printing to the screen. [2]

    Docstrings are required for your program and your function; comments are not required but may be helpful for partial credit if your code isn't perfect.
    See separate Python code.