Final Examination

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

This examination has a required prologue that must be completed by Monday afternoon. The prologue is intended to help you think about the examination.

There are five problems on this examination. You must do your best to answer all of them. The problems are not necessarily of equal difficulty. Problems may include subproblems. If you complete five problems correctly or mostly correctly, you will earn an A. If you complete four problems correctly or mostly correctly, you will earn a B. If you complete three problems correctly or mostly correctly, you will earn a C. If you complete two problems correctly or mostly correctly, you will earn a D. If you complete fewer than two problems correctly or mostly correctly, you will earn an F. If you do not attempt the examination, you will earn a 0. Partially correct solutions may or may not earn you a partial grade, depending on the discretion of the grader.

Read the entire examination before you begin.

I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about ten hours, depending on how well you've learned the topics and how fast you work.

This examination is open book, open notes, open mind, open computer, and open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. (You certainly should not post them to GitHub.) And, in case it's not clear, you may not ask others (in person, via email, via IM, via IRC, by posting a “please help” message or question on StackOverflow or on any other site, or in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, and because some students will choose to take a makeup examination that involves redoing the problems, you are not permitted to discuss the exam with anyone until after I have indicated that it is acceptable to do so. If you must say something about the exam, you are allowed to say “This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must turn in a sheet that includes both of the following statements.

Please sign and date each statement separately. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

You need only present your exam to me electronically. You should create the electronic version by making a tarball of any relevant code and emailing me the tarball. If you don't know how to make a tarball, let me know. If you really don't want to make a tarball, you can make a zip file. In either case, please make sure that the file unpacks into a single folder with your username. That folder should four subfolders, one each for problems 1, 2, and 3, and a combined folder for problems 4 and 5.

Unless specified otherwise in the problem, the .java files for each problem should be in a src subfolder of the problem folder, and should not have a package declaration. You can also include .txt or .md files in each folder that have notes you would like me to read, answers to non-coding questions, and sample output from any experiments you conduct. You may include a .txt or .md file in the top-level directory with general notes.

In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. You should do your best to format that code to the Sun/Oracle Java coding standards. I am likely to take off one point (on a 100-point scale) for each formatting error that I note, although I am also likely to allow up to three formatting errors without penalty.

You should document classes, interfaces, fields, and methods using Javadoc-style comments.

Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Since I should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. I will limit that form of extra credit to five points.

I may give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the issue you have observed and attempt to reword the question in such a way that it is answerable. You should also feel free to send me electronic mail at any time of day.

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.

Topics: Loops, Invariants, Arrays, Partitioning, Heaps

Varun and Ina understand why I like invariants, but have trouble writing their own, or at least maintaining them, so they've turned to you.

a. They've started working on an alternate version of partition in which elements equal to the pivot can either be on the left side or the right side. They don't like my standard approach, because they note that we sometimes swap a large element out of the large side and then back again. They also get bothered that I don't include the upper-bound in the subarray. Finally, they don't like that I indicate borders of cells, rather than the cells themselves.

They decide that their invariant should be:

+-+--------+---------+--------+
|p| <= piv | unknown | >= piv |
+-+--------+---------+--------+
 ^        ^           ^      ^
 |        |           |      |
 lb       small       large  ub

That is,

They put all their work together as follows.

    /**
     * Partition the elements between lb and ub, inclusive.
     *
     * @pre lb <= ub.
     */
    static <T> int partition(T[] vals, int lb, int ub, Comparator<T> order) {
        // Put a pivot at the start of the subarray.
        swap(vals, lb, lb + (ub-lb)/2);

        // Set up the bounds
        int small = lb+1;
        int large = ub;

        while (small <= large) {
            // Skip over small elements
            while ((small <= large) 
                     && (order.compare(vals[small], vals[lb]) <= 0)) {
                 ++small;
            } // while
            // Observation: At this point, vals[small] is large

            // Skip over large elements
            while ((small <= large)
                     && (order.compare(vals[large], vals[lb]) >= 0)) {
                 --large;
            } // while
            // Observation: At this point, vals[large] is small

            // We've reached large/small elements, swap 'em
            swap(vals, small++, large--);
        } // while

        // The element at position small is the last small element,
        // so we can swap it with the pivot.
        swap(vals, lb, small);
        return small;
   } // partition(T[], int, int, Comparator<T>)

