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
In-order Traversal – Left, Root, Right
Pre-order Traversal – Root, Left, Right
Post-order Traversal – Left, Right, Root
1.
Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex A.
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.
b) 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.
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.
b) What is the total weight along the Hamiltonian circuit?
3.
Consider the graph given above. Use Kruskal’s and Prim’s algorithms (for Prim start at J) to find the minimum spanning tree.
a) For each algorithm provide the edges in the order they were selected.
b) What is the total weight of the spanning tree?
4. Create the binary search tree representation of the following list: 22,8,41,34,5,20.
Then perform in-order traversal of the tree. What do you get?
5. Perform in-order, pre-order, and post-order traversal on the tree below. List out the sequence of values for each traversal.
6. Perform post-order traversal on this arithmetic expression tree. What is the resulting value?
7. 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?
a. (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
b. (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
c. (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
d. (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.
Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.
Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.
Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.
Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.
Read more