COMP3506/7505 Homework Task 1

Due Fri 9 Aug 2019, 6:00pm

10 marks total

Overview

The goal of this problem set is to become familiar with ADTs, CDTs, array-based data structures,

and basic time and memory analysis.

You have been supplied with an interface defining the Grid ADT - a two-dimensional grid, where

each element is stored at an (x, y) coordinate pair. You will be required to implement an array￾based grid in the ArrayGrid.java class.

Your Task

1. (5 marks) Implement the ArrayGrid CDT as per the Grid ADT specification. Your imple￾mentation should make use of a multi-dimensional array.

2. (5 marks) Analyse the advantages and limitations of your implementation in terms of memory

efficiency. In particular, you should:

• State (in big-O notation) the implementation’s memory complexity and briefly explain

how you calculated this bound

• Use this bound to evaluate the overall memory efficiency of your implementation -

you should especially consider the case where your grid is very large but has very few

elements

• Research and describe at least one alternative implementation that has significant ad￾vantages over the one chosen

• Compare the alternative implementation with your chosen approach in terms of both

memory and runtime efficiency

1

Constraints

• You may not edit Grid.java

• Apart from those defined in the Grid interface, you may not add non-private member vari￾ables or helper methods to ArrayGrid.java

• You may not use anything from the Java Collections Framework

• Your implementation should only use basic Java programming constructs and not other

libraries

Failure to adhere to these constraints will result in no marks for this exercise.

Submission and Marking

Submit two files as a part of your submission. Your solution to question 1 should be in ArrayGrid.java.

Your answers to question 2 should be in a PDF file named README.pdf. Do not submit any other

files or directories.

Question 1 will be marked by an automated test suite with timeouts present on each of the tests. A

sample test suite has been provided in ArrayGridTest.java. This test suite is not comprehensive

- there is no guarantee that passing these will ensure passing the tests used during marking. It

is recommended, but not required, that you write your own tests for your CDT. Marks may be

deducted for poor coding style.

Question 2 will be manually marked by a tutor. Your analysis for this question should be as concise

as possible (no longer than a couple of paragraphs).

Late Submissions and Extensions

Late submissions will not be accepted. It is your responsibility to ensure you have submitted your

work well in advance of the deadline (taking into account the possibility of computer or internet

issues). See the ECP for information about extensions.

Academic Misconduct

Students are reminded of the University’s policy on student misconduct, including plagiarism. See

the course profile and the School web page:

http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism.

2