Demonstrate prims algorithm starting from vertex a

Assignment Help Computer Engineering

Reference no: EM131137110

Question 1. Consider the weighted graph below:

(a) Demonstrate Prim's algorithm starting from vertex A. Write the edges in the order they were added to the minimum spanning tree.

(b) Demonstrate Dijkstra's algorithm on the graph, using vertex A as the source. Write the vertices in the order which they are marked and compute all distances at each step.

Question 2. Below is a list of courses and prerequisites for a factious CS degree.

Course	Prerequisite
CS 150	None
CS 151	CS 150
CS 221	CS 151
CS 222	CS 221
CS 325	CS 221
CS 351	CS 151
CS 370	CS 151
CS 375	CS 151, CS 222
CS 401	CS 375, CS 351, CS 325, CS 222
CS 425	CS 325, CS 222
MATH 200	None
MATH 201	MATH 200

(a) Draw a directed acyclic graph (DAG) that represents the precedence among the courses.

(b) Give a topological sort of the graph.

(d) Determine the length of the longest path in the DAG. How did you find it? What does this represent?

Question 3. Suppose you have an undirected graph G = (V,E) and you want to determine if you can assign two colors (blue and red) to the vertices such that adjacent vertices are different colors. This is the graph Two-Color problem. If the assignment of two colors is possible, then a 2-coloring is a function C: V -> {blue, red} such that C(u) ≠ C(v) for every edge (u,v) ∈ E. Note: a graph can have more than one 2- coloring.

Give an O(V + E) algorithm to determine the 2-coloring of a graph if one exists or terminate with the message that the graph is not Two-Colorable. Assume that the input graph G=(V,E) is represented using adjacency lists.

(a) Give a verbal description of the algorithm and provide detailed pseudocode.

(b) Analyze the running time.

Question 4. A region contains a number of towns connected by roads. Each road is labeled by the average number of minutes required for a fire engine to travel to it. Each intersection is labeled with a circle. Suppose that you work for a city that has decided to place a fire station at location G. (While this problem is small, you want to devise a method to solve much larger problems).

(a) What algorithm would you recommend be used to find the fastest route from the fire station to each of the intersections? Demonstrate how it would work on the example above if the fire station is placed at G. Show the resulting routes.

(b) Suppose one "optimal" location (maybe instead of G) must be selected for the fire station such that it minimizes the distance to the farthest intersection. Devise an algorithm to solve this problem given an arbitrary road map. Analyze the time complexity of your algorithm when there are f possible locations for the fire station (which must be at one of the intersections) and r possible roads.

Reference no: EM131137110

Questions Cloud

Perpetuating an individualist corporate culture : The value of teams is often described in the work product created by teams versus individuals. Using available research, how does team work differ from individual work, and how can the use of rewards enhance and promote teamwork, rather than perpetua..

What other diagnosis does the individual potentially : Does the individual presented in the video meet criteria for Borderline Personality Disorder? What aspects does she meet and which criteria does she not meet? What other diagnosis does the individual potentially meet criteria for (a personality di..

Evaluate the process using informal benchmarking : Describe in very general terms the as-is business process for applying for admission at your university. Collaborate with another student in your class and evaluate the process using informal benchmarking.

Identify the most appropriate bivariate statistical test : For this assessment, identify the most appropriate bivariate or multivariate statistical test or procedure from the first list below that you would use for each of the research situations and questions that follow, in the second list below.

Demonstrate prims algorithm starting from vertex a : Demonstrate Prim's algorithm starting from vertex A. Write the edges in the order they were added to the minimum spanning tree.

Determine the speed of the bullet before the impact : Knowing that the bullet becomes embedded in the bar and that the maximum angle of rotation of the bar in its subsequent motion is 45° clockwise determine the speed of the bullet before theimpact.

Write a short essay : It is difficult to make changes in one's life. - Do you agree with this statement? - Write a short essay with Introduction, content and conclusion.

Inventory to cover the cost of borrowed money : A typical manufacturing company pays __________ percent of the value of its inventory to cover the cost of borrowed money, warehouse space, materials handling, staff, lift-truck expenses, and fixed costs?

What is a potential diagnosis for melanie : What is a potential diagnosis for Melanie? What impact might Melanie's level of growth and development have on her response to life stressors? What are the priorities of care for Melanie at this time?

User Account

All Pages