Graph exercise instruction improvements

[ttaiv]

Current (English) instructions for all graph JSAV exercises

BFS and DFS Reproduce the behavior of the BFS/DFS algorithm for the graph below. Just click on the edges in the order that they will be traversed by the BFS/DFS algorithm. Start with Node A. If there is more than one node that could be visited next, choose the one that comes first in alphabetical order.

Prim (scaffolded-v2) Reproduce the behavior of Prim's Algorithm for the given graph below. Click on the appropriate edges to add them to the MST. Start with Node A. For each node, process its neighbors in alphabetic order. In case of similar weights add nodes alphabetically.

Dijkstra (research-v3) Simulate the behavior of Dijkstra’s Algorithm for the given graph below. Click on an edge (parent, node) to enqueue or update a node in the Priority Queue (PQ). Click Dequeue to remove the node from PQ, and to add a node to the spanning tree. Begin from node A. The table contains the known shortest distance from A to each node alongside its parent node.

Kruskal Reproduce the behavior of Kruskal's algorithm for the graph below. Just click on the appropriate edge in the graph to add it to the MST. In case of equal weights, select the edge whose nodes come first in alphabetical order.

Suggestions

• Because scaffolded Prim makes user do queue, update and dequeue operations just like Dijkstra (v3), the instructions should also mention those operations (just like Dijkstra does). Therefore Prim instructions should be very similar to Dijkstra's ones but they also need to mention the processing of neighbors in alphabetic order (but not twice as they now do.)
• In Dijkstra: "Click Dequeue to remove the node from PQ, and to add a node to the spanning tree" --> "Click Dequeue to remove the node from PQ, and to add the corresponding edge to the spanning tree.

Thoughts

• Dijkstra uses notation (parent, node) when mentioning edge. Could this be applied to other exercises too? Or maybe more generic notation edge (u, v)?
  • (u, v) notation is compatible with BFS/DFS exercise pseudocode. It would clarify that even though user clicks on edges, the algorithm visits nodes. Instructions could read for example "Click on the edges (u, v) in the order that nodes v are visited by the BFS/DFS algorithm.
  • If (u, v) notation would be used in BFS and DFS, should Prim/Dijkstra/Kruskal also use it or notation (parent, node)?
• Overall it would be great if notation across graph exercises was as consistent as possible.

Actions

Based on discussion summarized here #218 and Artturi's comment below.

• [x] Update all exercised to use notation edge (u, v).
• [x] Modify Dijkstra instructions: "Click Dequeue to remove the node from PQ, and to add a node to the spanning tree" --> "Click Dequeue to remove the node from PQ, and to add the corresponding edge to the spanning tree.
• [x] Update Prim instructions to be similar to Dijikstra's.
• [x] Refer to PQ elements with word "element".
• [x] "The table contains..." --> "The table at the bottom keeps track of..."
• [x] "Simulate the behavior of [graph algorithm name]" --> "Simulate the execution of [graph algorithm name]"

[atilante]

Discussion with Archie 13.6.2024

General

Remember to modify all language versions of the exercise translations at the same time. It is important that they are consistent.

Dijkstra-PQ

Archie would not like to have object-oriented programming terminology in the exercise. Let's keep the word "element" (Finnish: alkio) related to the priority queue element.

Be careful in English instructions: is the Finnish word "taulukko" in English "table" or "array"? Check the context, e.g. the exercise itself, related JSAV exercise, OpenDSA.

Use the expression "The table below" to refer the specific table.

(How to call the Node-Distance-Parent table? Proposals: solution table, solution matrix, result table, computing table? You may try one of these.)

"Simulate the behavior of Dijkstra's algorithm" -> "Run Dijkstra's algorithm" In Finnish: "Simuloi Dijkstran algoritmin suoritusta"

Prim-PQ

"The table below contains" -> "The table below keeps track of"

Finnish tutorial:

Itse simulaatiotehtävän jälkeen voisi olla huomautus: huomaa, että tehtävässä verkko on aina rakenteeltaan sellainen, että ratkaisu on poikkeuksellisesti yksikäsitteinen.