This is an exam. You may not speak with anybody other than Jeff Ondich about its contents. You may, however, use your book, your notes, the books in the library, the Internet, and divine guidance (should any be offered to you). If you obtain information from some source other than your own brain, cite your source and use quotation marks where appropriate.
Hand your exam in on paper.
(6 points) This recursive function prints out the elements of a list in order. For example, if you call "printList([4, 8, 15, 16, 23, 42])", you'll see those 6 numbers printed in that order.
def printList(theList):
if len(theList) > 0:
print theList[0]
printList(theList[1:])
Show how to modify printList to print the list out in reverse order. Keep the function recursive, and do not use any loops.
You may find it handy to recall that theList[-1] refers to the last item in a list.
(6 points) In the "functions" assignment, you wrote a function to determine whether a given string was a palindrome. In this problem, you will write another version if isPalindrome, but this time, you'll do it recursively. Note that for the purposes of this problem, spaces, punctuation, and capitalization will matter. For example, "rats live on no evil star" and "redivider" are palindromes, but "Madam, I'm Adam" and "Otto" are not palindromes. This will make your code considerably easier to write than it would be otherwise.
To write the recursive version of isPalindrome, use the following strategy.
Base case: If the string contains one or zero characters, it is automatically a palindrome.
General case: Otherwise, a string is a palindrome if and only if (1) its first and last characters are identical, and (2) the substring consisting of everything except the first and last characters is a palindrome.
Note that (2) in the general case can be viewed as a recursive function call. Your resulting code will look something like this (with pseudo-code in [brackets]):
def isPalindrome(s):
'''
Returns True if s is a (strict) palindrome, and False otherwise.
'''
if [base case applies]:
return True
if [first and last chars match] and [substring with first and last chars removed is a palindrome]:
return True
return False
(8 points) I have a list of integers, and I want to know the distance between the pair of these numbers that are furthest apart. Elmo suggests the following code, which does the job:
def elmo(theList):
N = len(theList)
maxDistance = 0
for k in range(N):
for j in range(N):
if theList[j] - theList[k] > maxDistance:
maxDistance = theList[j] - theList[k]
return maxDistance
As we discussed in class, selection sort, insertion sort, and mergesort are all members of a class of sorting algorithms whose performance is usually measured by counting the number of list element comparisons that need to be done to complete the sorting of the list. That is, we count the number of times something like "a[j] < a[k]" gets executed during the run of the algorithm. It would take several pages to provide a reasonably rigorous argument that the comparison count is a good measure of performance for these algorithms. With a lot less rigor, we can say something like this: by counting comparisons, we are counting the number of iterations of the inner loop, and by counting inner loop iterations, we are counting the most time-consuming portion of the algorithm.
To see how this plays out, try running "python sorter.py bubble 10 verbose" or "python sorter.py bubble 1000" to see a report of the sorting times and number of comparisons for a 10-element list or a 1000-element list. (The "verbose" causes the program to print out the list before and after sorting, to help you believe that sorting is actually taking place.) To try this with the other algorithms, replace "bubble" with "merge", "selection", or "insertion".
In what follows, you're going to count comparisons and measure running times for the three algorithms and several values of N. Let's get started.
Fill in the following chart.
| N | Comp. count for Sel. Sort | Running time for Sel. Sort | Comp. count for Ins. Sort | Running time for Ins. Sort | Comp. count for Merge Sort | Running time for Merge Sort |
|---|---|---|---|---|---|---|
| 5000 | ||||||
| 10000 | ||||||
| 15000 | ||||||
| 20000 |
As part of your final project, please hand in a separate sheet of paper with the following information. If you're working with a partner, you only need to hand in one copy of this sheet. This item is not part of the exam, so you may work with your partner on it.