Analyze the running time of lca

Assignment Help Data Structure & Algorithms
Reference no: EM131036661

Ancestor's algorithm

The least common ancestor of two nodes u and ν in a rooted tree T is the node w that is an ancestor of both u and ν and that has the greatest depth in T. In the off-line least-common-ancestors problem, we are given a rooted tree T and an arbitrary set P = {{u, ν}} of unordered pairs of nodes in T, and we wish to determine the least common ancestor of each pair in P. To solve the off-line least-common-ancestors problem, the following procedure performs a tree walk of T with the initial call LCA (T.root). We assume that each node is colored WHITE prior to the walk.

LCA(u)

1 MAKE-SET(u)
2 FIND-SET(u).ancestor = u
3 for each child ν of u in T
4 LCA(ν)
5 UNION(u, ν)
6 FIND-SET(u).ancestor D u
7 u.color = BLACK
8 for each node ν such that {u, ν } ∈P
9 if ν.color = = BLACK
10 print "The least common ancestor of"

u "and" ν "is" FIND-SET(ν).ancestor

a. Argue that line 10 executes exactly once for each pair {u,ν}∈P.

b. Argue that at the time of the call LCA(u), the number of sets in the disjoint-set data structure equals the depth of u in T .

c. Prove that LCA correctly prints the least common ancestor of u and ν for each pair {u, ν} ∈P.

d. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3.

Reference no: EM131036661

Questions Cloud

Find community program -focuses on addressing health issues : Identify one community based program (in Prince George's County, Maryland or Washington, D.C) that focuses on addressing health issues. The program will focus on behavior change, changing local environments for health, or developing new health pol..
Determine the mass fractions of the constituents of air : The composition of moist air is given on a molar basis to be 78 percent N2, 20 percent O2, and 2 percent water vapor.
Transactions demand for money : According to Baumol and Tobin, the transactions demand for money is
Business matters within the company : Mr. Smith is a retired director of XYZ Co Ltd, he was not appointed a director for the current year (2014), but still attends to many of the business matters within the company, and also attends the directors meetings to advise and mentor the new ..
Analyze the running time of lca : Prove that LCA correctly prints the least common ancestor of u and ν for each pair {u, ν} ∈P. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3.
Goals of the fed frequently conflict : 1. Unemployment us a bad thing, and the government should make every effort to eliminate it." Do you agree or disagree? Explain your answer. 2. Which goals of the Fed frequently conflict
Write comparative report on methodology all parties followed : Task: Read the ruling in both the Mittal Steel and SCI case and write a comparative report on the methodology all the parties followed in their assessment of excessive pricing. In your report specifically address the following: Factors assessed to..
Aggregate demand and real gross domestic product : the price level will drop.b. aggregate demand and real Gross Domestic Product (GDP) will not change.c. aggregate demand and real Gross Domestic Product (GDP) will increase by the amount of the spending increase.d. the government spending multiplie..
Why was that moment significant : After watching the video at http://www.youtube.com/watch?v=zT7TeryDzk0&feature=player_detailpage, consider how over time, the practice of psychology has become more widely accepted. What was one of the defining moments in the history of psycholog..

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Question 1nbsplist and describe the four steps in polyas

question 1nbsplist and describe the four steps in polyas how to solve it listquestion 2nbsplist the three phases of the

  Linear-time algorithm to find odd-length cycle in graph

Give a linear-time algorithm to find an odd-length cycle in a directed graph. You may not suppose that graph is strongly connected.

  Find values of n insertion sort beat merge sort

For inputs of size n, insertion sort runs in 8n 2 steps, where as merge sort runs in 64* nlog base 2 n steps. For which values of n odes insertion sort beat merge sort?

  Prove that there can be at most 13 distinct common entries

Tyrell-III has n replicants and each has a particular model specification. There are many models. Unfortunately, there was an insurgency on the planet and some of the replicants destroyed a critical database that held replicant data.

  Steps of asymmetric encryption algorithms to read message

Using only asymmetric encryption algorithms write down any steps taken by Bob which permit him to read the message.

  Propose an efficient data structure

Propose an efficient data structure that may hold the tour operator's data using a normalization process. Describe each step of the process that will enable you to have a 2nd Normal Form data structure.

  System analystis you are required to analyse the

you are required to analyse the effectiveness of the qantas online air ticketing system. to do this you are required to

  Write an algorithm, using pseudo code, "consensus algorithm"

Write an algorithm, using pseudo code, "Word Search": Given a string of letters, identify all substrings that create one of five given words.

  Draw one child diagram using the level 0 diagram

As a systems analyst or knowledgeable end-user, you must learn how to draw data flow diagrams to model business process requirements.

  Replace the letter n with the letter g and alter the pointer

Then how do I replace the letter N with the letter G and alter the pointers so that the new letter appears in the list in its proper place in alphabetical order?

  Implement the selection sort algorithm for sorting an array

Implement the Selection Sort algorithm for sorting an array of n elements. This algorithm has n-1 iterations, each selecting the next largest element a[j] and swapping it with the ele- ment that is in the position where a[j] should be.

  Writing the opeartors which contains the states

I want help with writing the opeartors which contains the states includiing its precondition and action for the eight queens problem. that is placing 8 pieces (the queens) on an 8 by 8 chess board. i want the code to be as basic and uncomplicated ..

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd