借助 algotutor 製作的小考範例

Algotutor 對於教師出考題也很有幫助。 教師可以用 gen_at_graph 產生一個很大的亂數圖檔, 在某個演算法進行到一半的時候, 詢問學生下一步會發生什麼事。 如果要用傳統手工的方式做這件事, 成本效益顯得太低。 以下的例子就是作者用 algotutor 所製作的小考考題的一部分。

圖一: 圖一

圖二: 圖二

  1. 圖一是 Dijkstra's algorithm for single source shortest path problem 進行到一半時的狀況。 接下來要將 L 從 Fringe 取出, 把它變成 visited。 請問 L 的每個鄰居 (除了它的 parent 之外) 會有何變化?
  2. 繼續進行, 又拍到圖二。 此時 H 剛從 fringe 變成 visited, 它的所有鄰居只剩下 I 還沒有處理, 而 heap 內容為: W 8, C 9, P 13, U 11, N 10, I 14, S 13, Q 11 共 8 個元素。 請描述處理 I 之後, graph 與 heap 各會發生什麼變化?
  3. 對 一個 graph 進行 Prim's algorithm 建立 minimal spanning tree。 從 G 出發; 進行到一半時拍到圖三。 此時的 heap 內容為: S 1, J 2, W 4, E 3, O 2, L 8, A 4, R 8, M 3, B 7 共 10 個元素。 現在即將從 fringe 當中取出 S, 將它變成 visited。 請畫出 「取出 S」 前後, heap 的內容, 並請標示出元素上升/下降的路徑。
  4. 請列出 S 每個 neighbor (除了它的 parent 之外) 的變化:

圖三: 圖三