Recursion - Data Structures and Problem Solving Using Java - page 319

actually employed is more complex than described here. One problem is that
the RSA algorithm is somewhat slow for sending large messages.

A faster method is called DES . Unlike the RSA algorithm, DES is a single-
key algorithm, meaning that the same key serves both to encode and decode. It
is like the typical lock on your house door. The problem with single-key algo-
rithms is that both parties need to share the single key. How does one party
ensure that the other party has the single key? That problem can be solved
by using the RSA algorithm. A typical solution is that, say, Alice will randomly
generate a single key for DES encryption. She then encrypts her message by
using DES, which is much faster than using RSA. She transmits the encrypted
message to Bob. For Bob to decode the encrypted message, he needs to get the
DES key that Alice used. A DES key is relatively short, so Alice can use RSA to
encrypt the DES key and then send it in a second transmission to Bob. Bob next
decrypts Alice's second transmission, thus obtaining the DES key, at which
point he can decode the original message. These types of protocols, with
enhancements, form the basis of most practical encryption implementations.

In practice, RSA is
used to encrypt the
key used by a
single-key encryp-
tion algorithm, such
as DES.

divide-and-conquer algorithms

7.5

An important problem-solving technique that makes use of recursion is
divide and conquer. A divide-and-conquer algorithm is an efficient recursive
algorithm that consist of two parts:

A divide-and-
conquer algorithm
is a recursive algo-
rithm that is gener-
ally very efficient.

Divide, in which smaller problems are solved recursively (except, of
course, base cases)

n

Conquer, in which the solution to the original problem is then formed
from the solutions to the subproblems

n

In divide and con-
quer, the recursion
is the divide, and
the overhead is the
conquer .

Traditionally, routines in which the algorithm contains at least two recur-
sive calls are called divide-and-conquer algorithms, whereas routines whose
text contains only one recursive call are not. Consequently, the recursive rou-
tines presented so far in this chapter are not divide-and-conquer algorithms.
Also, the subproblems usually must be disjoint (i.e., essentially nonoverlap-
ping), so as to avoid the excessive costs seen in the sample recursive computa-
tion of the Fibonacci numbers.
In this section we give an example of the divide-and-conquer paradigm.
First we show how to use recursion to solve the maximum subsequence
sum problem. Then we provide an analysis to show that the running time
is O ( N log N ). Although we have already used a linear algorithm for this