1. Binary Search
2. Fake-Coin Problem
3. Russian Peasant Multiplication
4. Josephus Problem
5. Exercises

**Decrease-by-a-Constant-Factor
Algorithms**

**1. Binary Search**

**2. Fake-Coin Problem**

**3. Russian Peasant Multiplication**

**4. Josephus Problem**

**5. Exercises**

You may
recall from the introduction to this chapter that decrease-by-a-constant-factor
is the second major variety of decrease-and-conquer. As an example of an
algorithm based on this technique, we mentioned there exponentiation by
squar-ing defined by formula (4.2). In this section, you will find a few other
examples of such algorithms.. The most important and well-known of them is
binary search. Decrease-by-a-constant-factor algorithms usually run in
logarithmic time, and, be-ing very efficient, do not happen often; a reduction
by a factor other than two is especially rare.

**Binary
Search**

Binary
search is a remarkably efficient algorithm for searching in a sorted array. It
works by comparing a search key ** K** with the
array’s middle element

Though
binary search is clearly based on a recursive idea, it can be easily
implemented as a nonrecursive algorithm, too. Here is pseudocode of this
nonre-cursive version.

**ALGORITHM** *BinarySearch*** (A**[0

//Implements
nonrecursive binary search

//Input:
An array ** A**[0

a search key *K*

//Output:
An index of the array’s element that is equal to *K*

// or −1 if
there is no such element

** l **←

**while ***l*** **≤** ***r*** do**

** m **←

**if ***K*** **=** **** A**[

**else if **** K
< A**[

**return **−1

The
standard way to analyze the efficiency of binary search is to count the number
of times the search key is compared with an element of the array. Moreover, for
the sake of simplicity, we will count the so-called three-way comparisons. This
assumes that after one comparison of ** K** with

How many
such comparisons does the algorithm make on an array of ** n** elements? The answer obviously
depends not only on

in the
worst case *C _{worst}*

comparison
the algorithm faces the same situation but for an array half the size, we get
the following recurrence relation for *C _{worst}*

(Stop and
convince yourself that ** n/**2 must
be, indeed, rounded down and that the initial condition must be written as
specified.)

We
already encountered recurrence (4.3), with a different initial condition, in
Section 2.4 (see recurrence (2.4) and its solution there for ** n** = 2

Further,
similarly to the case of recurrence (2.4) (Problem 7 in Exercises 2.4), the
solution given by formula (4.4) for ** n** = 2

Formula
(4.5) deserves attention. First, it implies that the worst-case time efficiency
of binary search is in ** (**log

What can
we say about the average-case efficiency of binary search? A so-phisticated
analysis shows that the average number of key comparisons made by binary search
is only slightly smaller than that in the worst case:

** C_{avg}(n) **≈

(More
accurate formulas for the average number of comparisons in a successful and an
unsuccessful search are ** C_{avg}^{yes}(n)** ≈ log

Though
binary search is an optimal searching algorithm if we restrict our op-erations
only to comparisons between keys (see Section 11.2), there are searching
algorithms (see interpolation search in Section 4.5 and hashing in Section 7.3)
with a better average-case time efficiency, and one of them (hashing) does not
even re-quire the array to be sorted! These algorithms do require some special
calculations in addition to key comparisons, however. Finally, the idea behind
binary search has several applications beyond searching (see, e.g., [Ben00]).
In addition, it can be applied to solving nonlinear equations in one unknown;
we discuss this continuous analogue of binary search, called the method of
bisection, in Section 12.4.

**Fake-Coin
Problem**

Of
several versions of the fake-coin identification problem, we consider here the
one that best illustrates the decrease-by-a-constant-factor strategy. Among ** n** identical-looking coins, one is
fake. With a balance scale, we 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 design an efficient algorithm for detecting
the fake coin. An easier version of the problem—the one we discuss here—assumes
that the fake coin is known to be, say, lighter than the genuine one.

The most
natural idea for solving this problem is to divide ** n** coins
into two piles of

piles on
the scale. If the piles weigh the same, the coin put aside must be fake;
otherwise, we can proceed in the same manner with the lighter pile, which must
be the one with the fake coin.

We can
easily set up a recurrence relation for the number of weighings ** W (n)** needed by this algorithm in the
worst case:

** W (n) **=

This
recurrence should look familiar to you. Indeed, it is almost identical to the
one for the worst-case number of comparisons in binary search. (The difference
is in the initial condition.) This similarity is not really surprising, since
both algorithms are based on the same technique of halving an instance size.
The solution to the recurrence for the number of weighings is also very similar
to the one we had for binary search: ** W
(n)** = log

This
stuff should look elementary by now, if not outright boring. But wait: the
interesting point here is the fact that the above algorithm is not the most
efficient solution. It would be more efficient to divide the coins not into two
but into *three* piles of about ** n/**3 coins each. (Details of a
precise formulation are developed in this section’s exercises. Do not miss it!
If your instructor forgets, demand the instructor to assign Problem 10.) After
weighing two of the piles, we can reduce the instance size by a factor of
three. Accordingly, we should expect the number of weighings to be about log

**Russian
Peasant Multiplication**

Now we
consider a nonorthodox algorithm for multiplying two positive integers called ** multiplication
a` la russe** or the

Using
these formulas and the trivial case of 1 ^{.}** m** =

Also note
that the algorithm involves just the simple operations of halving, doubling,
and adding—a feature that might be attractive, for example, to those

who do
not want to memorize the table of multiplications. It is this feature of the
algorithm that most probably made it attractive to Russian peasants who,
accord-ing to Western visitors, used it widely in the nineteenth century and
for whom the method is named. (In fact, the method was known to Egyptian
mathematicians as early as 1650 B.C. [Cha98, p. 16].) It also leads to very
fast hardware implementa-tion since doubling and halving of binary numbers can
be performed using shifts, which are among the most basic operations at the
machine level.

**Josephus
Problem**

Our last
example is the ** Josephus problem**, named for Flavius Josephus, a famous Jewish
historian who participated in and chronicled the Jewish revolt of 66–70 C.E. against
the Romans. Josephus, as a general, managed to hold the fortress of Jotapata
for 47 days, but after the fall of the city he took refuge with 40 diehards in
a nearby cave. There, the rebels voted to perish rather than surrender.
Josephus proposed that each man in turn should dispatch his neighbor, the order
to be determined by casting lots. Josephus contrived to draw the last lot, and,
as one of the two surviving men in the cave, he prevailed upon his intended
victim to surrender to the Romans.

So let ** n** people numbered 1 to

It is
convenient to consider the cases of even and odd ** n**’s
separately. If

** J (**2

Let us
now consider the case of an odd ** n** (

** J (**2

Can we
get a closed-form solution to the two-case recurrence subject to the initial
condition ** J (**1

**Exercises
4.4**

** **1. *Cutting a
stick *A stick* **n** *inches
long needs to be cut into* **n** *1-inch
pieces.* *Outline an algorithm that
performs this task with the minimum number of 1. cuts if several pieces of the
stick can be cut at the same time. Also give a formula for the minimum number
of cuts.

** **2. Design a decrease-by-half algorithm for computing
log_{2} ** n** and
determine its time efficiency.

** **3. **a. **What is
the largest number of key comparisons made by binary search in** **searching for a key in the following
array?

**
**List all the keys of this array that will require
the largest number of key comparisons when searched for by binary search.

**
**Find the average number of key comparisons made by
binary search in a successful search in this array. Assume that each key is
searched for with the same probability.

**
**Find the average number of key comparisons made by
binary search in an unsuccessful search in this array. Assume that searches for
keys in each of the 14 intervals formed by the array’s elements are equally
likely.

** **4. **
**Estimate how many times faster an average
successful search will be in a sorted array of one million elements if it is
done by binary search versus sequential search.

** **5. **
**The time efficiency of sequential search does not
depend on whether a list is implemented as an array or as a linked list. Is it
also true for searching a sorted list by binary search?

** **6. **a. **Design a
version of binary search that uses only two-way comparisons such** **as ≤ and =. Implement your algorithm in the
language of your choice and carefully debug it: such programs are notorious for
being prone to bugs.

**
**Analyze the time efficiency of the two-way
comparison version designed in part a.

** **7. *Picture
guessing *A version of the popular problem-solving task involves pre-senting
people with an array of 42 pictures—seven rows of six pictures each— and asking
them to identify the target picture by asking questions that can be answered
yes or no. Further, people are then required to identify the picture with as
few questions as possible. Suggest the most efficient algorithm for this
problem and indicate the largest number of questions that may be necessary.

8. Consider ** ternary
search**—the following algorithm for searching in a sorted array

**
**What design technique is this algorithm based on?

**
**Set up a recurrence for the number of key
comparisons in the worst case. You may assume that ** n** = 3

**
**Solve the recurrence for ** n** = 3

**
**Compare this algorithm’s efficiency with that of
binary search.

** **9. **
**An array ** A**[0

** **10. **a. **Write
pseudocode for the divide-into-three algorithm for the fake-coin** **problem. Make sure that your algorithm
handles properly all values of ** n**, not
only those that are multiples of 3.

**
**Set up a recurrence relation for the number of
weighings in the divide-into-three algorithm for the fake-coin problem and
solve it for ** n** = 3

**
**For large values of ** n**, about
how many times faster is this algorithm than the one based on dividing coins
into two piles? Your answer should not depend on

** **11. **a. **Apply the Russian peasant
algorithm to compute 26** **^{.}** **47*.*

**
**From the standpoint of time efficiency, does it
matter whether we multiply ** n **by

** **12. **
****a. **Write pseudocode for the Russian
peasant multiplication algorithm.

**
**What is the time efficiency class of Russian
peasant multiplication?

** **13. **
**Find ** J (**40

** **14. **
**Prove that the solution to the Josephus problem is
1 for every ** n** that is a power of 2.

** **15. For the Josephus problem,

**
**compute ** J (n)** for

**
**discern a pattern in the solutions for the first
fifteen values of ** n** and
prove its general validity.

**
**prove the validity of getting ** J (n)** by a 1-bit cyclic shift left of
the binary representation of

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

Introduction to the Design and Analysis of Algorithms : Decrease and Conquer : Decrease by a Constant Factor 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.