This file contains the exercises, hints, and solutions for Chapter 3 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
A. Levitin. The problems that might be challenging for at least some students
are marked by B; those that migh t be difficult for a majority of students are
marked by I
Exercises 3.1
1. a. Give an example of an algorithm that should not be considered an
application of the brute-force approach.
b. Give an example of a problem that cannot be solved by a brute-force
algorithm.
2. a. What is the efficiency of the brute-force algorithm for computing
as a function of ? As a function of the number of bits in the binary
representation of ?
b. If you are to compute
mod where 1 and is a large positive
integer, how would you circumvent the problem of a very large magnitude
of
?
3. For each of the algorithms in Problems 4, 5, and 6 of Exercises 2.3, tell
whether or not the algorithm is based on the brute-force approach.
4. a. Design a brute-force algorithm for computing the value of a polynomial
()=
+
−1
−1
+ ···+
1
+
0
at a given point
0
and determine its worst-case efficiency class.
b. If the algorithm you designed is in Θ(
2
) design a linear algorithm
for this problem.
c. Is it possible to design an algorithm with a better-than-linear efficiency
for this problem?
5. A network topology specifies how computers, printers, and other devices
are connected over a network. The figure below illustrates three common
topologies of networks: Ring, Star, and Fully Connected Mesh.
Ring Star Fully Connected Mesh
1
