Online 1.

_______/18 ANSWERS
Athena User Name
Online 2. _______/10
Online 3. _______/16
ANSWERS________________________
Online 4. _______/10 Full Name
Online 5. _______/22
Online 6. _______/24
Recitation hour

Total ______ /100

The final exam for 6.0001 is on MITx. Do not write your answers on this paper. Only fill out
this front page with your name, username, and recitation.

You are allowed 2 pages (4 sides total) on which you can write anything. On your computer, you
are only allowed to have the MITx website open and Anaconda/IDLE. Close everything except
for these. If the test proctors see that you have anything else open on the computer or if we
believe you are trying to cheat, you will be asked to leave immediately and given a zero on
the exam.

You have 120 minutes to complete the exam.

You must check out with an exam proctor after you have finished your exam but before you
leave. Hand in this paper cover sheet when you checkout. Any student who does not do this
will receive a 0 on the exam.
Problem 1

1. What data type is the object myst: myst = ( { 1: [1,1], 2: [2,2]}, { 'a': ['a',1], 'b': ['b',2] } )
  tuple
 list
 dictionary
 None of the above
2. Which of the following is correct?
 A superclass inherits attributes of its subclass.
  A subclass inherits attributes of its superclass.
 A subclass cannot override a superclass' attributes.
 A subclass will first look for (and use) a method in its superclass before doing so in its own class.
3. Suppose you have a class called At. There exists a special method defined in the class with two underbars
called __lt__ that tests whether one instance of the class, a, is less than another instance of the class, b.
Which is true?
 a < b is syntactically correct
 a.__lt__(b) is syntactically correct
  Both of the above
 None of the above
4. The function 8000*n*log(n)+1000*log(n)+40*n300+2n is
  O(2n)
 O(n*log(n))
 O(n300)
 O(log(n))
5. Consider the function f below. What is its big oh complexity?
def f(n):
def g(m):
m=0
for i in range(m):
print m
for i in range(n):
g(n)
 O(1)
 O(log(n))
  O(n)
 O(n2)
6. Consider the code:
L = [1,2,3]
d = {'a': 'b'}
def f(x):
return 3
Which of the following does NOT cause an exception to be thrown?
 print L[3]
 print d['b']
  for i in range(1000000001, -1, -2):
print f
 print int('abc')
 None of the above
7. Which of the following is true?
 Testing a program and debugging a program are the same thing.
  Testing compares program output to the expected output. Debugging is a process to study the
events leading up to an error.
 Testing checks that there is no input on which the program crashes.
 Testing is typically done by putting try-except blocks around pieces of code.
 8. Assume n = len(X). Which of the following is accurate?
 If X is a sorted tuple, binary search on X will be O(log(n)).
 If X is an unsorted list, binary search on X might return the wrong answer.
  Both of the above
 None of the above

9. Consider a list of length n. Assume you want to search that list for k different elements. What is the
smallest value of k for which the asymptotic running time of sorting the list before doing the k searches and
then doing the searches would be no larger than the asymptotic running time of doing the k searches on the
original list. Assume that the fastest known algorithms are used for sorting and searching in each case.
 k=1
  k = log(n)
 k=n
 k = n2

Problem 2

Answer the following questions by typing in the textbox below. Keep your answers to one sentence. Consider the
following code:

def hashString(s, size):

# assume sorted runs in time O(len(s)*log(len(s))
s = sorted(s)
intVal = ''
for c in s:
#assume ord is a constant time function that returns an int between 0 and 99
intVal = intVal + str(ord(c))
#assume int runs in time log(len(intVal))
return int(intVal)%size

What is the asymptotic complexity of hashString?

O(n log n) where n is len(s)

Ignoring complexity and coding style, why is hashString a bad hash function?

It sorts s beforehand, which leads to many more colisions.

Problem 3

In this problem, you will implement a class according to the specifications in the template file usresident.py. The file
contains a Person class similar to what you have seen in lecture and a USResident class (a subclass of Person).
Person is already implemented for you and you will have to implement two methods of USResident.

For example, the following code:

a = USResident('Tim Beaver', 'citizen')
print a.getStatus()
b = USResident('Tim Horton', 'non-resident')
will print out:
citizen
## will show that a ValueError was raised at a particular line

class USResident(Person):
""" A Person who resides in the US. """
def __init__(self, name, status):
"""
Initializes a Person object. A USResident object inherits
from Person and has one additional attribute:
status: a string, one of "citizen", "legal_resident", "illegal resident"
Raises a ValueError if status is not one of those 3 strings
"""
Person.__init__(self, name)
if status != "citizen" and status != "legal_resident" and status != "illegal_resident":
raise ValueError
self.status = status
def getStatus(self):
"""
Returns the status
"""
return self.status

Problem 4

You are given the following buggy implementation of the selection sort algorithm:

def buggysort(L):
for i in range(len(L)):
min_i = i
min_val = L[i]
for j in range(len(L)):
if L[j] > min_val:
min_i = j
min_val = L[j]
L[i], L[min_i] = min_val, L[i]
return L

