Question 5 [15 marks]
You have been hired by a prominent company that builds graphics software to implement the ADT
PixelSet. This is the description your client provides you:
PixelSet is a set S of red, green, and blue pixels that are represented by triples
(x, y, c). x and y are positive integers denoting a position of a pixel on the screen, and
c ∈ {R,B,G} denotes a colour. Each position can be assigned up to three colours. For
example (5, 3, R), (5, 3, B) and (5, 3, G) can co-exist in a PixelSet, but there cannot
be more than one (5, 3, R) in the same set.
The client also specifies the following operations to implement for PixelSet:
� ReadColour(S, x, y): Return the colours at position (x, y), i.e. the set { c | (x, y, c) ∈ S }.
� WriteColour(S, x, y, c): Assign colour c to position (x, y), i.e. add the triple (x, y, c) to S. If
position (x, y) already has colour c, then do nothing.
� NextInRow(S, x, y): Return the position of the next coloured pixel that appears after (x, y) and
in the same row as (x, y), i.e., return (x,min{ y′ | y′ > y and (x, y′, c) ∈ S for some c }). Return
(0, 0) if no such pixel exists or if (x, y) is the last pixel in that row. You can assume that a pixel
at (x, y) exists in the PixelSet.
� NextInColumn(S, x, y): Similar to NextInRow, return the position of the next coloured pixel
that appears after (x, y) and in the same column as (x, y) or (0, 0) otherwise. You can assume
that a pixel at (x, y) exists in the PixelSet.
� RowEmpty(S, x): Return whether Row x is empty, i.e. return True if and only if there does not
exist a triple (x, y, c) with the given x in S.
� ColumnEmpty(S, y): Similar to RowEmpty, return whether Column y is empty.
All the operations above must have worst-case runtime O(log n), where n is the total number of
coloured pixels in the PixelSet S. If this asymptotic bound makes you think of AVLs, then you’ve
cracked the first step! Now, answer the following questions:
(a) How many AVL trees are you using to implement PixelSet? What does each node correspond
to? What information is stored in each node?
(b) What are the keys that you use for sorting each of the AVL trees? For each AVL tree, define
carefully and precisely how you compare two pixels positioned at (x, y) and (x′, y′). This
comparison is important because AVLs need an ordering relationship between data points to
maintain the BST property.
(c) For each of the above operations, describe in detail how it works, and argue why it works correctly
and why its worst-case runtime is O(log n). Your solution should be in plain English. You may
choose to include pseudocode but it is not a substitute for a well-articulated description.
Hint: You can use any BST or AVL operations covered in class in your solution. You can also
refer to the runtimes we calculated instead of redoing the analysis here.
1