# CSS 220 Module 8 Homework

**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)