# CSS 220 Module 8 In-Class Activity

**CSS 220 Module 8 In-Class Activity**

1.

Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex L. 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?

2.

Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex N. 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?

3.

Consider the graph given above. Use Prim’s and Kruskal’s algorithm to find the minimum spanning tree.

What is the total weight of the spanning trees?

List the weights of the selected edges separated by commas in the order of selection.

4. Use Prim’s and Kruskal’s algorithm to find the minimum spanning tree. Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

a. (d—f),(a—b),(d—c),(b—f),(d—e)

b. (a—b),(d—f),(d—c),(b—f),(d—e)

c. (a—b),(d—f),(b—f),(d—c),(d—e)

d. (d—f),(a—b),(b—f),(d—e),(d—c)

5. Sort this list (52,56,48,34,11,8,92,4) using linear sorting (bubble sort, insertion sort) and binary tree sort.

6. Using this binary tree write down the corresponding arithmetic expression with

a. in-order traversal

b. post-order traversal