Unfortunately, there are flaws in their analysis and implementation. Lupe, their class mentor, suggests that you help them by answering the following questions.

i. Are small and large initialized correctly to ensure that the invariant holds at the start of the outer loop?

ii. Is the test in the outer loop consistent with this loop invariant?

iii. If the invariant holds at the start of the first inner loop, how, if at all, is it violated at the end of the first inner loop?

iv. Given that expectation, how, if at all, might the invariant be violated at the end of the second inner loop?

v. Given those expectations, does the final portion of the outer loop restore the loop invariant?

vi. Within the outer and inner loops, are the array elements accessed in a way consistent with the loop invariant?

vii. If we assume that the loop invariant holds at the end of the main loop, is vals[lb] being swapped with the correct element?

b. After you answer those questions, Lupe suggests that we “think more like SamR”. In particular, Lupe suggests that we treat small and large more like borders.

+-+--------+---------+--------+
|p| <= piv | unknown | >= piv |
+-+--------+---------+--------+
 ^          ^       ^        ^
 |          |       |        |
 lb         small   large    ub

Answer the same questions i to vii for this new invariant.

c. Find as simple a correction as possible to fix the given code.

d. Ina decides we all need more practice and notes that we have not bothered to write an invariant for our iterative Heap.swapUp method. Write that invariant.

e. Varun thinks we need even more practice and notes that we have not bothered to write an invariant for our iterative swapDown method. Lupe reminds Varun that we've been using a recursive Heap.swapDown method. Write or find an iterative Heap.swapDown method.

f. Write an invariant for the Heap.swapDown method.

Topics: Dynamic Data Structures, Trees, Lists, Nodes, Recursive Processing

Your classmates, Tate and Anna, note that we often want to calculate information about data structures. They suggest that we extend the nodes in our favorite linked data structures, the list and the tree, with an additional field, info, that can hold an arbitrary piece of information. You can find their updated code in the exam repository.

a. Anna notes that it might be useful to identify the distance of each node from the end of the list. For example, in the list { a, b, c }, the node that contains a is two from the end of the list, the node that contains b is one from the end of the list, and the node that contains c is 0 from the end of the list, since it's at the end of the list.

To the linked list class, add a method, computeDistances(), that fills in the info field for each node with an Integer that represents the distance of that node from the end of the list.

You may only iterate the list once in doing this computation. In particular, you may only set the info field of each node once and you may only access the info field of each node once.

In addition, you may not declare any variables that hold arrays or dynamic data structures and you may not create any new nodes.

b. Tate, in response, suggests that we do something similar for trees. Instead of filling in the distance to the end, he wants you to fill in the height of the node, the distance to the farthest leaf.

To the BST class, add a method, computeHeight(), that fills in the info field for each node with an Integer that represents the distance of that node to the farthest leaf that falls below that node.

Once again, you may visit each node at most once in doing this computation. In addition, you may not declare any variables that hold arrays or dynamic data structures and you may not create any new nodes.

c. Anna, not to be outdone, suggests something a bit more interesting. Rather than adding a height, we should create a string that gives the keys in the subtree, in alphabetical order, separated by commas.

To the BST class add a method, computeKeySequences(), that fills in the info field with a String that represents all of the keys in the subtree, in order, separated by commas.

Once again, you should visit each node at most once. And, once again, you may not declare any variables that hold arrays or dynamic data structures and you may not create any new nodes.

Topics: Heaps, Hash Tables, Hash Codes

I was talking about this course to my colleagues, Theodore and Tessa, at a recent conference. While they approved of our regular use of unit tests, they also noted that they prefer to see more “white box” testing, in which we look inside the algorithm to make sure that things are okay along the way. “After all,” they suggest, “a student could write something that gives the same output as a hash table, but does not organize the data correctly”. They suggested that I therefore give you some practice running algorithms “by hand”.

