|
Abstract : |
A basic issue in computer science is the complexity of problems. If one is doing a calculation once on a medium-sized input, the simplest algorithm may be the best method to use, even if it is not the fastest. However, when one has a subproblem that will have to be solved millions of times, optimization is important. A fundamental issue in theoretical computer science is the computational complexity of problems. How much time and how much memory space is needed to solve a particular problem? Here are a few examples of such problems: 1. Reachability: Given a directed graph and two specified points s; t, determine if there is a path from s to t. A simple, linear-time algorithm marks s and then continues to mark every vertex at the head of an edge whose tail is marked. When no more vertices can be marked, t is reachable from s iff it has been marked. 2. Min-triangulation: Given a polygon in the plane and a length L, determine if there is a triangulation of the polygon of total length less than or equal to L. Even though there are exponentially many possible triangulations, a dynamic programming algorithm can find an optimal one in O(n 3) steps. 3. Three-Colorability: Given an undirected graph, determine whether its vertices can be colored using three colors with no two adjacent vertices having the same color. Again there are exponentially many possibilities but in this case no known algorithm is faster than exponential time., |
