1.2 Fundamentals of Algo Problem Solving

Question 1

An input to an algorithm specifies an _____ of the problem the algorithm
solves. It is very important to specify exactly the set of instances the algorithm
needs to handle.

Answer 1

instance

Question 2

The central assumption of the RAM model does not hold for some newer
computers that can execute operations concurrently, i.e., in parallel. Algorithms
that take advantage of this capability are called ___ ____

Answer 2

parallel algorithms

Question 3

algorithms designed to be executed on such machines (von Neumann machines) are called ____ algorithms

Answer 3

sequential

Question 4

The next principal decision is to choose between solving the problem exactly or
solving it approximately. In the former case, an algorithm is called an ____ _____; in the latter case, an algorithm is called an approximation algorithm.
Why would one opt for an approximation algorithm? First, there are important problems that simply cannot be solved exactly for most of their instances; examples
include extracting square roots, solving nonlinear equations, and evaluating definite integrals. Second, available algorithms for solving a problem exactly can be
unacceptably slow because of the problem’s intrinsic complexity

Answer 4

exact algorithm

Question 5

a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

Answer 5

algorithm design technique

Question 6

Once an algorithm has been specified, you have to prove its _____. That is,
you have to prove that the algorithm yields a required result for every legitimate
input in a finite amount of time.

Answer 6

correctness

Question 7

For some algorithms, a proof of correctness is quite easy; for others, it can be quite complex. A common technique for proving correctness is to use ____ _____ because an algorithm’s iterations provide a natural sequence of steps needed for such proofs. It might be worth mentioning that although tracing the algorithm’s performance for a few specific inputs can be a very worthwhile activity, it cannot prove the algorithm’s correctness conclusively. But in order to show that an algorithm is incorrect, you need just one instance of its input for which the algorithm fails.

Answer 7

mathematical induction

Question 8

We usually want our algorithms to possess several qualities. After correctness,
by far the most important is _____

Answer 8

efficiency

Question 9

indicating how fast the algorithm runs

Answer 9

time efficiency

Question 10

indicating how much extra memory it uses

Answer 10

space efficiency

Question 11

Unlike efficiency, which can be precisely defined and investigated with mathematical rigor,
_______, like beauty, is to a considerable degree in the eye of the beholder.

Answer 11

simplicity

Question 12

Yet another desirable characteristic of an algorithm is ______. There are,
in fact, two issues here: generality of the problem the algorithm solves and the
set of inputs it accepts.

Answer 12

generality

Question 13

As a practical matter, the validity of programs is still established by ______.

Answer 13

testing