Many important algorithms, especially those for sorting and searching, work by comparing items of their inputs. We can study the performance of such algorithms with a device called a decision tree.

**Decision Trees**

Many important algorithms, especially those for sorting and searching, work by comparing items of their inputs. We can study the performance of such algorithms with a device called a ** decision tree**. As an example, Figure 11.1 presents a decision tree of an algorithm for finding a minimum of three numbers. Each internal node of a binary decision tree represents a key comparison indicated in the node, e.g.,

a run is equal to the length of this path. Hence, the number of comparisons in the worst case is equal to the height of the algorithm’s decision tree.

** **The central idea behind this model lies in the observation that a tree with a given number of leaves, which is dictated by the number of possible outcomes, has to be tall enough to have that many leaves. Specifically, it is not difficult to prove that for any binary tree with

Indeed, a binary tree of height ** h** with the largest number of leaves has all its leaves on the last level (why?). Hence, the largest number of leaves in such a tree is 2

Inequality (11.1) puts a lower bound on the heights of binary decision trees and hence the worst-case number of comparisons made by any comparison-based algorithm for the problem in question. Such a bound is called the ** information-theoretic lower bound **(see Section 11.1). We illustrate this technique below on

**Decision Trees for Sorting**

Most sorting algorithms are comparison based, i.e., they work by comparing elements in a list to be sorted. By studying properties of decision trees for such algorithms, we can derive important lower bounds on their time efficiencies.

We can interpret an outcome of a sorting algorithm as finding a permutation of the element indices of an input list that puts the list’s elements in ascending order. Consider, as an example, a three-element list ** a, b, c** of orderable items such as real numbers or strings. For the outcome

Inequality (11.1) implies that the height of a binary decision tree for any comparison-based sorting algorithm and hence the worst-case number of com-parisons made by such an algorithm cannot be less than | log2 ** n**! |:

In other words, about ** n** log2

We can also use decision trees for analyzing the average-case efficiencies of comparison-based sorting algorithms. We can compute the average number of comparisons for a particular algorithm as the average depth of its decision tree’s leaves, i.e., as the average path length from the root to the leaves. For example, for

the three-element insertion sort whose decision tree is given in Figure 11.3, this

number is ** (**2 + 3 + 3 + 2 + 3 + 3

Under the standard assumption that all ** n**! outcomes of sorting are equally likely, the following lower bound on the average number of comparisons

As we saw earlier, this lower bound is about ** n** log2

**Decision Trees for Searching a Sorted Array**

In this section, we shall see how decision trees can be used for establishing lower bounds on the number of key comparisons in searching a sorted array of ** n** keys:

We will use decision trees to determine whether this is the smallest possible number of comparisons.

Since we are dealing here with three-way comparisons in which search key ** K** is compared with some element

We can represent any algorithm for searching a sorted array by three-way comparisons with a ternary decision tree similar to that in Figure 11.4. For an array of ** n** elements, all such decision trees will have 2

This lower bound is smaller than log2** (n** + 1

As comparison of the decision trees in Figures 11.4 and 11.5 illustrates, the binary decision tree is simply the ternary decision tree with all the middle subtrees eliminated. Applying inequality (11.1) to such binary decision trees immediately yields

This inequality closes the gap between the lower bound and the number of worst-case comparisons made by binary search, which is also log2** (n** + 1

**Exercises 11.2**

** **Prove by mathematical induction that

** **** h **≥

** **** h **≥

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

** **What is the information-theoretic lower bound for comparison-based al-gorithms solving this problem?

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

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

** **Draw a decision tree and find the number of key comparisons in the worst and average cases for

** **the three-element basic bubble sort.

** **the three-element enhanced bubble sort (which stops if no swaps have been made on its last pass).

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

** **Design a comparison-based algorithm for sorting a five-element array with seven comparisons in the worst case.

** **Draw a binary decision tree for searching a four-element sorted list by sequen-tial search.

** **Compare the two lower bounds for searching a sorted array— log3** (**2

** **log3** (**2

** **log3** (**2

** **What is the information-theoretic lower bound for finding the maximum of ** n** numbers by comparison-based algorithms? Is this bound tight?

** **A ** tournament tree** is a complete binary tree reflecting results of a “knockout tournament”: its leaves represent

** **What is the total number of games played in such a tournament?

** **How many rounds are there in such a tournament?

** **Design an efficient algorithm to determine the second-best player using the information produced by the tournament. How many extra games does your algorithm require?

*Advanced fake-coin problem *There are* **n** *≥* *3 coins identical in appearance;* *either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a balance scale with which you can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other, but not by how much. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones.

** **Prove that any algorithm for this problem must make at least log3** (**2

** **Draw a decision tree for an algorithm that solves the problem for ** n** = 3 coins in two weighings.

** **Prove that there exists no algorithm that solves the problem for ** n** = 4 coins in two weighings.

** **Draw a decision tree for an algorithm that solves the problem for ** n** = 4 coins in two weighings by using an extra coin known to be genuine.

** **Draw a decision tree for an algorithm that solves the classic version of the problem—that for ** n** = 12 coins in three weighings (with no extra coins being used).

*Jigsaw puzzle *A jigsaw puzzle contains* **n** *pieces. A “section” of the puzzle is* *a set of one or more pieces that have been connected to each other. A “move” consists of connecting two sections. What algorithm will minimize the number of moves required to complete the puzzle?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Limitations of Algorithm Power : Decision Trees algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.