CSS 220 Module 8 In-Class Activity

CSS 220 Module 8 In-Class Activity

 

Just $7 Welcome
Order Now

 

1. A picture containing text, air, colorful  Description automatically generated

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.

A picture containing text, air  Description automatically generated

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.

Chart  Description automatically generated

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