Estimating the comparison-based algorithm

Assignment Help Basic Computer Science

Reference no: EM13968262

1. Suppose you have an array of N elements containing only two distinct keys, true and false. Give anO(N) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.

2. Suppose you have an array of N elements, containing three distinct keys, true, false, and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may use only constant extra space.

3. a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons.

b. Give an algorithm to sort 4 elements in 5 comparisons.

Reference no: EM13968262

Questions Cloud

Cost is irrelevant to the aggregate production plan : Which one of the following cost is irrelevant to the aggregate production plan?

Convey to her superiors using all of the proper channels : Lisha is an engineer at a robotics lab who has discovered that the CEO of her company has been embezzling money from the company for years. She had sufficient evidence of the crime, which she tried to convey to her superiors using all of the proper c..

Optimized version of quicksort : 1. Implement an optimized version of quicksort and experiment with combinations of the following: a. pivot: ?rst element, middle element, random element, median of three, median of ?ve

How are fictional scientists viewed in the media : Influences of the Media- How are fictional scientists viewed in the media? Give 2 examples of either heroes or villains and How is science viewed in the fictional media

Estimating the comparison-based algorithm : a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons. b. Give an algorithm to sort 4 elements in 5 comparisons.

What would you advise her in evaluating the service package : Joan is the operations manager at Dark Light Communications, a services company. She has been told that the Operations function needs to pay more attention to the "service package" in order to be able to support the competitive priorities of the busi..

Ethical behavior and social responsibility to their behavior : Discuss specific activities where Operations Managers can apply ethical behavior and social responsibility to their behavior. Use examples from the course materials to expand your analysis.

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..

User Account

All Pages