Transcript Proofs, Recursion and Analysis of Algorithms

Graphs and Trees
Mathematical Structures
for Computer Science
Chapter 5
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Graphs and Trees
Decision Trees



Section 5.3
DEFINITION: DECISION TREE A decision tree is a tree in which
the internal nodes represent actions, the arcs represent outcomes of an
action, and the leaves represent final outcomes.
The following figure represents the various possibilities for five coin
tosses under the constraint that two heads in a row do not occur.
Each internal node of the tree represents an action (a coin toss), and the
arcs to the children of internal nodes represent the outcomes of that
action (heads or tails). The leaves of the tree represent the final
outcomes, that is, the different ways that five tosses could occur.
Decision Trees
1
Searching

The binary search algorithm acts on a sorted list and distinguishes
between three possible outcomes of the comparison:



Section 5.3
x = L[i]: algorithm terminates, x has been found
x < L[i]: algorithm proceeds to the left half of the list
x > L[i]: algorithm proceeds to the right half of the list
Decision Trees
2
Lower Bounds on Searching





Section 5.3
The number of nodes at each level in a full binary tree follows a
geometric progression: 1 node at level 0, 21 nodes at level 1, 22
nodes at level 2, and so on.
1 + 2 + 22 + 23 ... 2d = 2d + 1  1
Any binary tree of depth d has at most 2d + 1  1 nodes.
Any binary tree with m nodes has depth log m.
THEOREM ON THE LOWER BOUND FOR SEARCHING Any
algorithm that solves the search problem for an n-element list by
comparing the target element x to the list items must do at least
└log n┘ + 1 comparisons in the worst case.
Since binary search does no more work than this required
minimum amount, binary search is an optimal algorithm in its
worst-case behavior.
Decision Trees
3
Binary Search Tree




Section 5.3
The binary search algorithm requires that data already be
sorted.
Arbitrary data can be organized into a structure called a
binary search tree, which can then be searched using a
different algorithm called, binary tree search.
To build a binary search tree, the first item of data is made
the root of the tree.
Successive items are inserted by comparing them to
existing nodes, beginning with the root. If the item is less
than a node, the next node tested is the left child; otherwise
it is the right child. When no child node exists, the new
item becomes the child.
Decision Trees
4
Binary Search Tree Example



Section 5.3
The data items 5, 8, 2, 12, 10, 14, 9 are to be organized into a binary
search tree.
A binary search tree, by the way it is constructed, has the property
that the value at each node is greater than all values in its left subtree
(the subtree rooted at its left child) and less than all values in its right
subtree.
A binary tree search compares item x with a succession of nodes,
beginning with the root. If x equals the node item, the algorithm
terminates; if x is less than the item, the left child is checked next; if x
is greater than the item, the right child is checked next. If no child
exists, the algorithm terminates because x is not on the list.
Decision Trees
5
Sorting




Section 5.3
Decision trees can also model algorithms that sort a list of items
by a sequence of comparisons between two items from the list.
The internal nodes of such a decision tree are labeled L[i]:L[j ]
to indicate a comparison of list item i to list item j.
The outcome of such a comparison is either L[i] < L[j ]
or L[i] > L[j ]. If L[i] < L[j ], the algorithm proceeds to the
comparison indicated at the left child of this node; if L[i] > L[j ],
the algorithm proceeds to the right child.
If no child exists, the algorithm terminates because the sorted
order has been determined.
Decision Trees
6
Sorting Example

Section 5.3
The figure below shows the decision tree for a sorting
algorithm acting on a list of three elements.
Decision Trees
7
Lower Bound on Sorting




A decision tree argument can also be used to establish a lower
bound on the worst-case number of comparisons required to sort
a list of n elements.
The leaves of such a tree represent the final outcomes, that is,
the various ordered arrangements of the n items.
There are n! such arrangements, so if p is the number of leaves
in the decision tree, then p ≤ n!. The worst case will equal the
depth of the tree.
But it is also true that if the tree has depth d, then p ≤ 2d:
d = log p  log n!

Section 5.3
THEOREM ON THE LOWER BOUND FOR SORTING
Any algorithm that sorts an n-element list by comparing pairs of
items from the list must do at least ┌log n!┐ comparisons in the
worst case.
Decision Trees
8