Exam 2: More Object-Oriented Design, ADTs, and Algorithms

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.

There are four 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 four problems correctly or mostly correctly, you will earn an A. If you complete three problems correctly or mostly correctly, you will earn a B. If you complete two problems correctly or mostly correctly, you will earn a C. If you complete one problem correctly or mostly correctly, you will earn a D. If you complete no 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.

I rarely give makeup problems because my experience in past semesters is that students spend a lot of effort on such problems but do not significantly improve their grade. There also will not be time to do makeup work for this examination.

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 six hours, depending on how well you've learned the topics and how fast you work. (When I do the problems, I will report how long each one took me.)

This examination has a required prologue that must be completed by the Sunday evening before the exam is due. (Ideally, you would complete it by Friday evening.) The prologue is intended to help you get started thinking about the examination.

This examination has an epilogue that must be completed by the evening after the exam is due. The epilogue is intended to help you reflect carefully on the examination. The epilogue is required. Failure to fill in the epilogue will incur a penalty of five points on the exam.

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 unless you create a private repository for your exam.) 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 in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. 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 include both of the following statements on the cover sheet of the examination.

Please sign and date each statement. 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).

Exams can be stressful. Don't let the stress of the exam lead you to make decisions that you will later regret.

You must present your exam to me in two forms: both physically and electronically.

While your electronic version is due at 10:30 p.m. Tuesday, your physical copy will be submitted in class on Wednesday. It is presumed the physical copy matches the electronic copy. Any discrepancies (other than formatting) will be considered a misrepresentation of your work and referred to the Committee on Academic Standing.

Physical copy: For the physical copy, you must write all of your answers using the computer, print them out, number the pages, staple them together (except for the cover sheet), and hand me the printed copy. For your benefit and for mine, I am doing blind grading on this examination, so you have been assigned a number to use on your exam. Please make sure that your assigned number appears at the top of every page. You should also number the printed pages sequentially. If you fail to number the printed pages, you may suffer a penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of penalty.

Along with your stapled and printed answers, you should turn in a separate cover sheet for the examination. The cover sheet should include (1) the two hand-written academic honesty statements (individually signed and dated, if it is appropriate for you to sign each), (2) your name, and (3) your assigned number.

The code and comments in your printed copy must use a fixed-width (a.k.a., monospaced or fixed-pitch) font; viable candidates (depending on your platform) include Monospace, Courier, Courier New, Monaco, DejaVu Sans Mono, Free Mono, Liberation Mono, and Lucida Sans Typewriter. Failure to format your code with a monospace font will result in a penalty. You must also ensure that any code you turn in adheres to the class code conventions.

Electronic copy: You must also submit an electronic copy of your exam. You should create the electronic version by making a tarball of any relevant code and emailing me the tarball. Here are the steps for making a tarball.

Code: 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 class formatting standards.

Documentation: You should document classes, interfaces, fields, and methods using Javadoc-style comments. You should specify preconditions and postconditions for each method.

Care: 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.

Partial Credit: 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.

Ali T, your classmate who is always so proper that people refer to zir as “Prim Ali” has noted that there are many algorithms that benefit from large primes. But how do we get large primes? Heigi and Kerstine (who are usually greeted by their first names) say “Use BigInteger.probablePrime”! Of course, you don't find that satisfactory, and what to learn more. If you talk to the math faculty (or look on Wikipedia), you'll learn that there are some proposed formulae for generating primes, although none of these formulae is completely successful.

So, we've now moved from the problem of generating primes to the problem of determining whether a candidate number is a prime. And, believe it or not, there's a well-known algorithm for probabilistically checking primality. Fermat's little theorem says that for any prime, p, and positive integer, i, less than p, i^p-1 is congruent to 1 mod p. (In Java, we'd express that as i.pow(p-1).mod(p).equals(BigInteger.ONE).) However, for composite numbers, c i^c-1 is usually not congruent to 1 (mod c). So, we can generate a bunch of different i values, do the exponentiation, and compare the result to 1.

Of course, if p is really large, we don't want to use a for loop to compute i^p-1 mod p; we'd rather use the divide-and-conquer solution. What is that solution? Your classmates Diva and Connor suggest that we use the rule that i^2k is the same as (i^k)².

Is that enough? No we don't want to compute i^p-1, because that's likely to be really really large, and we're going to be reducing it at the end. A little analysis by your classmate Maude shows that we can safely reduce by the modulus at every step, rather than just at the end.

Using these ideas, write a method, probablyPrime(BigInteger bi), that generates a large number of i values, computes i^p-1 (mod p) for each of them, and compares the result to 1. If all of the results are 1, probablyPrime should return true. If any of the results are not 1, probablyPrime should return false.

You should also implement a separate exponentiation method.

In implementing probablyPrime, you may not use BigInteger.modPow nor BigInteger.isProbablyPrime. Your goal in this problem is to discover if you can implement them yourself.

Your classmates, Randy and Linnea, recall that we started to design a randomized linear structure in class, and have built most of the code for that structure, which you can find in the Problem2 directory.

Your Professor, Hugh DeWitt, asks everyone else in the class to critique the code. Not surprisingly, they come up with a variety of issues.

As is his wont, Hugh DeWitt suggests that you should address all of these problems.

a. To address Dinah and Mick's concerns, extend the code so that if we run out of space in the array, we allocate a bigger array. (You must continue to use an array; you may not use any of the Java collections or the ilk.)

b. To address Remy and Delbert's concerns, implement the remove method in the iterator.

c. To address Phil and Faust's concerns, implement a fail-fast policy in the iterator using our standard technique. (You may also identify another approach, if you so choose.

Your classmates, Ida, Ray, and Tor, appreciate that we had the opportunity to explore various mechanisms for printing out the elements of trees. However, they think we were somewhat misguided in our approach. “After all,” they note, “printing every element is just a special case of iteration.” They suggest that we should instead design iterators that can handle the various traversal mechanisms.

To allow the user to describe the policy they want the program to use, they define an enumerated type, Traversal, which includes a variety of values such as DEPTH_FIRST_POSTORDER_LEFT_TO_RIGHT.

Of course, your classmates, Rafe and Acta, are worried that you someone will try to implement each iteration method with more-or-less the same code. They note that we discovered that most of the depth-first iteration could be done with a stack, and the order in which we put the value and the two subtrees on the stack governs the traversal order. Hence, the only difference in the code should be what goes on the stack when. They also note that for preorder breadth-first traversal, we need a queue and an ordering of children. “Hence”, they say, “we should be able to write a generalized tree iteration mechanism that just takes a linear structure and an order of value/left/right as parameters”.

You guessed it. Hugh DeWitt thinks that you're ideally suited to handling this generalization task. Implement the generalized iteration mechanism as consisely and clearly as possible. You should not implement the remove method.

Prof. DeWitt admits that the Rafe and Acta approach is difficult, so he permits you to write repetitious code if necessary. Rafe and Acta, in response, add a bit of supporting code to the class that they think will help. (You can feel free to ignore their code.)

We've seen two mechanisms for implementing hash tables: We can use chained (a.k.a. bucketed) hash tables, in which each cell in the hash table contains an association list, or we can use probed (a.k.a. open) hash tables, in which we look elsewhere when the location in the table contains a key other than the expected key.

The code accompanying this examination provides both implementations of hash tables. However, as per his normal practice, DeWitt has left the remove methods unimplemented.

Your classmates Remy and Delbert reiterate that it is essential to implement remove.

While you are worried that you will have to do both kinds of removal, your classmates Buck and Etta volunteer to handle the chained version. But that leaves the open hash table.

Implement OpenHashTable.remove.