Analyze the time-space complexity of algorithms

Assignment Help Data Structure & Algorithms
Reference no: EM1373332

1. Early printings of CLRS3 say on pages 546-547 "we treat min and max differently: the element stored in min does not appear in any of the clusters, but the element stored in max does." This is not true (they may have corrected it in later printings)-what that sentence should say is "we treat min and max differently: the element stored in min does not appear in any of the clusters, but unless the vEB tree contains just one element (so that the minimum and maximum elements are the same), the element stored in max does." Rewrite the code for vEB-Empty-Tree-Insert, vEB-Tree-Insert, and vEB- Tree-Delete so that indeed, max does not appear in any of the clusters, just as min does not appear in any of the clusters.

2. Problem 20-1, parts (a) and (b) only, on page 557. In part (b), be careful that you do not get snagged by the pitfall described in the middle of page 86 of CLRS3. (Hint : For part (b), can you prove, under reasonable assumptions, that P(u) = u - 2?) Do not do parts (c)-(g); instead, do the following replacement for part (c):

(c) We can store all of the array-of-pointers substructures in a single array outside the vEB tree itself. This would change the recurrence (20.5) to

P(u) = (√u + 1)P(√u) + O(1).

Solve this recurrence. Does this idea improve the vEB structure?

3. Consider the "dynamic range minimum query problem." Let S ⊆ U = {0, 1, 2, . . . , u-1}. Each s ∈ S is labeled with a real number v(s). We need to maintain a data structure on S that supports the following operations:

• initialize(S): Construct and initialize the data structure for S.
• decreaseKey(s, x): If x < v(s), change v(s) to x; otherwise, do nothing.
• minimum(x): Return min{v(s)|s ∈ S, s ≤ x}.

Show how a vEB tree can be used to support these three operations. Analyze the time/space complexity of your algorithms.

Reference no: EM1373332

Questions Cloud

Elucidate what is the minimum price the product could have : Elucidate what is the minimum price the product could have been sold for to cover the unit cost, period expenses also overhead.
Describe how many pounds of every seed should be in blend : If the blend needs to score at least 300 points for shade tolerance, 400 points for traffic resistance also 750 points for drought resistance, describe how many pounds of every seed should be in the blend. Describe how much will the blend cost.
Concepts in macroeconomics : As an worker of the World Bank you have been asked to research requires of a country with a particular economic concern.
Compute the value of the price index for gdp : Compute the value of the price index for GDP for 2006 using 2005 as base year. By what percent did prices rise?
Analyze the time-space complexity of algorithms : How a vEB tree can be used to support these three operations and analyze the time/space complexity of your algorithms.
Elucidate what volume of demand would manager have : Elucidate what volume of demand would the manager be indifferent between the 2 cities Which city should be chosen if demand is higher than this volume.
Which strategic alternatives emerge from situation analysis : Which strategic alternatives emerge from situation analysis. Which level of decision making would you target in your report-corporate, business or functional? It's for Integrative Business Strategy class.
Computing the growth rate of real gdp : Suppose past year's real GDP was $7,000 billion, this year nominal GDP is $8,820 billion, and GDP deflator for this year is 120. Determine the growth rate of real GDP? Does this demonstrate an improvement in economic welfare?
Elucidate what should be the optimal batch size : Elucidate what should be the optimal batch size (Q) of clay tigers to be produced also shipped to the stores in every order. Keep 4 digits after decimal points in calculations.

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

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