A Sample Quiz Created with the Help of Algotutor

Algotutor is also useful for teachers to give quizzes. One can use gen_at_graph to randomly generate a large graph, and ask students what happens next given a snapshot of the execution of a certain algorithm. To do this manually just for a quiz would be prohibitively costly and impractical. The following example is part of a quiz that the author created using algotutor.

Figure 1: figure 1

Figure 2: figure 2

  1. Figure 1 shows a spapshot of the execution of Dijkstra's algorithm for single source shortest path problem. The next step is to remove L from the fringe nodes and make it visited. Please state what happens to each of its neighbors (except its parent):
  2. The above execution goes on and arrives at the snapshot shown in figure 2. At the time H has just been moved from fringe to visited. All of its neighbors except node I are processed. The heap now contains 8 elements: W 8, C 9, P 13, U 11, N 10, I 14, S 13, Q 11. Please describe what happens to the graph and to the heap after node I is processed.
  3. Figure 3 shows the snapshot of the execution of Prim's algorithm for minimal spanning tree on a graph starting from node G. At the time the heap contains 10 elements: S 1, J 2, W 4, E 3, O 2, L 8, A 4, R 8, M 3, B 7. The next step is to remove S from the fringe nodes and make it visited. Please draw the heap before and after the removal of S, and indicate the path of rize/fall of the involved elements. Please state what happens to each of its neighbors (except its
  4. Please state what happens to each of its neighbors (except its parent):

Figure 3: figure 3