Assignment 3 Program that prints out all integers

1 Programming Assignment
Write a program that prints out all integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in the
range [0, 𝑛], in sorted order while using 𝑂(𝑛) space. That is, you cannot use an array of size 𝑛
2
and then sort it.
Input: A nonnegative integer n.
Output: A sorted list of all integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in
the range [0, 𝑛].
For each value integer of this form you will need to keep track of three things, the integer itself,
𝑎
3 + 𝑏
3
, and the two integers used to create it, 𝑎 and 𝑏. So, let’s denote our elements with the
triples (𝑎
3 + 𝑏
3
, 𝑎, 𝑏). We do not need duplicate values (𝑎
3 + 𝑏
3 = 𝑏
3 + 𝑎
3
) so we can assume
that 𝑎 ≥ 𝑏.
Hint: You can start with the 𝑛 + 1 values, (0
3 + 0
3
, 0,0), (1
3 + 0
3
, 1,0), … , (𝑛
3 + 0
3
, 𝑛, 0). At
any given time if the current smallest element is (𝑖
3 + 𝑗
3
, 𝑖,𝑗) and 𝑗 < 𝑖, then you may print
𝑖
3 + 𝑗
3
, remove it from your data structure and add new element (𝑖
3 + (𝑗 + 1)
3
, 𝑖,𝑗 + 1).
Otherwise, you may just print it, remove it and then find the next smallest element.
Your task is to write a java program, stored in a file named SortedSumsOfCubics.java that
contains a function SortedSumsOfCubics, which takes a nonnegative integer n as its only
argument, and prints out all the integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in the
range [0, 𝑛], in sorted order. For example, if the input is 𝑛 = 3, the output should be,
0 1 2 8 9 16 27 28 35 54
The main function in your code should help you test your implementation by getting an integer
from input and sending it to the function above.
2 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (various values for n, some very large) and human inspection.
Score (/50) Description
0 - 5 Submission does not compile or does not
conform to the provided description.
5 - 15 The implemented algorithm uses 𝑂(𝑛
2
) space or
is inaccurate. That is, the outputs are not in sorted
order or some are missed.
15 - 20 The implemented algorithm uses 𝑂(𝑛) space and
𝑂(𝑛
3
) or worse running time or minor errors.
20 - 25 The implemented algorithm uses 𝑂(𝑛) space and
𝑂(𝑛
2
log 𝑛) running time and is accurate.
To be properly tested, every submission must compile correctly as submitted. If your
submission does not compile for any reason (even trivial mistakes like typos), or was not
based on the template, it will receive at most 5 out of 25. The best way to make sure your
submission is correct is to download it from conneX after submitting and test it.