CSE310 HW06, Thursday, 04/22/2010, Due: Thursday, 04/29/2010Please note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version atthe digital drop box. For the electronic version, you should name your file using theformat HW06-LastName-FirstName.1. (5 pts) Assume that a hash table has 7 slots and the hash function is h(k) = k mod 7.Demonstrate the insertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into the hash table withcollisions resolved by chaining.Solution:The resulted hash table is:0 → 281 → 1523 → 10 → 1745 → 12 → 33 → 19 → 56 → 20Grading Keys:+0.5pts for each correct map;+0.5pts for correct chaining.2. (5 pts) Consider a hash table of size m = 100 and a corresponding hash function h(k) =bm(k A mod 1)c for A = 0.618. Compute the locations to which the keys 61, 62, 63, 64, 65 aremapped.Solution:161 → 6962 → 3163 → 9364 → 5565 → 17Grading Keys:1pt for each correct map.3. (10 pts) Write the adjacency list and the adjacency matrix of the graph in Figure 22.9(c) ofthe textbook.Solution:The adjacency list is as follows.abe : cd → fgcd : fg → hfg : hh :Grading Keys:1pt for each node;1 bonus pt for all correct nodes.The adjacency matrix is shown in figure 1.Figure 1: adjacency matrix2Grading Keys:1pt for each correct row;1 bonus pt for all correct rows.4. (10 pts) Let G be the graph in Figure 23.5(a) with the weights of edges (b, c) and (a, h)changed from 8 to 2. Compute an MST of G using Kruskal’s algorithm. Show the edgesselected into the tree in the correct order.Solution:The MST is show in figure 2. In figure 2, the MST is connected using dark edges.Figure 2: The MST computed using Kruskal’s algorithmThe order of the edges selected into the tree: hg, ah, bc, ci, gf, ab, cd, de.Grading Keys:1pt for each correct selection;2 bonus pts for all correct selections.5. (10 pts) Let G be the graph in Figure 23.5(a). Show the BFS tree obtained starting fromvertex a. Show the DFS tree obtained starting from vertex a, showing the discovery time andfinish time of each vertex.Solution:The obtained BFS tree is shown in figure 3.3Figure 3: The BFS treeThe obtained DFS tree associated with its discovery time and finish time of each vertex isshown in figure 4.Figure 4: The DFS treeGrading Keys:5pts for correct BFS tree;3pts for correct DFS tree;1pt for correct discovery time;1pt for correct finish time.6. (10 pts) Consider Figure 23.4(h) of the textbook. Is there an edge that is a light edge of everycut that respects the set of dark edges? If so, identify the edge. If not, explain why.Solution:No. There are three cuts in figure 23.4(h). They are ({a, b}, {c, d, e, f, g, h, i}), ({a, b, e },{c, d, f, g, h, i }) and ({a, b, c, d, f, g, h, i }, {e}). For cut ({a, b}, {c, d, e, f, g, h, i}), thelight edge is bc, whose weight is 8. For cut ({a, b, e }, {c, d, f, g, h, i }), the light edge is stillbc, and its weight is 8. However, for cut ({a, b, c, d, f, g, h, i }, {e}), the light edge is de witha weight of 9. Therefore, in figure 23.4(h), there is no edge that is a light edge of every cutthat respect the set of dark edges.4Grading Keys:6pts for correct answer;4pts for
View Full Document
Unlocking...