a. Suppose we are working with strings, that our non-expandable hash table has a capacity of 20 elements, and we have chosen the primitive hash function of “add the value of the first and last letter of the string, using the following chart”.

a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
1  3  5  7  9  11 13 15 17 19 21 23 25 26 24 22 20 18 16 14 12 10 8  6  4  2

Show the state of the hash table after inserting the following ten strings in that order: "raynard", "russell", "charlie", "pamela", "george", "richard", "glenn", "howard", "samuel", and "john". Use each of the following table construction policies (so show four different tables). If a policy makes it impossible to insert a particular string, note that impossibility.

i. Bucketed (more than one value can be in the same location).

ii. No buckets, linear probing, offset of subsequent multiples of 7 for linear probe.

iii. No buckets, quadratic probing (offsets of 1, 4, 9, 16, 25, 36, 49, ... from the original location).

iv. No buckets, linear probing, using the value of the second character to determine the offset. (E.g., for "charlie", the offset would be multiples of 15 and for "pamela" the offset would be multiples of 1.)

b. You may recall that the Heapsort algorithm works by turning an array into a heap, and then repeatedly swapping the element at the top of the heap to the end of the heap and restoring the heap.

i. Show the state of the following array after we've run the heapify step, but before we've started swapping elements. Assume that smallest values have highest priority (which means we will probably be sorting the array from largest to smallest).

5, 1, 8, 2, 3, 7, 9, 4, 4, 6

ii. Suppose we start with the heap given in the following array.

1, 2, 3, 2, 4, 8, 4, 6, 9, 5

Show the state of the array after we've swapped the three smallest values to the end, and restored the heap after each swap.

Topics: JSON, ArrayLists

Ray and Ari have almost finished the JSON homework, but are stumped on arrays. Finish their implementation.

Topics: Trees, Output, Recursion

Prince Theresa has appreciated all of the lovely tree output we've generated with the approach of “print the node, then print all the children indented slightly more”. PT would like to see us do the same with JSON. PT suggests that each field of an object should be indented, and the value should be on a separate line, indented again.

Extend Ray and Ari's code to print an appropriate tree. Examples follow. You may find that you present the fields in a different order.

{"Name":"Sam"}

Object
  Name:
    Sam

{"Name":"Sam","Job":{"Employer":"Grinnell","Title":
"Professor of Comp Sci","StartYear":1997}}

Object
  Name: 
    Sam
  Job: 
    Object
      Employer: 
        Grinnell
      Title: 
        Professor of Comp Sci
      StartYear:
        1997

{"Values":[5,1,2,9,3]}

Object
   Values: 
     [ 
       5
       1
       2
       9
       3
     ]

{"Students":[{"First":"John","Last":"Doe"},
{"First":"Jane", "Last":"Doe","Grades":[]}]}

Object
  Students: 
    [ 
      Object
        First:  
          John
        Last: 
          Doe
      Object
        First: 
          Jane
        Last: 
          Doe
        Grades:
          [
          ]
    ]

For 1C, are we trying to fix the code given in 1A to match the invariants and such in 1A or 1B?

For 1E, what are the parameters that the swapDown procedure should take?

Could you explain again exactly what swapUp and swapDown do, so we have that information to reference in the actual exam?

For 1F, should we write the invariant for the iterative or recursive Heap.swapDown method?

Suppose I've found one issue in the partition method. Do I really need to analyze the other issues?

Please remimd me what you want for an invariant.

For 2A, are we supposed to create a separate test/experiment class that actually calls the method we wrote, computeDistances?

Can you remind me of the loop invariant for heap sort?

I understand that the algorithm sorts largest to smallest. For b.ii, Can you show the state of the heap after, say, 8 swaps and reheaps?

I worry about the call to info.next() in the switch statement in parseArray.

I approached the homework much differently. Do you have any suggestions?

The object fields in my tree appear in a different order than they appear in the sample output. Is that okay?

How should the indent of subtrees relate to the indent of their parent?

What about those weirdo dashes that you put in the experiment?