1. Computing a Median and the Selection Problem
2. Interpolation Search
3. Searching and Insertion in a Binary Search Tree
4. The Game of Nim
5. Exercises

**Variable-Size-Decrease
Algorithms**

**1. Computing a Median and the Selection Problem**

**2. Interpolation Search**

**3. Searching and Insertion in a Binary Search Tree**

**4. The Game of Nim**

**5. Exercises**

In the
third principal variety of decrease-and-conquer, the size reduction pattern
varies from one iteration of the algorithm to another. Euclid’s algorithm for
computing the greatest common divisor (Section 1.1) provides a good example of
this kind of algorithm. In this section, we encounter a few more examples of
this variety.

**Computing
a Median and the Selection Problem**

The ** selection
problem** is the problem of finding the

** O(n **log

You
should immediately suspect, however, that sorting the entire list is most
likely overkill since the problem asks not to order the entire list but just to
find its ** k**th smallest element. Indeed, we
can take advantage of the idea of

Of the
two principal algorithmic alternatives to partition an array, here we discuss
the ** Lomuto
partitioning** [Ben00, p. 117]; we introduce the better known Hoare’s
algorithm in the next chapter. To get the idea behind the Lomuto parti-tioning,
it is helpful to think of an array—or, more generally, a subarray

Starting
with ** i** =

Here is
pseudocode implementing this partitioning procedure.

**ALGORITHM** *LomutoPartition*** (A**[

//Partitions
subarray by Lomuto’s algorithm using first element as pivot //Input: A subarray
** A**[

indices ** l** and

//Output:
Partition of ** A**[

** s **←

**for ***i*** **←** ***l*** **+** **1** to ***r*** do**

**if **** A**[

** s **←

**return ***s*

How can
we take advantage of a list partition to find the ** k**th
smallest element in it? Let us assume that the list is implemented as an array
whose elements are indexed starting with a 0, and let

To find
the ** k**th smallest element in array

*Quickselect*** (A**[0

**ALGORITHM** *Quickselect*** (A**[

//Solves
the selection problem by recursive partition-based algorithm //Input: Subarray ** A**[

integer ** k (**1 ≤

//Output:
The value of the *k*th smallest element
in ** A**[

** s **←

**else if ***s
> l*** **+** ***k*** **−** **1** ***Quickselect*** (A**[

In fact,
the same idea can be implemented without recursion as well. For the nonrecursive
version, we need not even adjust the value of ** k** but just
continue until

**EXAMPLE **Apply the
partition-based algorithm to find the median of the fol-lowing list of nine
numbers: 4, 1, 10, 8, 7, 12, 9, 2, 15. Here, ** k** = 9

We use
the above version of array partitioning, showing the pivots in bold.

Now ** s** =

How
efficient is quickselect? Partitioning an ** n**-element
array always requires

without
requiring more iterations, then for this best case we obtain *C _{best}*

partition
of a given array, with one part being empty and the other containing ** n** − 1
elements. In the worst case, this can happen on each of the

** C_{worst} (n) **=

which
compares poorly with the straightforward sorting-based approach men-tioned in
the beginning of our selection problem discussion. Thus, the usefulness of the
partition-based algorithm depends on the algorithm’s efficiency in the average
case. Fortunately, a careful mathematical analysis has shown that the
average-case efficiency is linear. In fact, computer scientists have discovered
a more sophisti-cated way of choosing a pivot in quickselect that guarantees
linear time even in the worst case [Blo73], but it is too complicated to be
recommended for practical applications.

It is
also worth noting that the partition-based algorithm solves a somewhat more
general problem of identifying the ** k** smallest
and

**Interpolation
Search**

As the
next example of a variable-size-decrease algorithm, we consider an algo-rithm
for searching in a sorted array called ** interpolation search**. Unlike binary
search, which always compares a search key with the middle value of a given
sorted array (and hence reduces the problem’s instance size by half),
interpolation search takes into account the value of the search key in order to
find the array’s element to be compared with the search key. In a sense, the
algorithm mimics the way we

search
for a name in a telephone book: if we are searching for someone named Brown, we
open the book not in the middle but very close to the beginning, unlike our
action when searching for someone named, say, Smith.

More
precisely, on the iteration dealing with the array’s portion between the
leftmost element ** A**[

Writing
down a standard equation for the straight line passing through the points ** (l, A**[

The logic
behind this approach is quite straightforward. We know that the array values
are increasing (more accurately, not decreasing) from ** A**[

After
comparing ** v** with

The
analysis of the algorithm’s efficiency shows that interpolation search uses
fewer than log_{2} log_{2} ** n** + 1 key comparisons on the average
when searching in a list of

Assessing
the worthiness of interpolation search versus that of binary search, Robert
Sedgewick wrote in the second edition of his *Algorithms* that binary search is probably better for smaller files
but interpolation search is worth considering for large files and for
applications where comparisons are particularly expensive or access costs are
very high. Note that in Section 12.4 we discuss a continuous counterpart of
interpolation search, which can be seen as one more example of a
variable-size-decrease algorithm.

**Searching
and Insertion in a Binary Search Tree**

Let us
revisit the binary search tree. Recall that this is a binary tree whose nodes
contain elements of a set of orderable items, one element per node, so that for
every node all elements in the left subtree are smaller and all the elements in
the right subtree are greater than the element in the subtree’s root. When we
need to search for an element of a given value ** v** in such
a tree, we do it recursively in the following manner. If the tree is empty, the
search ends in failure. If the tree is not empty, we compare

In the
worst case of the binary tree search, the tree is severely skewed. This
happens, in particular, if a tree is constructed by successive insertions of an
increasing or decreasing sequence of keys (Figure 4.15).

Obviously,
the search for *a _{n}*

**The Game
of Nim**

There are
several well-known games that share the following features. There are two
players, who move in turn. No randomness or hidden information is permitted:
all players know all information about gameplay. A game is impartial: each
player has the same moves available from the same game position. Each of a
finite number of available moves leads to a smaller instance of the same game.
The game ends with a win by one of the players (there are no ties). The winner
is the last player who is able to move.

A prototypical
example of such games is ** Nim**. Generally, the game is played
with several piles of chips, but we consider the one-pile version first. Thus,
there is a single pile of

Let us
call an instance of the game a winning position for the player to move next if
that player has a winning strategy, i.e., a sequence of moves that results in a
victory no matter what moves the opponent makes. Let us call an instance of the
game a losing position for the player to move next if every move available for
that player leads to a winning position for the opponent. The standard approach
to determining which positions are winning and which are losing is to
investigate small values of ** n** first.
It is logical to consider the instance of

position.
2** m** + 2 = 2

One-pile
Nim has been known for a very long time. It appeared, in particular, as the ** summation
game** in the first published book on recreational mathematics, authored
by Claude-Gaspar Bachet, a French aristocrat and mathematician, in 1612: a
player picks a positive integer less than, say, 10, and then his opponent and
he take turns adding any integer less than 10; the first player to reach 100
exactly is the winner [Dud70].

In
general, Nim is played with ** I >** 1 piles
of chips of sizes

A
solution to the general case of Nim is quite unexpected because it is based on
the binary representation of the pile sizes. Let *b*_{1}*, b*_{2}** , . . . , b_{I}** be the
pile sizes in binary. Compute their

Since
this sum contains a 1, the instance is a winning one for the player moving
first. To find a winning move from this position, the player needs to change
one of the three bit strings so that the new nim sum contains only 0’s. It is
not difficult to see that the only way to accomplish this is to remove two chips
from the first pile.

This
ingenious solution to the game of Nim was discovered by Harvard math-ematics
professor C. L. Bouton more than 100 years ago. Since then, mathemati-cians
have developed a much more general theory of such games. An excellent account
of this theory, with applications to many specific games, is given in the
monograph by E. R. Berlekamp, J. H. Conway, and R. K. Guy [Ber03].

**Exercises
4.5**

** **1. **
****a. **If we
measure an instance size of computing the greatest common divisor** **of ** m** and

**
**Prove that an instance size will always decrease at
least by a factor of two after two successive iterations of Euclid’s algorithm.

** **2. Apply quickselect to find the median of the list of
numbers 9, 12, 5, 17, 20, 30, 8.

** **3. Write pseudocode for a nonrecursive implementation
of quickselect.

** **4. Derive the formula underlying interpolation search.

** **5. Give an example of the worst-case input for
interpolation search and show that the algorithm is linear in the worst case.

** **. **
****a. **Find the smallest value of** ***n*** **for which log_{2}** **log_{2}** ***n*** **+** **1 is
greater than 6.

**
**Determine which, if any, of the following assertions
are true:

**i. **log log** ***n*** **∈** **** o(**log

** **. **a. **Outline
an algorithm for finding the largest key in a binary search tree.** **Would you classify your algorithm as a
variable-size-decrease algorithm?

**
**What is the time efficiency class of your algorithm
in the worst case?

**
****a. **Outline
an algorithm for deleting a key from a binary search tree. Would** **you classify this algorithm as a
variable-size-decrease algorithm?

**
**What is the time efficiency class of your algorithm
in the worst case?

** **9. Outline a variable-size-decrease algorithm for
constructing an Eulerian circuit in a connected graph with all vertices of even
degrees.

** **10. **
***Mis`ere
one-pile Nim *Consider the so-called* misere` version *of the
one-pile

** **11. **
****a. ***Moldy chocolate*** **Two
players take turns by breaking an** ***m*** **×** ***n*** **chocolate** **bar, which has one spoiled 1 × 1 square. Each break must be a
single straight line cutting all the way across the bar along the boundaries
between the squares. After each break, the player who broke the bar last eats
the piece that does not contain the spoiled square. The player left with the
spoiled square loses the game. Is it better to go first or second in this game?

** **b. Write an interactive program to play this game with
the computer. Your program should make a winning move in a winning position and
a random legitimate move in a losing position.

** **12. *Flipping
pancakes *There are* **n** *pancakes
all of different sizes that are stacked* *on
top of each other. You are allowed to slip a flipper under one of the pancakes
and flip over the whole stack above the flipper. The purpose is to arrange
pancakes according to their size with the biggest at the bottom. (You can see a
visualization of this puzzle on the *Interactive
Mathematics Miscellany* *and Puzzles *site
[Bog].) Design an algorithm for solving this puzzle.

** **13. You need to search for a given number in an ** n** ×

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

Introduction to the Design and Analysis of Algorithms : Decrease and Conquer : Variable Size Decrease Algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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