1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 1st December 2004), see www.w3.org" />
<link rel="stylesheet" href="../../c/exam.css" type="text/css" />
<title>A Sample Quiz Created with the Help of Algotutor</title>
</head>
<body>
<h1>A Sample Quiz Created with the Help of Algotutor</h1>
<hr />
<p>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.</p>
<hr />
<p>Figure 1: <img src="q61.png" alt="figure 1" /></p>
<p>Figure 2: <img src="q62.png" alt="figure 2" /></p>
<ol>
<li>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):
<ul>
<li>The status of node __ dose not change; __ becomes a back
edge;</li>
<li>The status of node __ changes from unseen to fringe, and
its value becomes __;</li>
<li>The parent of node __ changes __ to __, and its value
changes from __ to __;</li>
<li>... and so on</li>
</ul>
</li>
<li>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.</li>
<li>Figure 3 shows the snapshot of the execution of Prim's
algorithm for minimal spanning tree on <a href="q63.gr">a graph</a>
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</li>
<li>Please state what happens to each of its neighbors (except its
parent):
<ul>
<li>The status of node __ dose not change; __ becomes a back
edge;</li>
<li>The status of node __ changes from unseen to fringe, and
its value becomes __;</li>
<li>The parent of node __ changes __ to __, and its value
changes from __ to __;</li>
<li>... and so on</li>
</ul>
</li>
</ol>
<p>Figure 3: <img src="q63.png" alt="figure 3" /></p>
</body>
</html>
|
