Determine the median of this set of 2n values

Assignment Help Computer Engineering

Reference no: EM132217517

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 chosen database will return the kth 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: EM132217517

Questions Cloud

Explain how risk management could contribute : Fundamentals of risk management - Describe benefits of achieving risk maturity in thé tisk management pracess in the merged insurance broker

Write a procedure that accepts two null terminated strings : Write a procedure that accepts 2 null terminated strings and returns 1 if they are equal or 0 otherwise.

Prepare the adjusting entries for the items : The unadjusted trial balance for Sierra Corp. is shown in Illustration 4-4. Instead of the adjusting entries shown in the text at October 31.

Determine the total cost and the average cost per mile : The cost per mile for a rented vehicle is $1.25 for the first 100 miles, $0.75 for the next 200 miles, and $0.70 for all miles in excess of 300 miles.

Determine the median of this set of 2n values : Determine the median of this set of 2n values, which we will define here to be the nth smallest value.

Create two use cases for the school bus system : The X School operates 40 buses that serve approximately 1,000 students in grades K-12. The bus operation involves 30 regular routes, plus special routes.

Write a class classroom that extends room : A Room class contains an int instance variable for the area (in square feet) of the room one constructor that takes the area of the room.

Design an algorithm for an xml document : An XML document is a plain text file containing opening and closing tags that semantically mark-up pieces of data. Further, tags can be nested as many levels.

Write a proram to take a sequence of numbers from the stack : Write a program to take a sequence of numbers from the stack. The most recent stack value will contain the number of digits to use.

User Account

All Pages