CSSE 230
HardyPart2 Programming Assignment  - 100 Points

Overview

Objectives

• Choose data structures to make an algorithm efficient.
• Make intelligent space vs. time tradeoffs
• Experiment with various algorithms.

Detailed specifications

In this assignment you will most likely want to select and adapt data structure(s) from the Java Collections Framework, rather than implement a new data structure.  This problem focuses on the interplay between data structures and efficient algorithms. You will also need to deal with space vs. time tradeoffs, as you have to solve this problem using a fixed amount of heap space.  The bottom line is that you should write your code so it maximizes the largest value of n for which you can compute nthHardyNumber(n) in less than one minute using at most 900 megabytes of heap space. In 201610, we will run it on a Lenovo W530 - there may be slight differences between machines, but as you know, efficiency of the code is the most important factor. 

The JUnit test cases will start with small values of n, and gradually increase until your program produces an incorrect answer or runs out of memory.  The correctness part of your grade for this project will be based entirely on the largest n for which you get the correct answer within the given space and time constraints.

How the tests will run: Each JUnit test is assigned a certain number of points, based on getting the correct answer within one minute. It also prints to the console some additional information that you may find useful.  The total number of points that your program earns before it fails a test or takes more than a a minute to run is your score for the correctness part of this assignment. If a test fails for one value of n, it is extremely unlikely that the test for a higher value of n will succeed, so in order to make testing your program faster, we will not run it for higher values of n.  Note that the tests do not time out until 90 seconds;  this will give you an opportunity to see whether you almost succeeded, so that you can know whether a minor improvement might perhaps  get you under a minute for this value of n.  Also, if a test takes only slightly more than minute, we will rerun it to see if it will finish in under a minute next time, because there is some variability based on what else the computer is doing at the time.

84 points will be considered "full credit" for the correctness part of this problem;  if the JUnit tests yield more points for your program, those points will be extra credit.

Follow the directions in IncreasingJavaMemoryInEclipse.pdf to get Eclipse to allocate the correct amount of heap space for the Java virtual machine. If you don't do this, you might  earn fewer points when I run the tests.

Hardy Commandments

1. Your code for nthHardyNumber must not assume that it will there is a maximum value of n that it has to handle, except for the limitations of the long data type. You should write the code in such a way that, if you ran it with enough heap space and gave it enough time, it would compute the answer for any n that is small enough so that your  program does not have to deal with numbers greater than the largest long integer (Long.MAX_VALUE, which is about 9 quintillion).   So you may not allocate an array or other structure that is "just large enough" to handle the values of n that your program can run in under a minute. You may not even allocate a data structure whose size is a function of n, unless you can rigorously prove (not just from observation) that it is guaranteed to be large enough. I've only had one student (a senior science major) who satisfied me with such a proof, so don't take this lightly.
   Commentary: Your program is not allowed to do its calculations in a way that requires knowing in advance the largest possible a, b, c, and d that you need to check. Nor can it store the already-computed values in an array whose size is determined before the value of nthHardyNumber's parameter n is known.
   Hint (you are not required to do it this way): You can’t know in advance how large the a and b (for a³ + b³ = n^th HardyNumber) will be. But if you first generate n different Hardy numbers, you can use the information you get from them to calculate an upper bound for the a and b. Then use that maximum to finish the calculation of the n^th Hardy number. (It's hard to describe this clearly without too many "spoilers").
2. You must not cache any calculation results between calls to nthHardyNumber; this means that the timing tests will be based on computing the n^th number "from scratch".   If you declare any fields (as opposed to local variables of a method) that are/contain arrays or collections, you must re-initialize those structures at the beginning of each call to nthHardyNumber.

Grading

Answers to student questions