CSSE 230
HardyPart2 Programming Assignment  - 100 Points

Overview

In the WarmupAndStretching programming assignment, you found all Hardy numbers less than a given number. In this assignment, you are to write the nthHardyNumber method which efficiently finds the nth Hardy number (counting 1729 as the 1st Hardy number; i.e. nthHardyNumber(1) returns 1729, and nthHardyNumber(10) returns 65728).

Starting code will be in the HardyPart2 project in your pair's csse230-201410-hardyxx repository (info about your partner and your value of xx will be given to you in class).  Commit your working code to the repository.

Suggestion: Get a working version of nthHardyNumber very soon, so you have a few days to work on efficiency improvements.  Most of the credit for this problem is based on efficiency.

Efficiency note:  A simple approach is to start with 1 and check each number to see if it can be written as the sum of cubes in more than one way. But it is highly unlikely that this will be efficient enough to earn many points for this assignment, so I suggest that you consider other approaches.  Your choice of data structure(s) may be the key efficiency ingredient.

Objectives

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

See IncreasingJavaMemoryInEclipse.pdf for details on how to get Eclipse to allocate the correct amount of heap space for the Java virtual machine.

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.
    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 a3 + b3 = nth 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 nth 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 nth number "from scratch".   If you declare any fields (as opposed to local variables of a method) that are/contain arrays or collections, you should re-initialize those structures at the beginning of each call to nthHardyNumber.

Grading

See the grading checklist which the graders will use.

Answers to student questions

I have collected my answers to some student questions from the past. I may add some new questions and answers as this term's students work on this problem.