Page 245 - Discrete Mathematics and Its Applications

224 3 / Algorithms

multiplications are used. On the other hand, if A 1 and A 2 are first multiplied, then 30 · 20 · 40 =
24,000 multiplications are used to obtain the 30 × 40 matrix A 1 A 2 . Then, to multiply A 1 A 2
and A 3 requires 30 · 40 · 10 = 12,000 multiplications. Hence, a total of

24,000 + 12,000 = 36,000

multiplications are used.
Clearly, the first method is more efficient. ▲

We will return to this problem in Exercise 57 in Section 8.1. Algorithms for determining
the most efficient way to carry out matrix-chain multiplication are discussed in [CoLeRiSt09].

Algorithmic Paradigms

In Section 3.1 we introduced the basic notion of an algorithm. We provided examples of many
different algorithms, including searching and sorting algorithms.We also introduced the concept
of a greedy algorithm, giving examples of several problems that can be solved by greedy algo-
rithms. Greedy algorithms provide an example of an algorithmic paradigm, that is, a general
approach based on a particular concept that can be used to construct algorithms for solving a
variety of problems.
In this book we will construct algorithms for solving many different problems based on a
variety of algorithmic paradigms, including the most widely used algorithmic paradigms. These
paradigms can serve as the basis for constructing efficient algorithms for solving a wide range
of problems.
Someofthealgorithmswehavealreadystudiedarebasedonanalgorithmicparadigmknown
as brute force, which we will describe in this section. Algorithmic paradigms, studied later in
this book, include divide-and-conquer algorithms studied in Chapter 8, dynamic programming,
also studied in Chapter 8, backtracking, studied in Chapter 10, and probabilistic algorithms,
studied in Chapter 7. There are many important algorithmic paradigms besides those described
in this book. Consult books on algorithm design such as [KlTa06] to learn more about them.

BRUTE-FORCE ALGORITHMS Brute force is an important, and basic, algorithmic
paradigm. In a brute-force algorithm, a problem is solved in the most straightforward manner
based on the statement of the problem and the definitions of terms. Brute-force algorithms are
designed to solve problems without regard to the computing resources required. For example,
in some brute-force algorithms the solution to a problem is found by examining every possible
solution, looking for the best possible. In general, brute-force algorithms are naive approaches
for solving problems that do not take advantage of any special structure of the problem or clever
ideas.
Note that Algorithm 1 in Section 3.1 for finding the maximum number in a sequence is
a brute-force algorithm because it examines each of the n numbers in a sequence to find the
maximum term. The algorithm for finding the sum of n numbers by adding one additional
number at a time is also a brute-force algorithm, as is the algorithm for matrix multiplication
based on its definition (Algorithm 1). The bubble, insertion, and selection sorts (described in
Section 3.1 in Algorithms 4 and 5 and in Exercise 42, respectively) are also considered to be
brute-force algorithms; all three of these sorting algorithms are straightforward approaches much
less efficient than other sorting algorithms such as the merge sort and the quick sort discussed
in Chapters 5 and 8.
Although brute-force algorithms are often inefficient, they are often quite useful. A brute-
force algorithm may be able to solve practical instances of problems, particularly when the input