CS 1MD3 - Winter 2006 - Assignment #2
Generated for Student ID: 0553483
Due Date: Wednesday, February 8th
(You are responsible for verifying that your student number is correct!)
Part 1: Debugging
The following four functions are infested with bugs. Correct them by adding or changing a single
line in each one. Clearly indicate your changes with comments. If you add a line, append the
comment, "# added." If you change a line, append a comment to it containing the original, erroneous line.
Solutions submitted without comments will not be marked.
1
def argMin(aList):
"""Returns the index of the smallest element in the list"""
n = len(aList)
if n <= 0:
return None
i = 1
theArgMin = i
theMin = aList[theArgMin]
while i < n:
x = aList[i]
if x < theMin:
theMin = x
theArgMin = i
i = i + 1
return theArgMin
2
def hammingDistance(str1, str2):
"""Returns the Hamming distance (or "edit distance") between two strings of the
same length. Hamming distance is defined as the minimum number of characters which
must be changed to make the strings identical. For example, the Hamming distance
between "Python" and "Athlon" is 4 (only the last two letters are the same);
the Hamming distance between "noodle" and "needle" is 2 (only the second and
third letters differ)."""
if len(str1) != len(str2):
return None
list1 = list(str1)
list2 = list(str2)
n=len(list1)
distance = 0
i=0
while i < n:
if list1[i] != list2[i]:
distance = distance + 1
return distance
3
def deinterlaceEven(interlacedList):
"""Returns a list consisting of only the even elements of the given list.
For example, deinterlaceEven(['1', 'a', '2', 'b', '3', 'c']) returns [1,2,3]."""
n = len(interlacedList)
if n == 0:
return None
i = 0
evenList = []
while i < n:
evenList.append(interlacedList[i])
i = i+2
return evenList
4
def product(numberList):
"""Computes the product of all the list elements."""
n = len(numberList)
if n <= 0:
return None
theProduct = 1
i=0
while i < n:
theProdcut = theProduct * numberList[i]
i=i+1
return theProduct
Part 2: Testing
Create automated tests for the following function using PyUnit. Your tests should ensure that the code produces the expected result in all cases.
def median(aList):
"""Returns the median of the given list, which is defined as the element which is no greater
than half the elements, and no less than half the elements. If the list contains an even
number of elements, the median is traditionally the mean of the two such bisectors."""
n = len(aList)
if n == 0:
return None
if n == 1:
return aList[0]
# Make a deep copy of the list so as not to destroy it
listCopy = []
for x in aList:
listCopy.append(x)
# Do a (slow but simple) selection sort to put the elements in order
for i in range(0,n-1):
nextElmt = min(listCopy[i:n])
j = i
while listCopy[j] != nextElmt:
j = j+1
tmp = listCopy[i]
listCopy[i] = listCopy[j]
listCopy[j] = tmp
# If there are an even number of elements, the median is the mean of the middle two
print listCopy
if 2*(n/2) == n:
return (listCopy[n/2 - 1] + listCopy[n/2]) / float(2)
else:
return listCopy[n/2]