Next time: problem 3 generates muddy responses. Figure out a better
way to get them to engage with recurrence-plus-base-case.
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 made 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 in your exam via Moodle as a PDF file named exam2.pdf.
For problem 6, submit your code as problem6.py. For problems 1 and 4, just
include your code in the PDF within your answer to the problem.
- (10 points) Section 11.7 of your textbook 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:
- Opens the file names.txt, which consists of
lines of the form "Last name,First name,Middlename", where
the middle name is usually but not always the empty string. (These names happen
to be the names of female computer scientists taken from
a Wikipedia page on that topic,
though your program will work with any similarly formatted file of names.
I didn't make an effort to figure out who had two-word last names and who had middle names, but
since first names are mostly unambiguous, that shouldn't matter.)
- Reads the file one line at a time, keeping track of how many times each
first name appears in the file. (This part uses a dictionary.)
- Closes the file.
- Prints the first names in descending order of the number of times they
appeared in the file.
- (10 points) I have a list of names, and I want to know
how many of my names are singletons (i.e. strings that appear exactly
once in my list). For example, if the list is ['Alice', 'Bob', 'Carla', 'Bob', 'Alice', 'Desmond'],
there are 2 singletons ('Carla' and 'Desmond').
Elmo suggests the following code, which does the job:
def elmo_count_singletons(the_list):
N = len(the_list)
number_of_singletons = 0
for k in range(N):
item_to_look_for = the_list[k]
found_match = False
for j in range(N):
if j != k and the_list[j] == item_to_look_for:
found_match = True
if not found_match:
number_of_singletons += 1
return number_of_singletons
Note that I don't care which names are singletons—just how many of them there are.
- When I used Elmo's code on an array of 10000 integers on my
laptop, it took 7.8 seconds (I tried it several
times—7.8 seconds every time). Approximately how long will Elmo's
code take to run if N is 25000 (assuming I use the same computer)?
Justify your answer. (It is not sufficient to tell me that you ran
the code yourself and it took a certain amount of time. I want you
to explain why it will take as long as you say it will.)
- Zoe says she thinks Elmo's code is silly. Describe an
algorithm that will run significantly faster than Elmo's, and
explain why it's faster. (You do not need to implement your algorithm,
but you do need to describe it clearly.)
(7 points) Recursion, part 1
Consider the following function.
def mystery(list_of_integers):
if len(list_of_integers) == 0:
result = 0
elif len(list_of_integers) == 1:
result = list_of_integers[0]
else:
middleIndex = len(list_of_integers) // 2
result = mystery(list_of_integers[:middleIndex]) + mystery(list_of_integers[middleIndex:])
return result
- What is the meaning, numerically speaking, of the return value of this function if you
pass it a list of integers?
- Recursive algorithms work by breaking a big problem down into one or more smaller
problems of the very same type. For example, the Sierpinski triangle program draws the
n-level diagram by first drawing the middle triangle, and then drawing three (n-1)-level
diagrams around it. In the case of the mystery function here, describe the function's
strategy: what is the big problem it's trying to solve, and what is/are the smaller
problem(s) it uses to solve the bigger problem?
(6 points) Recursion, part 2
For this problem, you will write a recursive function called
sum_of_digits that accepts an int parameter and returns the sum of its base ten digits. For
example, sum_of_digits(357) would return 15, since 3 + 5 + 7 = 15.
- In what way does/will your function break the sum_of_digits problem down into one or more smaller
problems of the same type?
- What is your base case?
- Show your code.
For simplicity, you may assume that sum_of_digits's parameter is never negative. Hand in
a print-out of your function.
- (3 points) I'm going to need to take a break for a few days after the term. To help enhance my
experience, please recommend something for me to watch (TV, movie, YouTube,...) or listen to
(musical or otherwise). Thanks! (If you remind me in class, I'm happy to offer
some recommendations for you, too.)
(11 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 maisie-with-message.png is my usual
photograph of my dog Maisie, with a slight modification. The blue values of
the pixels in the top row or rows of this picture have been altered to store
a sequence of 8-bit ASCII characters. Each character is represented by
8 pixels, where an even blue value represents a 0 bit, and an odd blue value represents
a 1 bit. For example, if the leftmost 8 pixels in the top row of the photograph
have blue 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).
If the message is too long to fit in the top row of the image, it continues
into the second row (again, moving left to right), then the third, etc. until
you encounter a null character—that is, a character whose ASCII representation
in binary is 00000000.
Your job is to write a program to extract the hidden message from the modified
Maisie photograph. Include the message in your exam2.pdf, and submit your program
as problem6.py.
Note, by the way, that this form of steganography doesn't work with jpg files
using PIL, but it does work with png files, which is why the picture in question
is in png form.
