借助 algotutor 製作的小考範例

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

圖一:

圖二:

1. 圖一是 Dijkstra's algorithm for single source shortest path problem 進行到一半時的狀況。 接下來要將 L 從 Fringe 取出, 把它變成 visited。 請問 L 的每個鄰居 (除了它的 parent 之外) 會有何變化?
   • __ 的狀態不改變; ____ 成為一條 back edge;
   • __ 從 unseen 變成 fringe, value 成為 __;
   • __ 的 parent 從 __ 變成 __, value 從 __ 變成 __
   • ...
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 之外) 的變化:
   • __ 的狀態不改變; ____ 成為一條 back edge;
   • __ 從 unseen 變成 fringe, value 成為 __;
   • __ 的 parent 從 __ 變成 __, value 從 __ 變成 __
   • ... 等等

圖三: