We covered breadth-first search, depth-first search, topological sort (8.1) and started talking about Euler tours and trails (beginning of 8.2). Next week we will finish 8.2 and 8.3, possibly parts of 8.4
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
1. [Searching, 40pt] Look at the following maze (generated
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.
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.