Solutions to exam 1 of 2002.
Question 1
Part (a)
Please see the
web tutorial
by Abeer Ghuneim.
I expected you to describe the starting condition, all possible motions
and the two stopping criteria.
Part (b)
You could have used the counterexample in the tutorial mentioned above.
I expected you to mark the starting position.
Question 2
Part (a)
See these
web notes .
I expected only a brief description.
Almost everyone got full marks here, as long as you explained that all
edges between vertices are considered, showed how the directed graph is
built, and mentioned finding the shortest path. Since all possible paths
are considered, the algorithm finds a path that is optimal.
Part (b)
Please see the solution to the first question of the
second assignment.
Question 3
Part (a)
Please see the
web tutorial
by Hang Fai Lau.
NOTE: this link is now broken. I will see if it can be restored. -greg-
Parts (b,c)
To find the distance from a pattern-pixel to a boundary pixel, you
compute the horizontal and vertical displacements and take the max.
Many of you did not compute this for all possible paths to the boundary.
It was not enough to do this only for purely horizontal or vertical paths.
The distance from each pixel to the boundary is given below, and pixels
that have been colored blue are part of the skeleton.