CMPT140 Fall 2008 Final Exam (part 1), Trinity Western

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

___________

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

___________

Show the contents of appleNames, myApples, and yourApples after the following Python code is executed: [4]

	appleNames = [ "Fuji", "Gala", "Empire", "Jonagold" ]
	myApples = appleNames
	yourApples = appleNames[1:3]
	myApples[2] = "Rome"

appleNames: [ "Fuji", "Gala", "Rome", "Jonagold" ] myApples: [ "Fuji", "Gala", "Rome", "Jonagold" ] yourApples: [ "Gala", "Empire" ]

Recall that in Python int/float/bool parameters are essentially passed by value, and lists/dictionary parameters are essentially passed by reference. What is printed by the following block of Python code? [4]

	def double_me(x):
		x *= 2
	y = 3
	z = range(3)
	double_me(y)
	double_me(z)
	print 'y =', y, ', z =', z

y = 3, z = [0, 1, 2, 0, 1, 2]
The variable y points to an immutable object (the float 3.0) and is roughly pass-by-value, so it is not affected by double_me(). The variable z points to a mutable object (the list range(3)) and is roughly pass-by-reference, so it is changed by double_me(). The real scoop on Python parameter passing is call-by-object and is a bit more complicated; it has to do with Python's object-oriented roots.

Describe at least four kinds of documentation (internal or external) that you should have in your Python programs. [4]
Comments, docstrings, online help, good identifiers, user manual, programmer's diary, etc....

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. [11]

2%2**2+2*2 6
2 + 3>4 and 2 == 14.0//4.0 False
'pi' + 2*'z' + 'a' 'pizza'
not False or (12 % 0) True
range(len(range(-1, 2))) [ 0, 1, 2 ]
len(range(1, 5)) = len(range(4)) SyntaxError (assignment)
3*range(2) [ 0, 1, 0, 1, 0, 1 ]
chr(ord('p') - 3) 'm'
"%s%04d.jpg" % ('img-', 99.9) 'img-0099.jpg'
'%05.1f' % (17.0 / 4) '004.2' (or '004.3' is also okay)
0 in range(3) True

What is output by the following block of Python code? [3]

myList = [ "Hi there", ("hi", "there"), range(10, 40, 5), [ range(5) * 2 ] ]
for item in myList:
	print len(item),

'8 2 6 1 '

Compare and contrast Python lists with C/M2 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.

Evaluate the following Python block: [3]

	x = 10
	while x > 0:
		if x%2 == 0:
			continue
		print x,
		x -= 1
	else:
		print "Blastoff!"

The loop doesn't finish! Nothing is printed, and the loop spins forever. The first 'if' is true, and x doesn't get decremented, so it keeps 'continue'-ing forever. (To fix it, consider moving the if statement to the end of the loop, after the decrement.)

Tell me everything you know about software pseudo-random number generators. [4]

A software RNG is a function that yields a new random number every time it is called. Usually, no parameters are required, and the function returns a float in the range [0,1). A software RNG works by taking the output of the last invocation of the function, performing a bunch of math to "randomize", and returning a new number in the appropriate range. As a result, it needs to keep track of the last generated value. The software RNG can be "seeded" with a user-supplied value; given the same seed, the RNG will always yield the same sequence of "random" numbers.

Describe and contrast a header (DEF) file with an implementation (IMP) file. [3]

Header: public interface, doesn't define bodies of functions, like a car's owner/user manual.
Implementation: contains bodies of the functions; like a car's shop manual.

Consider a Caesar substitution cipher on a reduced alphabet of just the letters A through J (ten letters). Using the key 'FCHDAJIEBG', encode the cleartext string "Jeff cached a big bag" [3]
"GAJJ HFHEAD F CBI CFI"

Using the same key and alphabet as the previous question, construct the decode key: [3]
"EIBDHAJCGF"

Write and document a simple Python function that returns a factorial (n!). The input should come from a parameter (not keyboard input), and the output should be via return value (not console output). Include docstring and pre/post conditions. [4]
def factorial(n): """Return n-factorial, n! pre: n must be a positive integer. post: returns a positive integer, n! """ if n <= 1: return 1 return n * factorial(n-1)

Name:	_______________________________ K E Y
Student ID:	_______________________________