What kinds of problems are solved by algorithms I ?

What kinds of problems are solved by algorithms I ? 

While some of the details of these examples are beyond the scope of this book, we do give underlying techniques that apply to these problems and problem areas.We also show how to solve many concrete problems in this book, including the following :

• We are given a road map on which the distance between each pair of adjacent intersections is marked, and our goal is to determine the shortest route from one intersection to another. The number of possible routes can be huge, even if we disallow routes that cross over themselves. How do we choose which of all possible routes is the shortest? Here, we model the road map (which is itself a model of the actual roads) as a graph (which we will meet in Chapter 10 and Appendix B), and we wish to find the shortest path from one vertex to another in the graph. We shall see how to solve this problem efficiently in Chapter 24.

• We are given a sequence A1, A2, . . . , An of n matrices, and we wish to determine their product A1 A2 · · · An . Because matrix multiplication is associative, there are several legal multiplication orders. For example, if n = 4, we could perform the matrix multiplications as if the product were parenthesized in any of the following orders: (A1(A2(A3 A4))), (A1((A2 A3)A4)), ((A1 A2)(A3 A4)), ((A1(A2 A3))A4), or (((A1A2)A3)A4). If these matrices are all square (and hence the same size), the multiplication order will not affect how long the matrix
multiplications take. If, however, these matrices are of differing sizes (yet their sizes are compatible for matrix multiplication), then the multiplicationorder can make a very big difference. The number of possible multiplication orders is exponential in n, and so trying all possible orders may take a very long time. We shall see in Chapter 15 how to use a general technique known as dynamic programming to solve this problem much more efficiently.

• We are given an equation ax ≡ b (mod n), where a, b, and n are integers, and we wish to find all the integers x, modulo n, that satisfy the equation. There may be zero, one, or more than one such solution. We can simply try x = 0, 1, . . . , n − 1 in order, but Chapter 31 shows a more efficient method.

• We are given n points in the plane, and we wish to find the convex hull of these points. The convex hull is the smallest convex polygon containing the points. Intuitively, we can think of each point as being represented by a nail sticking out from a board. The convex hull would be represented by a tight rubber band that surrounds all the nails. Each nail around which the rubber band makes a turn is a vertex of the convex hull. (See Figure 33.6 on page 948
for an example.) Any of the 2n subsets of the points might be the vertices of the convex hull. Knowing which points are vertices of the convex hull is not quite enough, either, since we also need to know the order in which they appear. There are many choices, therefore, for the vertices of the convex hull. Chapter 33 gives two good methods for finding the convex hull.

Tweet