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.