CSE310 HW06 Thursday 04 22 2010 Due Thursday 04 29 2010 Please note that you have to typeset your assignment using either LATEX or Microsoft Word Hand written assignment will not be graded You need to submit a hardcopy before the lecture on the due date You also need to submit an electronic version at the digital drop box For the electronic version you should name your file using the format 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 with collisions resolved by chaining Solution The resulted hash table is 0 28 1 15 2 3 10 17 4 5 12 33 19 5 6 20 Grading 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 are mapped Solution 1 61 69 62 31 63 93 64 55 65 17 Grading 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 of the textbook Solution The adjacency list is as follows abe cd f g cd f g h fg h h Grading Keys 1pt for each node 1 bonus pt for all correct nodes The adjacency matrix is shown in figure 1 Figure 1 adjacency matrix 2 Grading 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 edges selected 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 algorithm The 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 from vertex a Show the DFS tree obtained starting from vertex a showing the discovery time and finish time of each vertex Solution The obtained BFS tree is shown in figure 3 3 Figure 3 The BFS tree The obtained DFS tree associated with its discovery time and finish time of each vertex is shown in figure 4 Figure 4 The DFS tree Grading 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 every cut 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 the light edge is bc whose weight is 8 For cut a b e c d f g h i the light edge is still bc and its weight is 8 However for cut a b c d f g h i e the light edge is de with a weight of 9 Therefore in figure 23 4 h there is no edge that is a light edge of every cut that respect the set of dark edges 4 Grading Keys 6pts for correct answer 4pts for explanation 5
View Full Document
Unlocking...