Draw a decision tree for an algorithm solving this problem

Assignment Help Basic Computer Science

Reference no: EM131252793

Consider the problem of finding the median of a three-element set {a, b, c} of orderable items.

a. What is the information-theoretic lower bound for comparison-based algorithms solving this problem?

b. Draw a decision tree for an algorithm solving this problem.

c. If the worst-case number of comparisons in your algorithm is greater than the information-theoretic lower bound, do you think an algorithm matching the lower bound exists? (Either find such an algorithm or prove its impossibility.)

Reference no: EM131252793

Questions Cloud

Common law contract principles : Please discuss the questions below using common law contract principles.

Discuss rhetorical components : What is the text trying to say--its main point or thesis? Audience: who has the text been created for?

Discuss your career goals as a healthcare administrator : Discuss your career goals as a Healthcare Administrator following the completion of your master's degree. When conducting this research, consider selecting articles that support.

Prove or give a counter example to the claim : Either prove or give a counter example to the claim that if the equilibrium payoff of player 1 in a strictly competitive game is v then any strategy pair that gives player 1 a payoff of v is an equilibrium.

Draw a decision tree for an algorithm solving this problem : What is the information-theoretic lower bound for comparison-based algorithms solving this problem?

What are the requirements to take the credentialing exam : What are the requirements to take the credentialing exam? What is the current cost and schedule for the exam? Would you take the exam to obtain the Certified Health Education Specialist credential? Why or why not

Examples of fostering goodwill : Is it important for managers to "foster goodwill"? Why or Why not? What are 2 examples of fostering goodwill in the workplace as a business manager? Is it possible for goodwill to hinder the image of a company?

Design a comparison-based algorithm for sorting array : Design a comparison-based algorithm for sorting a four-element array with the smallest number of element comparisons possible.

Why is it important that the problem be addressed : Outline the context of the problem or challenge, including the history and any policy decisions that have contributed to the situation. Why is it important that the problem be addressed? Who is impacted internally and externally?

User Account

All Pages