CS 111

Fall 2016

Introduction to Computer Science

Final Exam

Due: Monday, 2016-11-14 at 13:50.

This is an exam. You may not speak with human beings other than Jed Yang about its contents. You may, however, use non-human resources: your book, your notes, the books in the library, and the Internet (but not to consult humans such as via email, chat, or forums). 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.

  1. (8 points) Section 11.6 of your textbook includes 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:

    • Opens the file colleges.txt, which consists of lines of the form "College, City, State". (These are the best liberal arts colleges as ranked by US News a few years ago, but your program will work with any similarly formatted file.)
    • Reads the file one line at a time, keeping track of how many times each state name appears in the file. (This part uses a dictionary.)
    • Closes the file.
    • Prints the state names and counts in descending order of the number of times they appeared in the file. That is, the state with the largest number of best liberal arts colleges will appear at the top of the list, while the one with the fewest will appear at the bottom (and some, such as the corporate haven Delaware, will not appear at all).

    Hand in a copy of your program on paper, but also hand it in electronically in the usual way. Please call it dictionary.py.

  2. (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). Rory suggests the following code, which does the job:

    def rory(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
    • When I used Rory's code on a list of 10000 integers on my laptop, it took 20.7, 21.1, and 20.8 seconds the three times I tried it. Approximately how long will Rory's code take to run if I use a list of 25000 integers (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.)
    • Paris says she thinks Rory's code is silly. Describe an algorithm that will run significantly faster than Rory's, and explain why it is faster.

  3. (2 points) I am teaching this course again next quarter, and I want to do better. Please give me one (short) piece of advice. There are no wrong answers, except blank ones. (Note: you will have an opportunity to evaluate my performance anonymously at the end of term as well.)

  4. (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 behaviours of iterative and recursive Insertion Sorts, with further comparison to Merge Sort.

    As we discussed in class, Selection Sort, 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 python3 sorter.py insertion 10 verbose or python3 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 Comparison count for Insertion Sort Running time for Insertion Sort Comparison count for Merge Sort Running time for Merge Sort
      5000
      10000
      15000
      20000

    • Can you use the comparison counts to predict the running times? If so, how? If not, why not?
    • When we analyzed Insertion Sort in class, we concluded that its running time is approximately proportional to N^2. Do the numbers in your chart support this conclusion?
    • What happens if you try to fill in a column of this chart for Recursive Insertion Sort? Explain why this problem occurs for Recursive Insertion Sort but not Merge Sort, even though they are both recursive algorithms.

  5. (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 teddy-with-message.png is my usual photograph of a cute teddy bear, with a slight modification. The blue values of the pixels in the bottom row 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 blue value represents a 0 bit, and an odd blue value represents a 1 bit. For example, if the left 8 pixels in the bottom 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).

    Your job is to write a program to extract the hidden message from the modified teddy photograph. Write the message on your test paper, and submit your program electronically as usual. Please call the program stegano.py.