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

Unless otherwise specified, all questions pertain to Python.
Total points: 120
  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: [21]
    1. "Computers are tools__________, and computing scientists are toolsmiths________________."
    2. The Python keyword used to introduce a new function definition is def__________
    3. Evaluate: 23 << 2: 92__________
    4. Convert 0x127 to decimal: 295_________
    5. Convert 1011 0101 from binary to octal: 0265_________
    6. What word describes functions which invoke themselves? recursion
    7. The assignment operator (=) with mutable objects like lists creates a alias___________
    8. What is the type of the Python expression 'x' + 2*'y' ? str________
    9. What special method name does Python use for the constructor/initializer method? __init__()____________
    10. Name the two Python program control constructs we learned which correspond to repetition: while, for________ __________
    11. 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.
    12. A DSL connection runs at 2Mb/s. Assuming full utilization of the bandwidth (which never happens in reality), how many gigabytes can be transferred in 2 hours? Use binary units. 1800 MB = 1800/1024 GB (= 225/128 GB)___________
    13. The Python operator which tests for membership in a list is in________
    14. The Python method on file objects that moves the file position pointer is called seek()__________
    15. What English part of speech should a function name be? verb___________
    16. What symbol is used to indicate logical negation in Python? not___________
    17. The Python command used to skip to the next iteration of a loop prematurely is continue______________
    18. 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________________
  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 = "Bartlett"
	from math import pi
    1. 'pi' + 2*'z' + 'a' 'pizza'
    2. 2 + 1>4 and (5/0 < 1) False
    3. 14 / 4 - 4.0 -1.0
    4. 9 | 3 11
    5. 9 % 3 0
    6. "%03d%s" % (15.189, 'pears') '015pears'
    7. string.upper(Bosc) NameError: Bosc
    8. "%07.3f" % 3.1415926535 '003.142'
    9. range(myPear) TypeError
    10. myPear[1:2] 'a'
    11. 'b' + 'e' 'be'
    12. ord('b') - ord('e') -3
    13. 'b' - 'e' TypeError
    14. 'b' + 3+'e' TypeError

  5. 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.









  6. 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
  7. 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];




  8. Tell me everything you know about Python dictionaries. [4]
    A dictionary is a mapping from keys to values. The keys may be anything of immutable type (numbers, strings, tuples of immutable things, etc.); the values may be Python object (including instances of user-defined classes). Dictionaries are indexed by key in square brackets, much like lists are. Some commonly used operations on dictionaries include len(), in (test for membership), .keys() (list all the keys), .values() (list all the values), etc.











  9. 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.









  10. Write a Python program to read in text from the file "input.txt", translate all letters to uppercase, and print out the result to the screen. Docstring is required; pseudocode is not. [6]
    Many ways to solve this. One simple solution:
    myFile = open('input.txt')
fullText = myFile.read()	# read whole file in!
print fullText.upper()







  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] 
    class Date:
	def __init__(self, y=2000, m=1, d=1):
		self.year = y
		self.month = m
		self.day = d
class Student:
  	def __init__(self, n='', bd=Date()):
		self.name = n
		self.birthdate = bd

s1 = Student('Bob', Date(1987, 1, 1))

# alias: s3 is an alias for Bob
s3 = s1

# shallow copy: a twin of Bob, shared birthdate
import copy
s4 = copy.copy(s1)
# or:
s4 = Student()
s4.name = s1.name
s4.birthdate = s1.birthdate

# deep copy: a separate copy of Bob
s5 = copy.deepcopy(s1)
# or:
s5 = Student()
s5.name = s1.name
s5.birthdate.year  = s1.birthdate.year
s5.birthdate.month = s1.birthdate.month
s5.birthdate.day   = s1.birthdate.day






    1. Declare a Python class for a node of a doubly-linked list. [4] 
      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.) [4] 
      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 insert a node into a given doubly-linked list at a given position. 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 insert(self, pos, data):
	"""Insert a new entry into the current linked-list (self).
	pos: integer >= 0: 0 means insert at head of list.
	data: payload to put in new node.
	Does not return anything, but modifies current list (self)."""








    4. Now write a complete Python function to insert into a doubly-linked list. Docstring and preconditions are not required (that was the point of the last part of this question). [6] 
      # This goes in the class definition for a DoublyLinkedList
def insert(self, pos, data):
	# Special case: insert at head
	if pos == 0:
		newNode = DoublyLinkedNode(data, None, self.head)
		self.head = newNode
		return

	# Move cursor to just before where we'll insert
	cursor = self.head
	for idx in range(pos-1):
		cursor = cursor.next

	# Thread in a new node
	newNode = DoublyLinkedNode(data, cursor, cursor.next)
	cursor.next = newNode









  13. Design a definition (header) file for a pseudorandom number generator library. You may use a formal language like Python or C, or you may use pseudocode. Include (in docstrings or comments) preconditions for each function. [6]
  14. Write a complete pseudorandom number generator library in Python. Also include a testbed program using your library (need not be interactive). You need not worry about producing truly random numbers, but please make a reasonable effort to make them hard to predict. Docstrings and pseudocode are not required, but may be good for partial credit. [10]
    For these problems, see the file pseudorandom.py