CSC 225 ASSIGNMENT 3 – PROGRAMMING AND WRITTEN

Description

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. You are not
permitted to revise your submission after the due date, and late submissions will not be accepted,
so you should ensure that you have submitted the correct version of your code before the due
date. conneX will allow you to change your submission before the due date if you notice a
mistake. After submitting your assignment, conneX will automatically send you a confirmation
email. If you do not receive such an email, your submission was not received. If you have
problems with the submission process, send an email to the instructor before the due date.

CSC 225 SUMMER 2016
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 3
UNIVERSITY OF VICTORIA
1. Consider a version of the deterministic quick-sort algorithm that uses the element at rank ⌊𝑛/2⌋ as
the pivot for a sequence on 𝑛 elements.
(a) What is the running time of this version on a sequence that is already sorted?
(b) Describe the kind of sequence that would cause this version of quick-sort to run in Θ(𝑛
2
)
time.
2. Illustrate the performance of the heap-sort algorithm on the following input sequence, S, by
drawing the heap tree after each insert() and removeMin() call. That is, there should be 20 trees,
each the final result of the given operation after bubbling is complete.
𝑆 = (2, 5, 16, 4, 10, 23, 39, 18, 26, 15)
3. Design algorithms for the following operations for a node v in a binary tree T:
(a) preorderNext(v): return the node visited after v in a preorder traversal of T.
(b) inorderNext(v): return the node visited after v in an inorder traversal of T.
(c) postorderNext(v): return the node visited after v in a postorder traversal of T.
What are the worst-case running times of your algorithms?
4. Define the internal path length, 𝐼(𝑇), of a tree T to be the sum of the depths of all the internal
nodes in T. Likewise, define the external path length, 𝐸(𝑇), of a tree T to be the sum of the
depths of all the external nodes in T. Show that if T is a proper binary tree with n internal nodes,
then 𝐸(𝑇) = 𝐼(𝑇) + 2𝑛.
5. Suppose we are given a sequence S of n elements, each of which is an integer in the range
[0, 𝑛
3 − 1]. Describe a simple method for sorting S in O(n) time.
Hint: Think of an alternate way of representing the elements.