Description
Question 1
2
Suppose that your Quick-Sort algorithm uses a pivot rule that always picks the
FIRST element. So for any array A, regardless of size, it picks the element at
A[0] as its pivot. Draw a quick-sort tree for the algorithm as it sorts the following
array (without in-place partitioning):
[8 2 1 7 6 3 5 4]
Question 2
Consider the following graphs presented in three different representations:
1. a drawing of vertices and edges
2. an adjacency list
3. an adjacency matrix
Graph 1:
Graph 2:
Graph 3:
a) Draw graphs 2 and 3 as vertices and edges (similar to graph 1).
b) Convert graphs 1 and 3 into adjacency lists (similar to graph 2).
c) Convert graphs 1 and 2 into adjacency matrices (similar to graph 3).
d) What pairs of graphs are isomorphic? Indicate the mapping from one graph’s
vertex labels to the other for each pair.
e) Draw a valid spanning tree for graph 2 rooted by Sam.
f) Provide an associative array, Parents, for all nodes in the spanning tree of
graph 2 rooted by Sam. Parents should consist of a set of key-value pairs where
each vertex in the graph has a key, and the associated value for each key is the
node’s parent in the spanning tree.
3
Question 3
Provide the order of vertices visited for both a pre-order and post-order
traversal of the following graph. Begin each traversal at vertex A.
When choosing between neighbours to visit first, assume the algorithm
chooses the neighbour that comes first alphabetically.
4
Question 4
Images can be represented as 2-dimensional arrays of pixels. Usually, each pixel’s
Colour is based on Red, Green and Blue (RGB) components between 0 and 255. An
RGB value of (255,0,0) would be red, whereas (0,255,0) is green, and (0,0,255) is blue.
Many image processing tasks use information from neighbouring pixels. For this
assignment, you will be representing images and graphs, where each vertices
neighbours are adjacent pixels in the corresponding image of the same colour.
For example, look at the image below on the left depicting a house (with a blue door,
blue roof and chimney, and green frame). The middle image below depicts the same
image as a grid of pixels.
The image on the right shows the same image represented as a graph, with the
following properties:
1. each vertex in the graph corresponds to a pixel in the image
2. each vertex is connected to adjacent pixels of the SAME colour
5
Your task will be to implement the flood-fill algorithm found in many image
editors. To perform a flood fill, one chooses a colour and clicks a point in the
image. All pixels connected to the point clicked of the same colour are then
changed to the new colour.
This same process will be done using DFS and BFS traversals. When a point in
the image is clicked, all connected vertices will be changed to the same colour.
The only file you need to add code to is GraphAlgorithms.java.
It will likely be necessary to read through the PixelVertex.java and
PixelGraph.java files to understand how the graph has been set up, as well as
the operations available to you for each vertex (PixelVertex) in the graph.
You are not expected to understand the code in the A5Tester.java file, but for
those of you who are curious, feel free to experiment with it. Your solution must
work with the current version of the A5Tester.java file. A5Tester.java is executed
with the name of an image. For example, `java A5Tester house.png` opens up
the testing visualization program with the house image shown previously.
There are four other sample images provided for you. All of them are very small,
so if you want to animate the flood fills, you are able to without waiting too long.
Good luck!
