Write algorithm to calculate the median using queries

Assignment Help Data Structure & Algorithms

Reference no: EM1368930

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 in all - and you can 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 as the n-th 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 databases, and the chosen database will return the k-th smallest value that it contains. Since queries are expensive, you would like to calculate the median using as few queries as possible. Provide an algorithm which determines the median value using at most O(lg n) queries.

Reference no: EM1368930

Questions Cloud

Find the speed of the moving charge : Two identical 30 {rm g} particles each carry 3 {rm mu C} of charge. One is held fixed, and the other is located 1 {rm mm} away and released. Find the speed of the moving charge when it's 1{rm cm} from the fixed charge.

Explain new technologies or material changes : Explain new technologies or material changes that transform businesses' or companies' expectations and the way they interact

Considerations for training development : Considerations for Training Development - Show the process through which training needs identified in the analysis phase are translated into the training objectives.

What is the goal of employee development : What is the relationship between employee training and employee development and are both necessary within an organization

Write algorithm to calculate the median using queries : Calculate the median using as few queries as possible. Provide an algorithm which determines the median value using at most O(lg n) queries.

Determine the constant velocity of car : Two cars cover the same distance in a straight line. Car A covers the distance at a constant velocity. Car B starts from rest and maintains a constant acceleration. Both cars cover a distance of 547m in 221s.

Describe how you think a biographer causes of the event : Describe how you think a biographer, historian, or social scientist would describe the causes and consequences of the event

What is the linear charge density along the arc : A wooden raft has a mass of 59 kg. When empty it floats in water (density 1000 kg/m3) with 59 percent of its volume submerged. What mass of sand can be put on raft without it sinking.

Analyzing competitive markets : In a speech, Professor Gregory Mankiw contends that our elected federal leaders should raise the gasoline tax. Not quickly, but substantially.

User Account

All Pages