You work for a road construction company and your manager asks you to list all dead-ended...
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 dead-ended 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 dead-ended. 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 dead-ends, rather than just the intersections. Remember that the order of choosing edges from a vertex in a breadth-first search is arbitrary. An edge leads to a dead-end if a breadth-first traversal beginning from a dead-ended intersection MUST traverse that edge in a deterministic order. For example: In the image to the right, intersections A and J are dead-ends. A breadth-first 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 dead-ends. 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 dead-ended. A breadth-first search from J must traverse (J,I), so that road leads to a dead-end. However, from point I, we can choose either of (I.H) or (I,K) to traverse, so these roads will not be marked as dead-ended. 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 dead-ends. You may use the function you wrote in part b) as a sub-procedure. (7 points) d. Provide the big-O 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 dead-ended 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 dead-ended. 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 dead-ends, rather than just the intersections. Remember that the order of choosing edges from a vertex in a breadth-first search is arbitrary. An edge leads to a dead-end if a breadth-first traversal beginning from a dead-ended intersection MUST traverse that edge in a deterministic order. For example: In the image to the right, intersections A and J are dead-ends. A breadth-first 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 dead-ends. 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 dead-ended. A breadth-first search from J must traverse (J,I), so that road leads to a dead-end. However, from point I, we can choose either of (I.H) or (I,K) to traverse, so these roads will not be marked as dead-ended. 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 dead-ends. You may use the function you wrote in part b) as a sub-procedure. (7 points) d. Provide the big-O 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
-
Starting from rest, a 5 . 5 kg block slides 3.2 m down a rough 2 3 . 0 degree incline in 3 . 0 s . The acceleration of gravity is 9 . 8 1 m / s ^ 2 a ) Find the work done by the force of gravity....
-
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
-
If the price level were below PE in Figure 11.5, what macro problems would we observe? Why is PE considered an equilibrium?
-
You are a US Citizen employed by Hot Feet a US shoe manufacturer. You are the CFO for its subsidiary in Sri Lanka you have lived there for twenty years. A major part of your satisfactionis derived...
-
What pleading is used to commence a lawsuit?
-
Build a House of Quality (showing only the Voice of the customer, Technical features, Interrelationships, and Relationship matrix from Exhibit 6.2) for designing and producing chocolate chip cookies....
-
The going rate on your student loan is 8% annual percentage rate (APR), why is your effective annual rate on your loan always larger than 8%? Please explain why you might prefer effective annual rate...
-
SAE specifications call for the low-side R-134a servicehose to be A) Solid blue with a black stripe B) Solid blue with no stripe C) Solid blue with a yellow stripe D) Solid black with a blue stripe...
-
Here are comparative balance sheets for Whispering Company. Prepare a statement of cash flows-indirect method. WHISPERING COMPANY Comparative Balance Sheets December 31 K Assets 2020 2019 Cash...
-
When is the indirect strategy appropriate, and what are the benefits of using it?
-
Valuable insider information about a companys culture, interview procedures, and day-to-day activities is available for those who take the time to search. Enterprising job seekers check YouTube...
-
James Howe, _____________ of _____________ will give a keynote address at our shareholder meeting in the spring. a. the president/Kendrick, inc., b. the President/Kendrick, inc., c. the...
-
Sugar-filled soft-drink sales have been declining for nine straight years, however diet drinks are not far behind. Your Task. Identify the sentence fault (fragment, run-on sentence, comma splice)....
-
The _____________ of three companies met at _____________ favorite restaurant in Hollywood. a. principals, theyre b. principles, there c. principals, their For the above sentence, write the correct...
-
The curve of the functions f(x) = x + Bx-12x+7 passes through (1, 0) and has a stationary value at (-2, 27). (a) Show that ?=2 and B=3. (b) Find the other turning point. (c) Determine the other point...
-
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 merge-sort algorithm assuming the input is given as a linked list.
-
how that the running time of the merge-sort algorithm on an n-element sequence is O(n log n), even when n is not a power of 2.
-
How do you allocate requirements?
-
How do you flow down requirements?
-
What is requirements flow down?
Advanced Strategies Taking Your Trading To The Next Level 1st Edition - ISBN: B0BZF576B3 - Free Book
Study smarter with the SolutionInn App