Design an algorithm that finds the median salary

Assignment Help Computer Engineering

Reference no: EM133217992

Question: You are interested in finding the median salary in Syracuse City. The city has two towns, Happyville and Sadtown. Each town maintains a database of all of the salaries for that particular town, but there is no central database. Each town has given you the ability to access their particular data by executing queries. For each query, you provide a particular database with a value k such that 1 ≤ k ≤ n, and the database returns to you the kth smallest salary in that town. You may assume the following:

• Each town has exactly n residents (so 2 × n total residents across both towns)

• Every salary is unique (i.e., no two residents, regardless of town, have the same salary)

• We define the median as the nth highest salary across both towns. (a) Design an algorithm that finds the median salary across both towns in θ(log(n)) total queries. (b) Prove that the algorithm finds the correct answer.

Reference no: EM133217992

Questions Cloud

Write a report on smart home automation system : Write a report on smart home automation system project with the capability of Internet of Things (IoT) applications incorporating different sensors

In what ways can each party leverage power to force : In what ways can each party leverage power to force a deal on favorable terms? Provide examples of power-based moves that each party could employ

Identify two to three features of pycharm : Identify two to three features of PyCharm that could make coding easier for programmers, and briefly explain why.

How do you think technology helps solve crimes : Coincidentally this revolution has led to a direct increase in solved crimes. How do you think technology helps solve crimes? Think about how technology

Design an algorithm that finds the median salary : Design an algorithm that finds the median salary across both towns in ?(log(n)) total queries. (b) Prove that the algorithm finds the correct answer.

Explain some advantages a business : Explain some advantages a business would get from utilizing cloud computing of the chosen model.

Write the command to display the contents : Write the command to display the contents of a file in your current directory called 'notes' so that you have forward and backward page control and the display

Creating a miniature established models : Embracing reasonable assumptions and zeroing in on creating miniature established models that are resistant to the Lucas investigate.

Explain the pros of LTD using external finance vs cash : Explain the pros of LTD using external finance vs. cash on hand in this venture. Provide four supporting examples

User Account

All Pages