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 available 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) Chapter 8 of your textbook, which I asked you to read prematurely several weeks ago, concerns 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:
Hand in a copy of your program on paper, but also hand it in electronically in the usual way. Please call it dictionary.py.
(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, -2, 8, 10, 6], then the distance I'm looking for is 12 (i.e. the distance between 10 and -2). 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
(8 points) In class, we have studied an iterative version of Insertion Sort--that is, a version that uses loops. But Insertion Sort can also be implemented recursively. In this problem, you will use sorter.py to help investigate the different behaviors of iterative and recursive Insertion Sorts, with further comparison to Merge Sort.
As we discussed in class, Insertion Sort and Merge Sort are 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. When we count 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 insertion 10 verbose" or "python sorter.py merge 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.)
In what follows, you're going to count comparisons and measure running times for the two algorithms and several values of N.
Fill in the following chart.
| N | Comp. count for Ins. Sort | Running time for Ins. Sort | Comp. count for Merge Sort | Running time for Merge Sort |
|---|---|---|---|---|
| 3000 | ||||
| 6000 | ||||
| 9000 | ||||
| 12000 |
(8 points) Steganography is the art of hiding messages in places where people will be unaware there is a message at all, let alone an encoded message. In this exercise, you will work with a form of steganography that involves hiding messages in digital images.
The image ox-with-message.png is my usual Babe the Blue Ox photograph, with a slight modification. The green values of the pixels in the rightmost column have been altered to hold a message consisting of a sequence of 8-bit ASCII characters. Each character is represented by 8 pixels, where an even green value represents a 0 bit, and an odd green value represents a 1 bit. For example, if the top 8 pixels in the right column of the photograph have green values equal to 50, 51, 48, 48, 50, 52, 52, 51 (i.e. even, odd, even, even, even, even, even, odd), then the first character in the hidden message is the character whose binary ASCII representation is 01000001 (that is, the capital letter A).
Your job is to write a program to extract the hidden message from the modified ox photograph. Write the message on your test paper, and submit your program as usual. Please call the program problem5.py.
