Consider the recursive algorithm in Figure 10.80 for finding the shortest weighted path in an acyclic graph,
Question:
a. Why does this algorithm not work for general graphs?
b. Prove that this algorithm terminates for acyclic graphs.
c. What is the worst-case running time of the algorithm?
Transcribed Image Text:
Distance shortest( s,t ) Distance di, tmp; if( s == t ) return 0; de 00; for each Vertex v adjacent to s { tmp = shortest (v, t ); if( Cs,y + tmp < d¿) di = Csy + tmp; } return d;; }
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 66% (9 reviews)
a If the graph has a cycle then the recursion does not alway...View the full answer
Answered By
Somshukla Chakraborty
I have a teaching experience of more than 4 years by now in diverse subjects like History,Geography,Political Science,Sociology,Business Enterprise,Economics,Environmental Management etc.I teach students from classes 9-12 and undergraduate students.I boards I handle are IB,IGCSE, state boards,ICSE, CBSE.I am passionate about teaching.Full satisfaction of the students is my main goal.
I have completed my graduation and master's in history from Jadavpur University Kolkata,India in 2012 and I have completed my B.Ed from the same University in 2013. I have taught in a reputed school of Kolkata (subjects-History,Geography,Civics,Political Science) from 2014-2016.I worked as a guest lecturer of history in a college of Kolkata for 2 years teaching students of 1st ,2nd and 3rd year. I taught Ancient and Modern Indian history there.I have taught in another school in Mohali,Punjab teaching students from classes 9-12.Presently I am working as an online tutor with concept tutors,Bangalore,India(Carve Niche Pvt.Ltd.) for the last 1year and also have been appointed as an online history tutor by Course Hero(California,U.S) and Vidyalai.com(Chennai,India).
4.00+
2+ Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Question Posted:
Students also viewed these Computer Sciences questions
-
Assume a packet is made only of four 16-bit words (A7A2) 16 , (CABF) 16 , (903A) 16 , and (A123) 16 . Manually simulate the algorithm in Figure 10.17 to find the checksum. Figure 10.17 Figure 10.17...
-
Describe a recursive algorithm for finding the maximum element in an array, A, of n elements. What is your running time and space usage?
-
Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in Figure 3.31. This is an idealization of the problem that a robot has to...
-
Doug Robinson and Dante are considering the possibility of opening their own manufacturing facility. They expect first-year sales to be $800,000, and they feel that their variable costs will be...
-
A rocket for use in deep space is to be capable of boosting a total load (payload plus rocket frame and engine) of 3.00 metric tons to a speed of 10 000 m/s. (a) It has an engine and fuel designed to...
-
Which of the following is not true concerning gift taxes? a. Gift taxes are not abolished, but a lifetime exclusion of $12.06 million is available in 2022. b. The Tax Cuts and Jobs Act of 2017 will...
-
Identify the six different discovery devices. What is the purpose of each device?
-
As the HR manager, you have heard rumors about potential efforts to unionize your warehouse employees. Use the www.genelevine .com website to develop a set of guidelines for supervisors if they are...
-
An Indonesian company is about to pay an international turnkey project with total payment of US Dollar 25 million and due six months from today. The current spot rate is IDR 14,000/$, and a forward...
-
Two particles are in a uniform electric field that points in the 1x direction and has a magnitude of 2500 N/C. The mass and charge of particle 1 are m1 = 1.4 x 10-5 kg and q1 = -7.0 C, while the...
-
In the game of chess, a knight in row R and column C may move to row 1 R' B and column 1 C' B (where B is the size of the board) provided that either |R - R'| = 2 and |C - C'| = 1 or |R - R'| =1...
-
Let A be an N-by-N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square. a. Design an O(N2) algorithm that determines the size of the largest submatrix...
-
Following is the adjusted trial balance, with accounts in alphabetical order, for TRN Magazine as at January 31, 2014: Required Prepare the closing entries. Debit Credit 21,000 Accounts receivable...
-
Malone Company makes and sells products with variable costs of $ 2 4 each. Malone incurs annual fixed costs of $ 4 2 8 , 4 0 0 . The current sales price is $ 8 7 . Note: The requirements of this...
-
Costs of $ 7 , 0 0 0 were incurred to acquire goods and make them ready for sale. The goods were shipped to the buyer ( FOB shipping point ) for a cost of $ 4 0 0 . Additional necessary costs of $ 8...
-
Salvia Company recently purchased a truck. The price negotiated with the dealer was $40,000. Salvia also paid sales tax of $2,000 on the purchase, shipping and preparation costs of $3,000, and...
-
A company reports the following beginning inventory and two purchases for the month of January. On January 26, the company sells 360 units. Ending inventory at January 31 totals 130 units. Units Unit...
-
Royal Cigar Company is preparing a budget for cash collections. Its sales for November and December are estimated as $175,000 and $202,000, respectively. Past practice indicates that sales in any...
-
Gabriel Industries stock has a beta of 1.12. The company just paid a dividend of $1.15, and the dividends are expected to grow at 4 percent. The expected return on the market is 11.4 percent, and...
-
What are three disadvantages of using the direct write-off method?
-
Assume (for simplicity in this exercise) that only one tuple fits in a block and memory holds at most 3 page frames. Show the runs created on each pass of the sort-merge algorithm, when applied to...
-
Let relations r1 (A, B, C) and r2 (C, D, E) have the following properties: r1 has 20,000 tuples, r2 has 45,000 tuples, 25 tuples of r1 fit on one block, and 30 tuples of r2 fit on one block. Estimate...
-
Design a variant of the hybrid mergejoin algorithm for the case where both relations are not physically sorted, but both have a sorted secondary index on the join attributes.
-
Calculate the hardness of water in units of mg/L of CaCO3 (see equation 15-7) if your titration at pH = 10 resulted in a concentration of 15 mmol/L. Round your answer to the nearest whole number and...
-
How do central banks' monetary policies, such as interest rate adjustments and reserve requirements, influence the deposit-taking behavior of commercial banks, and what are the broader implications...
-
On January 1, the first day of the fiscal year, a member of a nonprofit hospital's board of directors passed away. His will provided a $35,000 contribution to the hospital to upgrade the skills of...
Study smarter with the SolutionInn App