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.
(8 points) Some questions about numbers.
(8 points) Sections 11.6.1 through 11.6.3 of your textbook include a discussion of an important Python structure called a dictionary. Your job for this problem is to read about dictionaries, and then write a Python program that does the following:
This program is very similar to the one described in section 11.6.3, so you should use that section as a starting point for your program. Note that the program I am asking you to write should be simpler than the one in 11.6.3, since reading a single character from a file is easier than reading a single word.
Hand in a copy of your program on paper, but also hand it in electronically in the usual way. Please call it dictionary.py.
(6 points) Consider the following recursive function.
def doSomething(s):
''' Expects s to be a string. '''
if len(s) == 0:
return ''
t = doSomething(s[1:]) + s[0]
return t
(8 points) I have a list of integers, and I want to know the distance between the two integers that are furthest apart. For example, if the list is [3, 5, -1, 8, 10, 6], then the distance I'm looking for is 11 (i.e. the distance between 10 and -1). Elmo suggests the following code, which does the job:
def elmo(theList):
N = len(theList)
biggestDistance = 0
for k in range(N):
for j in range(N):
if theList[j] - theList[k] > biggestDistance:
biggestDistance = theList[j] - theList[k]
return biggestDistance
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 |