Algorithms and OOD (CSC 207 2014F) : Assignments

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

This examination is in “draft mode” and will remain in draft mode until class time on Monday, December 1.

Assigned: Wednesday, 26 November 2014


Exam Format

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.

Academic Honesty

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.

  1. I have neither received nor given inappropriate assistance on this examination.
  2. I am not aware of any other students who have given or received inappropriate assistance on this 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.

Presenting Your Work

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.

  1. Remove any cruft (needless files) from your directory structure. I don't want to see .class files, editor backups, or anything similar. You should, however, leave the .git directory in the examination.
  2. Switch to the parent directory of your exam directory. (Note that your exam directory should be named username).
  3. Rename your examination directory to your given number (e.g., 297672).
  4. Issue the command tar cvzf number.tgz directory.
  5. Make sure that the tar file contains the appropriate contents using the command tar tf username.tgz. For example, if I were to check my tarball, I might see something like the following.
    > tar tf 297672.tgz

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.

Getting Help

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.


Clone the repository using the following command, which will help ensure that you have the correct directory structure. Note that I've set things up so that you can treat each problem as a separate Eclipse project. Please do not make one project for the whole exam.

$ git clone *number*


Problem 1: Primality Testing

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, ip-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 ic-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 ip-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 i2k is the same as (ik)2.

Is that enough? No we don't want to compute ip-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 ip-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.

Problem 2: Random Linear Structures

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.

  • Dinah and Mick are concerned that the linear structure can fill. They suggest that we should allow structures to expand to handle how ever many elements the client adds (up to system limits, of course).
  • Remy and Delbert, note that we often find utility in a working Iterator.remove method, or at least learn something when we implement it.
  • Phil and Faust suggest that the iterator is likely to have difficulty working after the structure is changed by either get or put.

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.

Problem 3: Traversing Trees

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.)

Problem 4: Removing Values from Hash Tables

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.

Questions and Answers

General Questions

What is a general question?
A question that is about the exam in general, not a particular problem.

Problem 1

How long did this take you?
Ten minutes. But I've written a recursive exponentiation procedure many times.
The version of Fermat's Little Theorem that I found online says that (ip - i) is evenly divisible by p.
It's the same thing, believe it or not. If (ip - i) is evenly divisible by p, then ip is equivalent to i (mod p). Divide both sides by i, and you get the formula that I gave you.
What's with this “(mod p)”? I thought mod took two arguments?
Sorry. Switched to traditional math notation. I'll add a note about the standard Java notation.

Problem 2

How long did this take you?
Sixteen minutes. About four minutes to make the array expand. About seven minutes to write the remove method. About five minutes to implement the fail-fast approach. A few minutes were spent looking up the exceptions I needed to throw (ConcurrentModificationException for fast failure, IllegalStateException for remove). I also had a small brain freeze in which I decided that the remove method didn't make sense (but then I realized that it did).
Did doing this problem inspire you any thoughts you want to share?
1. I realized that I had neither tests nor experiments to illustrate the remove method. So I added some. 2. I implemented remove in the way that AK suggested for get, along with our standard flag for repeated removal in iterators. 3. I implmented fast failure in the standard way.
Does it matter what replaces the value that was deleted? [2014-12-04]
No. However, you need to make sure that your iterator still visits all the values. For example, if I have five values in the structure and call next, next, remove, next, next, and next, that last next should succeed.

Problem 3

How long did this take you?
Too long. I went back and made lots of changes to the support structure, which was too complex. Then the new version took me under ten minutes.
What did Rafe and Acta add?
At last count, they added the LinearStructureFactory class, the traversalStructures and traversalOrders fields (and the incomplete setup method for initializing them), QUEUE_FACTORY and STACK_FACTORY, the unpack method, the initialization cdoe for the iterator, and some other things I've probably forgotten.
Do I have to use all of that?
Prof. DeWitt and I agree that the generalized iteration can be hard. So you need not use any or all of that. But if you get the approach, it should be useful to have everything there.
Do I have to implement the keysIterator method or anything similar? [2014-12-04]
When I get something from remaining, I want to check whether it's a value or a node. If I use instanceof V, Eclipse complains. What should I do? [2014-12-04]
Use instanceof BSTNode instead. Type variables are a pain in the neck.

Problem 4

How long did this take you?
Under ten minutes.
Any hints?
Remember that when we have a conflict, we shift an element. That means that we need to look for things to shift back. And there may be a sequence of things to shift backwards (e.g., if we shift the next thing back, the thing after it may also have been shifted). There are also some potentially subtle issues. For example, suppose v1 and v3 have a hash code of h and v2 has a hash code of h+offset. If we v1, v2, and v3 and then delete v1, the first thing after v1 (that is, v2) is in the right place, but the next thing (that is, v3) is not in the right place.


Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. I usually limit such extra credit to five points. However, if I make an astoundingly large number of errors, then I will provide more extra credit.

I will not accept corrections for credit until after I have taken the examination out of draft mode.

I will not credit corrections for text in the Q&A and errata sections, since those are often written quickly to get information out to students.

I generally will not credit corrections to text that appears on comments in code.

  • they things” should be “they think”. [AOA, 1 point]
  • Broken links to prologue and epilogue. [AOA, 1 point]
  • There's only one “T” in “Mileti”. [AK, 1 point]
  • fo” instead of “of”. [ZW, 1 point]
  • Missing comma after “i, less than p”. [LBA, 1 point]
  • Bug: Fail to recompute capacity in [EF, 1 point]


I learned about the Fermat probalistic primality test in a recent lecture by Joe Mileti.