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:
![You work for a road construction company and your manager asks you to list all dead-ended intersections in](https://dsd5zvtm8ll6.cloudfront.net/questions/2023/11/656718713006c_1701345259231.jpg)
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
-
The defendant contracted with the plaintiff to design, maintain, and develop software and to host the defendant's web page. After a falling out, the defendant moved its web page to another site and...
-
Insert the missing word: Many people have argued the value of CRSA: Whats so good about control and risk self assessment? It forces managers and their staff to think very carefully about their . . ....
-
Economist Lester Thurow once posed the question, If you were the president of your own country and could specialize in one of two industries, computer chips or potato chips, which would you choose?...
-
Suppose Sparrow Sporting Goods Company reported the following data at March 31, 2012, with amounts in thousands: Use these data to prepare Sparrow Sporting Goods Company's income statement for the...
-
Environmental Landscaping Inc. is preparing its budget for the first quarter of 2020. The next step is to prepare a cash receipts schedule and a cash payments schedule. The following information has...
-
a. Answer (a) through (c) from Exercise 11.1 using the results in column (3). b. Sketch the predicted probabilities from the probit and linear probability in columns (1) and (3) as a function of...
-
A 20-year 10% annual coupon bond has a par value of $1,000.When you originally purchased this bond, the eective annual interest ratewas 8%. Suppose that ve years after purchase, the eective annual...
-
Encouraging you to sit back and watch a full hour of one of your favorite shows on prime-time television. However, instead of getting up during the commercial break or fast forwarding through the...
-
A family member has been recently diagnosed with a heart condition that requires replacing a heart valve. She points out that if she goes to India, the surgery cost is about 60% cheaper on average...
-
Based on the case of Bowers Machine Parts. Critically analyze why people were not doing their best and critically explain why hiring a consultant might solve the issue. Justify your answer by using...
-
Identify a few strategies for sustainability effectiveness. Should sustainability be a corporation's top priority? Why or why not? What are the challenges associated with implementing sustainable...
-
Answer the following questions for the topic you want to write about. Type your answers in a separate Word document. What is the issue or debatable idea you might write about? What is debatable about...
-
A perpetual inventory system gives a continuous record of the amount of inventory on hand. True False
-
Privitera and Freeman (2012) constructed a scale to measure or estimate the daily fat intake of participants; the scale was called the estimated daily intake scale for fat (EDIS-F). To validate the...
-
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.
-
Purchased debt instrument with impairment LO9, 11, 13, 14 On 1 January 2019, Biko Banking Ltd purchases a debt instrument with a 5-year term for its fair value of $1000 million (including...
-
Applying accounting theory LO6, 8, 13, 14 Tropical Tours Ltd needs to raise $500 000 to finance the acquisition of a new tour bus. It approached an investment bank that proposed the following...
-
Various financial assets and financial liabilities LO12, 13 Great Adventure Ltd has entered into a number of contracts that are financial instruments as follows. (a) On 1 July 2018, the company...
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App