You work for a road construction company and your manager asks you to list all deadended...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You work for a road construction company and your manager asks you to list all deadended intersections in the city. You are given an undirected graph G, with vertices representing intersections, and edges representing roads in the city. You can assume that there are no vertices with 0 edges, i.e., all roads are connected. Dead ends are represented as vertices that have only one edge. a. Describe at a high level how you would determine which vertices are deadended. Your function should return a list of vertices, and the only parameter should be the graph G, with G.V as a list of vertices and G.E as a list of edges. (3 points) b. Provide the pseudocode for your function. (5 points) Your manager now wants you to find which roads (edges) lead to deadends, rather than just the intersections. Remember that the order of choosing edges from a vertex in a breadthfirst search is arbitrary. An edge leads to a deadend if a breadthfirst traversal beginning from a deadended intersection MUST traverse that edge in a deterministic order. For example: In the image to the right, intersections A and J are deadends. A breadthfirst search from A MUST traverse (A,B), then (B,C), and (C,D), in that exact order, so those will be roads that lead to deadends. Once we reach D, we can arbitrarily choose any of (D,E), (D,G), or (D,F), so those roads will not be marked as deadended. A breadthfirst search from J must traverse (J,I), so that road leads to a deadend. However, from point I, we can choose either of (I.H) or (I,K) to traverse, so these roads will not be marked as deadended. A (3 EM ol ol F H L ·K I J c. Write the pseudocode for an algorithm that, given a graph G, will return a list of edges that lead to deadends. You may use the function you wrote in part b) as a subprocedure. (7 points) d. Provide the bigO runtimes of part b) and c), and explain your answer. (10 points) You work for a road construction company and your manager asks you to list all deadended intersections in the city. You are given an undirected graph G, with vertices representing intersections, and edges representing roads in the city. You can assume that there are no vertices with 0 edges, i.e., all roads are connected. Dead ends are represented as vertices that have only one edge. a. Describe at a high level how you would determine which vertices are deadended. Your function should return a list of vertices, and the only parameter should be the graph G, with G.V as a list of vertices and G.E as a list of edges. (3 points) b. Provide the pseudocode for your function. (5 points) Your manager now wants you to find which roads (edges) lead to deadends, rather than just the intersections. Remember that the order of choosing edges from a vertex in a breadthfirst search is arbitrary. An edge leads to a deadend if a breadthfirst traversal beginning from a deadended intersection MUST traverse that edge in a deterministic order. For example: In the image to the right, intersections A and J are deadends. A breadthfirst search from A MUST traverse (A,B), then (B,C), and (C,D), in that exact order, so those will be roads that lead to deadends. Once we reach D, we can arbitrarily choose any of (D,E), (D,G), or (D,F), so those roads will not be marked as deadended. A breadthfirst search from J must traverse (J,I), so that road leads to a deadend. However, from point I, we can choose either of (I.H) or (I,K) to traverse, so these roads will not be marked as deadended. A (3 EM ol ol F H L ·K I J c. Write the pseudocode for an algorithm that, given a graph G, will return a list of edges that lead to deadends. You may use the function you wrote in part b) as a subprocedure. (7 points) d. Provide the bigO runtimes of part b) and c), and explain your answer. (10 points)
Expert Answer:
Answer rating: 100% (QA)
It appears that the image contains a question related to graph theory asking for algorithms to find deadend vertices and edges in an undirected graph ... View the full answer
Related Book For
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia
Posted Date:
Students also viewed these programming questions

Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...

Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...

Which of the following activity bases would best be used to allocate setup activity to products? a. Number of inspections b. Direct labor hours c. Direct machine hours d. Number of production runs

(a) Explain why in a gas of N molecules, the number of molecules having speeds in the finite interval u to u + u is N = N f uu + uf(u) du. (b) If u is small, then f (u) is approximately constant over...

Indicate whether data administration or database administration is typically responsible for each of the following functions: a. Managing the data repository b. Installing and upgrading the DBMS c....

Write a code to test a Gaussian pseudorandom number generator. If you do not have a canned generator available, write a generator based on the BoxMuller algorithm in Appendix I. Apply the following...

For the year ended December 31, 2010, Blasing Electrical Repair Company reports the following summary payroll data. Blasing Companys payroll taxes are: FICA 8%, state unemployment 2.5% (due to a...

Dr. Jose Rizals arrest, exile, trial, and eventual execution, primarily, was the result of his two books namely, Noli Me Tngere, and El Filibusterismo. However, his protagonist Crisostomo Ibarra,...

A textile company produces shirts and pants. Each shirt requires two square yards of cloth, and each pair of pants requires three square yards of cloth. During the next two months the following...

Introduction The students in the MGT 4109 project management class are planning a fundraising Easter dinner for their Faculty members. The event will take place on Saturday, April 8, 2023, and the...

Comparison Report Outline and Annotated References/Bibliography It is time to work on your formal research report. This assignment will be comprised of two parts. 1. Create a rough outline for your...

Part I: Answer the following questions 1. There are several strategies to persuade your audience. Discuss one strategy in detail and provide an example of how you could use this strategy to persuade...

A . Hearts had a net income of $ 4 7 5 , 0 0 0 . The company only uses cash dividends. B . Hearts bought $ 7 4 , 0 0 0 worth of investments and sold other investments for a gain of $ 8 , 3 0 0 . C ....

Convert the coordinate vector [x] from the given basis B to the standard basis. B = {[] []}, = [2] x=

As a Sr. Technical Writer, you have been tasked to train a team of communicators about how to utilize visual and textual elements in documentation effectively. Please include all the information in...

The estimating approach that is used under the condition of strategic decision making or high uncertainty is called?

Suppose you are comparing just two means. Among the possible statistics you could use is the difference in means, the MAD, or the max min (the difference between the largest mean and the smallest...

Professor Amongus has just designed an algorithm that can take any graph G with n vertices and determine in O(n k ) time whether G contains a clique of size k. Does Professor Amongus deserve the...

Give a pseudocode description of the mergesort algorithm assuming the input is given as a linked list.

how that the running time of the mergesort algorithm on an nelement sequence is O(n log n), even when n is not a power of 2.

A firm in Saudi Arabia uses capital and labor in its production process. The hourly cost of labor is SR30 and the initial rental rate of capital is SR60 per hour. What is the firm's isocost line? How...

Canada removed all duties and quotas on imports from Bangladesh in 2003. Since that time, Bangladesh has become the second largest source (after India) of Canadian merchandise imports from South...

A firm has the cost curve \(C(q)=100+150 q\) \(46 q^{2}+5 q^{3}\). What are the equations of the firm's marginal cost, average variable cost, and average cost curves? What are the minimum values of...
Study smarter with the SolutionInn App