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) 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.
(6 points) For this problem, you will write a recursive function to count the number of vowels in a given string (for our purposes, "y" is not a vowel). I would like your code to use the following strategy:
Base case: If the string is empty, it contains zero vowels.
General case: First, compute the number of vowels in the string not counting the first character in the string. Then, add either one or zero to the vowel count, depending on whether the first character in the string is a vowel.
def getVowelCount(s): ''' Returns the number of vowels in the string s. ''' if [base case applies]: return 0 [compute the number of vowels in the last len(s)-1 characters in s] if [the first character in the string is a vowel]: [add 1 to the vowel count] return [the vowel count]
(8 points) I have a list of integers, and I want to know whether any of them are identical. Elmo suggests the following code, which does the job:
def elmo(theList): N = len(theList) foundAMatch = False for k in range(N): for j in range(N): if j != k and theList[j] == theList[k]: foundAMatch = True return foundAMatch
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 |