Your goal is to debug this program such that it sorts the input list in ascending order. You must fix this code by
changing exactly 2 lines. The total number of lines of the program should not change. You will not be given points
for implementing a sorting algorithm that does not follow the procedure that this algorithm is attempting to
implement.

def buggysort(L):
for i in range(len(L)):
min_i = i
min_val = L[i]
for j in range(i+1, len(L)):
if L[j] < min_val:
min_i = j
min_val = L[j]
L[i], L[min_i] = min_val, L[i]
return L
Problem 5

You are given a dictionary aDict that maps integer keys to integer values. Write a Python function that returns a list
of keys in aDict that map to dictionary values that appear exactly once in aDict.

This function takes in a dictionary and returns a list.

Return the list of keys in increasing order.
If aDict does not contain any values appearing exactly once, return an empty list.
If aDict is empty, return an empty list.
Hint: You may want to create another dictionary as an intermediate data structure.

For example:
If aDict = {1: 1, 3: 2, 6: 0, 7: 0, 8: 4, 10: 0} then your function should return [1, 3, 8]
If aDict = {1: 1, 2: 1, 3: 1} then your function should return []

def uniqueValues(aDict):
'''
aDict: a dictionary
returns: a sorted list of keys that map to unique aDict values, empty list if none
'''
counts = {}
unique = []
for i in aDict.values():
counts[i] = 0
for i in aDict.keys():
counts[aDict[i]] += 1
for i in aDict.keys():
if counts[aDict[i]] == 1:
unique.append(i)
unique.sort()
return unique

Grader Test Cases:

aDict = {3: 4, 0: 4, 9: 4, 5: 2, 1: 1}
aDict = {10: 10, 2: 1}
aDict = {}
aDict = {1: 1}
aDict = {1: 1, 2: 2}
aDict = {5: 8, 3: 4}
aDict = {1: 1, 2: 1}
aDict = {5: 1, 7: 1}
aDict = {2: 0, 3: 3, 6: 1}
aDict = {8: 3, 1: 3, 2: 2}
aDict = {8: 1, 0: 4, 9: 4, 5: 2, 10: 1}
aDict = {-2: -2, -1: -1, -9: -9, -3: -3, -4: -4}
aDict = {-2: -1, -1: -1, -9: -9, -3: -9, -4: -4}
aDict = {8: 1, 0: -4, -9: 4, -5: 2, 1: -1}
aDict = {4: -4, 3: -3, 2: -2}
aDict = {1: 1, 2: 1, 3: 3}
aDict = {1: 1, 3: 2, 6: 0, 7: 0, 8: 4, 10: 0}
aDict = {0: 0, 1: 1, 2: 7, 3: 3, 5: 2, 6: 5, 7: 8, 9: 10, 10: 0}
aDict = {2: 2, 5: 0, 7: 2}
aDict = {0: 3, 1: 2, 2: 3, 3: 1, 4: 0, 6: 0, 7: 4, 8: 2, 9: 7, 10: 0}
aDict = {0: 2, 1: 3, 2: 0, 3: 6, 7: 2, 9: 3}
aDict = {8: 1, 0: 4, 9: 4, 5: 2, 1: 1}
Problem 6

Write a Python function called satisfiesF that has the specification below. Then make the function call
run_satisfiesF(L, satisfiesF). For testing of satisfiesF, for example, the following test function f and test code:
def f(s):
return 'a' in s
L = ['a', 'b', 'a']
print satisfiesF(L)
print L
Should print:
2
['a', 'a']

def satisfiesF(L):
"""
Assumes L is a list of strings
Assume function f is already defined for you and it maps a string to a Boolean
Mutates L such that it contains all of the strings, s, originally in L such
that f(s) returns True, and no other elements
Does not return anything
"""
for i in range(len(L) - 1, -1, -1):
if not f(L[i]):
L.pop(i)
return len(L)

run_satisfiesF(L, satisfiesF)

Grader Test Cases:

def f(s): def f(s):

return True return 'mit' in s
L = ['a', 'b', 'a'] L = ['a', 'mit', 'tim', 'mitsy']

def f(s): def f(s):

return False return 'b' in s
L = ['a', 'b', 'a'] L = ['b', 'b', 'b']

def f(s): def f(s):

return 'a' in s return 'b' in s
L = ['a', 'b', 'a'] L = ['a', 'a', 'a']

def f(s): def f(s):

return 'a' in s return len(s) == 3
L = ['abc', 'bcd', 'def', 'gha'] L = ['12', '123', '1234']

def f(s): def f(s):

return 'd' in s return len(s) == 0
L = ['abc', 'bcd', 'def', 'gha'] L = ['', 'b', '']

def f(s): def f(s):

return 'mit' in s return s[0] == 'z'
L = ['a', 'mit', 'tim'] L = ['z', 'zzz', 'adze']