1.3- problem types

Question 1

sorting problem

Answer 1

to rearrange the items of a given list in nondecreasing
order. Of course, for this problem to be meaningful, the nature of the list items
must allow such an ordering. (Mathematicians would say that there must exist
a relation of total ordering.) As a practical matter, we usually need to sort lists
of numbers, characters from an alphabet, character strings, and, most important,
records similar to those maintained by schools about their students, libraries about
their holdings, and companies about their employees.

Question 2

Sorting:
key

Answer 2

In the case of records, we
need to choose a piece of information to guide sorting.
Such a specially chosen piece of information is called a key. Computer scientists often talk about sorting a list of keys even when the list’s
items are not records but, say, just integers

Question 3

A sorting algorithm is called ______ if it preserves the relative order of any two equal elements in
its input.

Answer 3

stable

Question 4

The second notable feature of a sorting algorithm is the amount of extra
memory the algorithm requires. An algorithm is said to be _______ if it does
not require extra memory, except, possibly, for a few memory units. There are
important sorting algorithms that are in-place and those that are not

Answer 4

in-place

Question 5

deals with finding a given value, called a search key, in a given set (or a multiset, which permits several elements to have the same value).

Answer 5

searching problem

Question 6

string

Answer 6

a sequence of characters from an alphabet.
Strings of particular interest are text strings, which comprise letters, numbers, and
special characters; bit strings, which comprise zeros and ones; and gene sequences,
which can be modeled by strings of characters from the four-character alphabet {A,
C, G, T}

Question 7

One particular problem—that of searching for a given word in a text—has
attracted special attention from researchers. They call it _____ ______. Several
algorithms that exploit the special nature of this type of searching have been
invented.

Answer 7

string matching

Question 8

can be thought of as a collection of points called vertices, some
of which are connected by line segments called edges.

Answer 8

graph

Question 9

the problem of finding the shortest tour
through n cities that visits every city exactly once. In addition to obvious applications involving route planning, it arises in such modern applications as circuit
board and VLSI chip fabrication, X-ray crystallography, and genetic engineering.

Answer 9

traveling salesman problem (TSP)

Question 10

seeks to assign the smallest number of colors to
the vertices of a graph so that no two adjacent vertices are the same color. This
problem arises in several applications, such as event scheduling: if the events are
represented by vertices that are connected by an edge if and only if the corresponding events cannot be scheduled at the same time, a solution to the graph-coloring
problem yields an optimal schedule.

Answer 10

graph-coloring problem

Question 11

From a more abstract perspective, the traveling salesman problem and the graph coloring problem are examples of ______ _____. These are problems
that ask, explicitly or implicitly, to find a combinatorial object—such as a permutation, a combination, or a subset—that satisfies certain constraints. A desired
combinatorial object may also be required to have some additional property such
as a maximum value or a minimum cost.

Answer 11

combinatorial problems

Question 12

Generally speaking, combinatorial problems are the most difficult problems in
computing, from both a theoretical and practical standpoint. Their difficulty stems
from the following facts. First, the number of combinatorial objects typically grows
extremely fast with a problem’s size, reaching unimaginable magnitudes even
for moderate-sized instances.

Answer 12

Second, there are no known algorithms for solving
most such problems exactly in an acceptable amount of time. Moreover, most
computer scientists believe that such algorithms do not exist. This conjecture has
been neither proved nor disproved, and it remains the most important unresolved
issue in theoretical computer science

Question 13

deal with geometric objects such as points, lines, and polygons.

Answer 13

geometric algorithms

Question 14

closest-pair problem

Answer 14

given n points in the plane, find the closest pair among them.

Question 15

convex-hull problem

Answer 15

asks to find the smallest convex polygon that
would include all the points of a given set. If you are interested in other geometric
algorithms, you will find a wealth of material in such specialized monographs as
[deB10], [ORo98], and [Pre85].

Question 16

another large special area of applications, are problems
that involve mathematical objects of continuous nature: solving equations and
systems of equations, computing definite integrals, evaluating functions, and so on.
The majority of such mathematical problems can be solved only approximately.
Another principal difficulty stems from the fact that such problems typically
require manipulating real numbers, which can be represented in a computer only
approximately. Moreover, a large number of arithmetic operations performed on
approximately represented numbers can lead to an accumulation of the round-off error to a point where it can drastically distort an output produced by a seemingly
sound algorithm.

Answer 16

numerical problems