COMP2123/2823/9123 Assignment 3
Summary
This assignment involves writing the code that performs operations on a given data structure, and
writing a report that analyses the big-O worst-case time costs of these operations. (Students in the
postgrad unit COMP9123 also have extra aspects in their report.)
Submission details
• Due: Friday May 18 (Week 10) at 11pm
• Submit your report via Canvas through Turnitin. You may resubmit as often as you wish
without penalty, until the due date. (We will mark whichever submission is the latest among
those before the due date.)
• Submit your report as a single document (preferably a pdf or doc file). Your work must be
typed text. (No images of text, although you can use diagrams if you think it helps.)
• To support anonymous marking, do not put your name on the document, nor include your
name in the filename. (It is fine to put SID on the document or the filename.)
• Submit your source code in the Assessments section on Ed. You may resubmit as often as
you wish without penalty, until the due date. (We will mark whichever submission is the latest
among those before the due date.)
• Value: 10% of the unit
• Language: You may choose to program in either Python or Java.
• This is an individual assignment, so your code and writing should be entirely your own work
(except where you include scaffold code that we have provided). Make sure that you acknowl-
edge sources of information, and any direct quotations. If you re-use any code from the text-
books for this course, this must be acknowledged, just like any other sources. We will be using
similarity matching software on your code and on your report. Please do not plagiarize;
make sure that you follow the University policy on academic honesty.
1
COMP2123/2823/9123
1 Description
1.1 Quadtrees
The quadtree is a hierarchical spatial data structure. A quadtree is a tree data structure in which each
internal node has exactly four children. The internal nodes represent a partition of the two dimensional
space into four equal quadrants (NW - North West, NE - North East, SE - SouthEast and SW - South
West). The structure is used to improve the performance of applications that use large spatial data sets
including: ray tracing in computer graphics, collision detection for simulation and gaming, motion
planning for robotics, nearest neighbor calculation, image processing, and many, many others.
In this assignment we are going to use quadtrees to efficiently store black-and-white bitmap images.
A black-and-white bitmap image is a dot matrix, representing a rectangular grid of pixels, where each
pixel is either black (which can be represented by a single 1-bit) or white (0-bit). A bitmap corre-
sponds bit-for-bit with an image displayed on a screen. A black-and-white bitmap is characterized by
the width (W) and height (H) of the image in pixels and by one bit per pixel. A bitmap consisting of
8 8 pixels and its representation is shown in Fig. 1. The height and width of a bitmap can be any
positive integers but for this assignment we will assume that the bitmap is a square (H = W) and that
the height and widths are a power of 2 (in Fig. 1 its 23 = 8).
0
1
1 1
1 1
1
1 1
1 1 1
1 1 1
11
1
1 1
1 1
1
0 0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0
0 0 0 0
0 0 0
0 0 0 0
0 0 0
Figure 1: A black-and-white bitmap of height and width 8 = 23.
There are many variants of quadtrees. We are going to use one specifically for bitmaps. The root
node represents the entire image region. If the pixels in any region are not entirely 0s or 1s, it is
subdivided. In this application, each leaf node represents a block of pixels that are all 0s or all 1s.
Note the potential savings in terms of space when these trees are used for storing images since images
often have many regions of considerable size that have the same colour value throughout. Rather
than storing a big 2-D array of every pixel in the image, a quadtree can capture the same information
potentially many divisive levels higher than the pixel-resolution sized cells that we would otherwise
require. The tree resolution and overall size is bounded by the pixel and image sizes. Fig. 2 shows an
example of a quadtree constructed from the image in Fig. 1.
Data Structures and Algorithms Page 2 of 7
COMP2123/2823/9123
NW SW NE SE
root
Figure 2: The subdivision of the bitmap and the corresponding quadtree.
Data Structures and Algorithms Page 3 of 7
COMP2123/2823/9123
Level 0: The root of the quadtree represents the entire region occupied by the bitmap. Since it
contains both black and white pixels it will have four children representing the four quadrants NW,
SW, NE and SE.
Level 1: Each of the quadrants contains both black and white pixels so each node will have four
children.
Level 2: At the second level there are several regions of size 2 2 pixels that have only one colour.
For example, NW quadrant of the NW quadrant has only white pixels and will therefore be a leaf
marked as ‘white’ (a 0-bit), while the SE quadrant of the SE of the SE quadrant only has black pixels
and will therefore be a leaf marked as ‘black’ (a 1-bit). Some regions will still contain both black and
white pixels and will therefore have four children each.
Level 3: At the lowest level each region (pixel) will either be black or white, hence, the corresponding
nodes will be leaves marked either as black or white.
1.2 Methods to implement
Your task is to implement a set of methods working with quadtrees. The following methods are
required. Observe that some of the methods require you to modify the existing quadtree, whereas
others require you to return a new quadtree and leave the input quadtrees unmodified.
• Blacken the entire north-west quadrant. (Modify existing quadtree.)
• Count the number of pixels of a given colour in the bitmap represented by the quadtree.
• Invert the colours in the bitmap represented by the quadtree, i.e. turn every black pixel white
and every white pixel black.(Modify existing quadtree.)
• Change the colour of one pixel (x;y) in the bitmap represented by the quadtree, to a specified
colour. (Modify existing quadtree.)
• Compute the overlay of two bitmaps of the same size. In the overlay a pixel is black if either
of the input images has a black pixel in the same location. That is, a pixel in the output image
is white only when the corresponding pixel in both input images is white, otherwise the output
pixel is black. Rather than do the operation pixel by pixel, one can compute the overlay more
efficiently by leveraging the quadtree’s ability to represent multiple pixels with a single node.
(Generate a new quadtree, leaving the input trees unmodified.)
Note: for full marks, the resulting quadtree needs to be in "reduced" form, i.e. any subtree that is
entirely one colour needs to be reduced to a single leaf.
We strongly encourage you to implement most of the methods recursively. There will be at least one
question in the exam which will be much easier to answer recursively than iteratively, so this is a great
opportunity to get some more practice with recursion. If you would prefer to iterate over some sort
of tree traversal for some of the methods, you may do so, although you will need to implement the
appropriate traversal(s) yourself.
Data Structures and Algorithms Page 4 of 7
COMP2123/2823/9123
2 Implementation
2.1 Scaffold
You may implement your submission in either Java or Python. The only file which you need to edit
is QuadtreeBitmap.java or quadtree_bitmap.py, which contains a class QuadtreeBitmap, which
contains the methods you need to implement.
Our representation of quadtrees will not have a separate Node class. Instead, a QuadtreeBitmap
itself can be thought of as a node. A QuadtreeBitmap is either a leaf, in which case it represents
a square region of pixels all of the same colour; or an internal node, in which case it has four child
QuadtreeBitmaps, one per quadrant.
We have provided a scaffold which includes many helpful things, such as:
• A method which constructs a QuadtreeBitmap from a string representation. See below for
details on the string representation format expected.
• A method which converts a QuadtreeBitmap into a string representation.
• Various constructors which you might find helpful, e.g.
– A constructor which creates a leaf QuadtreeBitmap for a given location and size.
– A constructor which creates a QuadtreeBitmap for a given location and size, with
quadrants given by a list of QuadtreeBitmaps provided as an argument.
• Convenience methods, e.g.
– A method which enumerates quadrants in the following order: northeast, northwest, south-
east, southwest.
– A method which determines which quadrant an input (x, y) coordinate pair lies within. (If
any.)
– A convenience method which you may enable, which reads a string representation of a
bitmap from standard input and constructs the corresponding QuadtreeBitmap.
– Methods which generate string representations of a QuadtreeBitmap, both as a string
representation of the bitmap it encodes, and with boxing interspersed to depict its tree
structure.
Empty method definitions have been provided in the QuadtreeBitmap class for each of the meth-
ods you need to implement. A main method, which will not be tested, has also been provided and may
be used by you for experimentation/testing. We advise against changing the other methods provided
in the scaffold. You are allowed to write additional methods, classes, etc., and add additional source
files to your assignment workspace as you see fit, though take note of the plagiarism notice above.
Data Structures and Algorithms Page 5 of 7
COMP2123/2823/9123
2.2 Libraries
You may, and indeed are expected to make use of data structures either built into your language of
choice or supplied by your language’s standard library. You may make use of other features of your
language of choice’s standard library, and any code provided in the textbooks for this course.
Use of external libraries is not allowed.
2.3 String Representation of Bitmaps
To generate a QuadtreeBitmap from text, you will need to provide it in a particular string repre-
sentation format. The expected format is a string consisting of a newline-separated sequence of rows,
where each row consists of a sequence of characters which each encode the colour of a pixel: either
’*’ for black or ’.’ for white.
For example, the string representation of the bitmap in Fig. 1 is the following:
1 ........
2 .....***
3 ...***..
4 ..**....
5 ..*.....
6 .**...**
7 **...***
8 *....***
3 Report
You must write a short report, and submit it via Turnitin. The report should have a heading which
gives your SID (but not your name!) and also indicates which unit you are enrolled in.
The report contains the following content:
• In a separate section for each of the 5 public methods that you are asked to implement, you
should describe the algorithm you intend to use for this method. You need to state the big-O
worst-case runtime of this algorithm, in terms of the dimension of the bitmap. You should
also give a justification of this cost, for example, by indicating how much of the quadtree is
examined, and how much work is done on each node. Note that your analysis can also include
discussion of the costs of private methods that are called in your public method.
• If you are a postgraduate student enrolled in COMP9123, you need two extra sections in the
report. In one section, you discuss how useful (and how easy to use) are the methods we have
put on the bitmap. In the final section of the report, describe some extra methods you would
propose to extend the functionality of the system. Explain what each proposed method would
do, and how this could be useful.
Data Structures and Algorithms Page 6 of 7
COMP2123/2823/9123
4 Grading scheme
Automatic grading [3 points]. The ed platform. will check whether the program produces the correct
output on various inputs. Some of the inputs we check will be visible to you during submission (this
are called public tests). There are other tests where you see whether it passed, but can’t see what input
was used, and still others which we check only after the due date. Auto-grading is worth 4 points, and
the score depends on how many of our tests are passed. If your code passes all the public tests, it will
get at least half the available marks. If it gives the correct output on all the tests, it will get full marks
for this component of the grading.
Hand marking [2 points], only for students in COMP2123 and COMP2823. Part of the marking
of your code will be done by hand. We will grade your code on its readability and overall quality;
this is worth 2 points. To gain half the marks for this component, you must have implemented several
of the public methods in a sensible way, and also your code needs to be understandable without
great effort by a reader. That is, your code should be well laid out, with an internally consistent
style. Comments should be used where otherwise the reader might become confused. Variables and
methods should be named appropriately. If appropriate, helper methods should be used to avoid
duplicating code, and to make any very complex methods easier to understand. You should be using
the typical idioms of the language (for example, when traversing a list). Three-quarters of the marks
for this component would be awarded for code where the code is fully correct, most of the methods
are implemented efficiently, and the code is easy to follow for a reader. To get full marks, your code
should be exemplary: something we could show to other students as a model or ideal solution, for
correctness, efficiency, simplicity, and clarity. Note that if you have an efficient design, and the code
is not easy to understand, then you will get less than half the marks.
Run-time analysis [5 points]. This is based on your report. Note that you can gain these marks
even if you didn’t write any code, as long as you analyse algorithms that you describe in the report,
intended to operate on the bitmap quad tree. There is 1 point for your analysis of each of the 5 public
methods. To get half the point, you describe a reasonable algorithm for the task, and you state a
correct big-O for its worst-case running time. To get the whole point, you also provide convincing
and valid arguments that justify your claim about the cost.
Evaluation of usefulness [2 points], only for students in COMP9123. This is based on your report.
Note that you can gain these marks even if you didn’t write any code. To gain half these points,
you should explain how each of the methods we included would be used, and you need to have
sensible comments on the value and convenience of these uses for the intended users. Three-quarters
of the marks for this component would be awarded where the discussion is insightful, and where
you propose and justify at least two extra methods that really add value. The full points are for
an exemplary solution, that captures the tradeoffs and shows deep understanding of how the given
methods, and at least four others that you propose, could be used.