Determining the comparison-based algorithms

Assignment Help Basic Computer Science

Reference no: EM13968255

1. Suppose we want to partition N items into G equal-sized groups of size N/G, such that the smallestN/G items are in group 1, the next smallest N/G items are in group 2, and so on. The groups themselves do not have to be sorted. For simplicity, you may assume that N and G are powers of two.

a. Give an O(N log G) algorithm to solve this problem.

b. Prove an 0.(N log G) lower bound to solve this problem using comparison-based algorithms.

2. Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.

3. Suppose arrays A and B are both sorted and both contain N elements. Give an O(log N) algorithm to ?nd the median of A ∪ B.

Reference no: EM13968255

Questions Cloud

Disadvantages of this capacity change to the supply chain : Jill has heard that in order to improve the reliability of her supply chain that she should add a capacity cushion. But, exactly what is a capacity cushion and why would a manufacturing company desire to have a large one? Discuss the advantages and d..

Development program encompassing eight research projects : The Texas Consolidated Electronics Company is contemplating a research and development program encompassing eight research projects. The company is constrained from embarking on all projects by the number of available management scientists (40) and t..

Discuss ethical principles under which the organization work : Discuss the mission, vision, and ethics policy of this corporation. What led you to select it? Discuss the ethical principles under which the organization works.

If they have people with good problem solving skills : What you feel an organization can do to make sure that people they hire are both in control and capable of doing the job? Companies are only good problem solvers if they have people with good problem solving skills. Do you feel you are a good problem..

Determining the comparison-based algorithms : a. Give an O(N log G) algorithm to solve this problem. b. Prove an 0.(N log G) lower bound to solve this problem using comparison-based algorithms.

Decisions differ for service facilities-manufacturing plants : How do facility location decisions differ for service facilities and manufacturing plants? How does the factor-rating system help supply chain managers? What is the purpose of using the transportation method of linear programming

What are the different types of demand : What are the different types of demand? What is the difference between different types of both qualitative and quantitative forecasting methods? How do yu describe a series analysis? How to apply simply moving average, weighted moving average, and li..

Briefly discuss the topic you have decided to explore : You should briefly discuss the topic you have decided to explore. Explain what is involved in this topic. Define clearly the framework.

Relationship between country foreign direct investments : Relationship between country foreign direct investments, and a country’s balance of payments. Are some FDI initiatives better than others at helping a country’s BOP accounts? Explain.

User Account

All Pages