Why choose database will return the k-th smallest value

Assignment Help Computer Engineering

Reference no: EM1327916

You are interested in analyzing some hard to obtain data from two separate databases. Each database contains n numerical values - so there are 2n values total- and you may assume that no two values are the same. You'd like to determine the median of this set of 2n values, which we will define here to be the nth smallest value.

However, the only way you can access these values is through queries to the databases. In a single query you can specify a value k to one of the two databases and the choose database will return the k-th smallest value that it contains.

Since queries are expensive you would like to compute the median using as few queries as possible. Give an algorithm that fins the median value using at most O(logn) queries.

Reference no: EM1327916

Questions Cloud

Algorithm for computing a topological ordering of a dag : But assume that we're given an arbitrary graph that may or may not be a DAG. Extend the topological ordering algorithm so that given an input directed graph G it outputs one of two thing.

Regarding the employee safety : Should employers be responsible for employee safety while employees are working from home or working off site of the company building?

Drucker-s discussion of generic vs. exceptional issues : Using Drucker's discussion of generic vs. exceptional issues, how would you categorize/analyze the Katrina disaster.

Implement an enterprise resource planning system : Would implementing an enterprise resource planning system help streamline operations and achieve efficiencies between operating departments? What major concerns need to be addressed

Why choose database will return the k-th smallest value : as queries are expensive you would like to compute the median using as few queries as possible. Give an algorithm that fins the median value using at most O(logn) queries.

Prepare a forecast for five week moving average : Prepare a forecast for week 11 by using a five -week moving average.

Explain what policies and measures could health care use : Explain What policies and measures could health care administrators use to ensure security of the system and applications and privacy of patients' information and records

Evaluating future value of money : Pedro Gonzalez will spent $5,000 at the beginning of each year for next 9 years. The interest rate is 8 percent. What is the future value.

Why all projects include risk in their project planning : Managing Risk in Project Management and Why should all projects include risk in their project planning? What are some of the drawbacks if risks are not considered?

User Account

All Pages