Question: By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each

By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of the weights of all the nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let N be the number of nodes in the tree, and let M be the number of accesses. Prove the following two theorems:
a. The total access time is O(M + (M + N) logN).
b. If qi is the number of times that item i is accessed, and qi > 0 for all i, then the total access time is

0M+E log(M/q) i=1

Step by Step Solution

★★★★★

3.47 Rating (180 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

a Choose W i 1 N for each item Then for any access of node X R f X 0 and R i X log N so th... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Document Format (1 attachment)

1486-C-S-A(567).docx

120 KBs Word File

Students Have Also Explored These Related Algorithms Questions!

Show that it is possible to ensure that a dependency-preserving decomposition into 3NF is a loss less-join decomposition by guaranteeing that at least one schema contains a candidate key for the...

In some systems it is possible to map part of a file into memory. What restrictions must such systems impose? How is this partial mapping implemented?

Assuming it is possible to sort n numbers in O(nlogn) time, show that it is possible to solve the three-way set disjointness problem in O(nlogn) time.

Describe, in detail, how the heapsort algorithm works. [10 marks] Show that the worst-case cost of heapsort is O(n log n). [6 marks] Would it be possible to implement a variant of heapsort based on a...

Give the typing rules for Peano natural numbers and their eliminator.(ii) Using the rules given above, define the addition function.] (iii) Let a binary tree be either a leaf Leaf or a node...

dee complete please help Complexity Theory (a) Defifine the set of Boolean expressions 2CNF and the language 2SAT over them. (b) For a Boolean expression in 2CNF, let G() be the directed graph with...

ANSI-SPARC6 Programming Language Compilation Write notes on each of the following topics: (a) the implementation of labels and jumps in a recursive, block structured programming language [7 marks]...

This question concerns lexical grammars. (a) Tree Adjoining Grammars contain two types of elementary tree. (i) What are these trees called? [1 mark] (ii) If one were building a grammar for English...

nodes, but at least its bias can be quantified by Markov Chain L. INTRODUCTION analysis and thus can be corrected via appropriate re-weighting The popularity of online social networks (OSNs) in...

an operation that yields a N aN value when neither of its arguments is a N aN, (b) an operation with finite arguments that yields +, (c) an operation with an argument + that yields a finite result....

5 Difference between 9th rib and 3rd rib.

a) Explain the term Corporate Governance from a banking industry perspective. b) Explain three determinants of weak corporate governance that could lead to the insolvency of banks in Africa. c)...

The vehicle speeds at a particular interstate location can be described by a normal curve. The mean speed is 67 mph, and the standard deviation is 6 mph. What is the proportion of vehicle speeds at...

Consider the following dating game, which has two players, A and B, and two strategies, to buy a movie ticket or a baseball ticket. The payoffs, given in points, are as shown in the matrix below....

Consider the following graph-based locking protocol, which allows only exclusive lock modes, and which operates on data graphs that are in the form of a rooted directed acyclic graph. A transaction...

Consider the following graph-based locking protocol that allows only exclusive lock modes, and that operates on data graphs that are in the form of a rooted directed acyclic graph. A transaction can...

Consider a variant of the tree protocol called the forest protocol. The database is organized as a forest of rooted trees. Each transaction Ti must follow the following rules: The first lock in each...

1. Suppose that the probability of having an accident-free day at a power plant is 60%. Assume all days are independent of each other. The plant manager wants to determine the likelihood of various...

Miyagi Data, Inc., sells earnings forecasts for Japanese securities. Its credit terms are 3/30, net 60. Based on experience, 60 percent of all customers will take the discount. (Enter your answer as...

The Riddler is a column on the website https://fivethirtyeight.com that posts logic, math, and probability puzzles each week. Some of puzzles can be attacked by simulation and discrete probability:...