Write algorithm to find median value using queries

Assignment Help Data Structure & Algorithms

Reference no: EM1371240

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. Ina single query, you can specify a value k to one of the two databases, and the chosen database will return the/(m 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 finds the median value using at most O(log n) queries.

Reference no: EM1371240

Questions Cloud

Compute calvin profit-maximizing output level : Compute Calvin's profit-maximizing output level. Compute the Calvin's economic profits at this activity level. Is this activity level sustainable in long run?

Knowledge about business management : how taking the QRB course will prepare you for future courses in economics, finance, accounting, and research.

Local public agencies were capital constrained : Suppose you are Chief Economist of the FCC. The Chairman has called you in to discuss a thorny issue. Two wireless broadcasters operate on adjacent frequencies.

Perfect competition-cost curves : When developing short-run cost curves, it is supposed that all firms in perfect competition have the same cost curves and they all make identical short-run profits or losses.

Write algorithm to find median value using queries : As queries are expensive, you would like to calculate median using as few queries as possible. Provide the algorithm which finds median value using at most O(log n) queries.

Effect of retained earnings on divisions of a company : When the company I work for earns a profit on a project by coming in under budget on expenses or by finishing before the project due date, would that be retained earnings?

Determining amount of profit and loss : Johnston production is the price taker which utilizes this cost structure in the short run:

Question related to mass customization : Question related to mass customization - What challenges would an organization face if it sought to rely on mass customization more

Model of perfect competition : Describe and discuss the model of perfect competition and adopting strategies to gain market power in the competitive industries.

User Account

All Pages