1. [Searching, 40pt]  Look at the following maze (generated automatically)

• [5pt] Draw the graph corresponding to the maze; there should be one vertex for each fork, each dead end, the entrance and the exit (there will be less than twenty vertices overall).
• [15pt] Perform a depth-first search on the maze. (List the vertices in the order that they are visited.)
• [15pt] Perform a breadth-first search on the maze. (Show the details of how reached changes and the new distance calculated in each step.)
• [5pt] Why is there a unique solution to this maze?

Explain how to exchange the black and the white knights using legal knight's moves. A knight moves two squares in one direction (horizontally or vertically) and then one square in an orthogonal direction. There can never be more than one piece on a square.

Model this problem as a graph (what are the vertices and what are the edges) and show how to derive the solution in the graph model. Hint: the graph you want for the solution does not have 9 vertices and 12 edges.

b) [10pt] In this problem you want to start with an empty 3x3 chessboard. You put down a knight on the board and make a legal knight's move with it. Repeat this 6 times, that is you place an additional 6 knights on the board, moving each one once after it has been placed. (Two knights can never share a square.) If you modeled your solution in a) correctly, this will be easy. Explain your solution in the graph model.

3. [Topological Sort, 25pt] Here is a simplified version of the prerequisite structure of the graphics degree. GPH 213 and GPH 212 require GPH 211, GPH 338 requires GPH 213 and GPH 325. GPH 325 requires CSC 212, which requires CSC 211, which requires IT 130. GPH 339 requires GPH 325 and CSC 212. CSC 321 requires CSC 393 and MAT 140. CSC 393 requires CSC 212. MAT 220 requires MAT 141, which requires MAT 140. GPH 329 requires CSC 393 and MAT 220. GPH 375 requires GPH 329. GPH 372 requires GPH 329. GPH 395 requires GPH 338 and GPH 372.

• [5pt] Draw the dependency graph for the classes in the graphics degree.
• [15pt] Run topological sort on the graph and show the sorted output.
• [5pt] Find a longest path in the graph. What does it mean?

4. [Extra Credit]  Here is a memorization card trick: a magician gives 64 cards to an audience and asks them to arrange them in a 8 x 8 square, randomly putting the
cards face-up or face-down. The magician then adds another 17 = 8+8+1 cards
extending the 8 x 8 square to a 9 x 9 square. While he has turned around the audience can flip over a single card. When he turns back, the magician can quickly find the card that has been flipped. How does he do it? Hint: The solution is purely mathematical, no memorization skills are needed.

5. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.