Module 8 Assignment
CSS 220 Module 8 Homework
Kruskal’s algorithm – is a Minimum Spanning Tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.
Prim’s algorithm – The algorithm operates by building the Minimum Spanning Tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
Binary Tree Traversals
Inorder Traversal – Left, Root, Right
Preorder Traversal – Root, Left, Right
Postorder Traversal – Left, Right, Root
1.
Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex A.
 List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends.
 Calculate the weight of the circuit.
2.
Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex O.
 List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends.
 What is the total weight along the Hamiltonian circuit?
Consider the graph given above. Use Kruskal’s and Prim’s algorithms (for Prim start at J) to find the minimum spanning tree.
 For each algorithm provide the edges in the order they were selected.
 What is the total weight of the spanning tree?
 Create the binary search tree representation of the following list: 22,8,41,34,5,20.
Then perform inorder traversal of the tree. What do you get?
 Perform inorder, preorder, and postorder traversal on the tree below. List out the sequence of values for each traversal.
 Perform postorder traversal on this arithmetic expression tree. What is the resulting value?
 Consider the following graph:
Which one of the following can NOT be the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

 (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
 (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
 (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
 (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)