2.11 Review questions

This final section contains some review questions about the contents of this chapter.

2.11.1 Review questions: Introduction

Answer TRUE or FALSE.

There is only one way that a given problem can be solved.

  • There are always an infinite number of ways to solve a problem (though there might be only one “reasonable” approach).

Answer TRUE or FALSE.

There are some algorithms that do not terminate for certain inputs.

  • By the technical definition of “algorithm”, all algorithms terminate.
  • Of course, that means that some programs are not technically algorithms.

Answer TRUE or FALSE.

An algorithm is a series of steps that act as a recipe to solve a particular problem.

  • This is as good a descriptive definition for “algorithm” as any.

Answer TRUE or FALSE.

A problem instance is a series of steps that act as a recipe to solve a particular problem.

  • A problem instance is a particular input for a problem.

Answer TRUE or FALSE.

A problem is an instantiation of an algorithm implemented in a specific programming language.

  • A PROGRAM is an instantiation of an algorithm implemented in a specific programming language.

Answer TRUE or FALSE.

A program is an instantiation of an algorithm implemented in a specific programming language.

  • This statement captures the relationship between a program and an algorithm.

Answer TRUE or FALSE.

An algorithm can only work if it is written in the right type of programming language.

  • All programming languages implement the same set of algorithms. Though, some languages make certain algorithms easier to implement than do other languages.

Answer TRUE or FALSE.

A problem maps inputs to outputs.

  • This is the standard technical definition for a problem.

Answer TRUE or FALSE.

An algorithm maps inputs to outputs.

  • No. A PROBLEM maps inputs to outputs.
  • An algorithm implements the mapping.

Answer TRUE or FALSE.

A program maps inputs to outputs.

  • No. A PROBLEM maps inputs to outputs.
  • A program implements an algorithm.

Answer TRUE or FALSE.

A problem instance is a specific selection of values for the problem input.

  • This is correct.

Which is the best definition for algorithm?

  • An algorithm is implemented using a program, but it is not a program.
  • A problem is a mapping from input to output.
  • While informal, the term “recipe” captures the essence of what an algorithm is.

Which is true about the relationship between algorithms and problems?

  • A problem is a mapping from inputs to outputs.
  • An algorithm is a recipe.
  • There are many algorithms that can solve a given problem.

2.11.2 Review questions: Growth rates

Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size nn in one hour, what size input can XYZ’s computer execute in one hour for an algorithm whose growth rate is n2n^2?

  • If the XYZ Corp. computer runs 100 times faster, then if the Prunes computer does SS computations in an hour, the XYZ Corp. computer does 100S100S computations in an hour.
  • Assume that the Prunes computer can solve a problem size of at most PP in an hour. This means it makes about P2=SP^2 = S computations.
  • How much bigger size than PP can run in 100S100S, given that the growth rate of the algorithm on input size PP is T(P)=P2T(P) = P^2?
  • If PSP \approx S, then T(10P)=(10P)2100ST(10P) = (10P)^2 \approx 100S.

Suppose that a particular algorithm has time complexity T(n)=3×2nT(n) = 3 \times 2^n and that executing an implementation of it on a particular machine takes tt seconds for nn inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in tt seconds?

  • This problem has an exponential growth rate. The behaviour of an exponential growth rate is different from a polynomial growth rate.
  • With a polynomial growth rate, a faster computer leads to a new problem size that is bigger by some factor multiplied by the original problem size that can done in the same amount of time.
  • But with an exponential growth rate, we only get an additive improvement.
  • Regardless of the value of tt, the machine that is 64 times faster can only do a problem size that is 6 larger in the same amount of time (because log64=6\log 64 = 6).
Suppose that a particular algorithm has time complexity T(n)=n2T(n) = n^2 and that executing an implementation of it on a particular machine takes tt seconds for nn inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in tt seconds?

  • If the slower computer does SS computations in time tt, then the faster computer does 64S64S computations in time tt.
  • Assume that the slower computer can solve a problem size of at most nn in time tt. This means it makes about n2=Sn^2 = S computations.
  • How much bigger size than nn can run in 64S64S, given that the growth rate of the algorithm on input size nn is T(n)=n2T(n) = n^2?
  • If n2Sn^2 \approx S, then T(8P)=(8P)264ST(8P) = (8P)^2 \approx 64S.

Suppose that a particular algorithm has time complexity T(n)=8nT(n) = 8n and that executing an implementation of it on a particular machine takes tt seconds for nn inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in tt seconds?

  • If the slower computer does SS computations in time tt, then the faster computer does 64S64S computations in time tt.
  • Assume that the slower computer can solve a problem size of at most nn in time tt. This means it makes about 8n=S8n = S computations.
  • How much bigger size than nn can run in 64S64S, given that the growth rate of the algorithm on input size nn is T(n)=8nT(n) = 8n?
  • If 8nS8n \approx S, then T(64n)=64*8n64ST(64n) = 64*8n \approx 64S.

2.11.3 Review questions: Running time

In this quiz you will give the complexity of some code fragments. Note that you should answer with the tightest possible growth factor, so it’s not correct if you answer O(n2)O(n^2) when the fragment is O(n)O(n).

Determine OO for the following code fragment. Assume that all variables are integers.

a = b + c
d = a + e
  • Does any line of code get executed more than once?

Determine OO for the following code fragment. Assume that all variables are integers.

sum = 0
for i = 0 to 2:
    for j = 0 to n-1:
        sum = sum + 1
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

sum = 0
for i = 0 to n*n-1:
    sum = sum + 1
  • How much work is done by the body of the inner for loop?
  • How many times is the for loop executed? Multiply this by the amount of work done by the body.

Determine OO for the following code fragment. Assume that all variables are integers.

for i = 0 to n-2:
    for j = i+1 to n-1:
        tmp = AA[i][j]
        AA[i][j] = AA[j][i]
        AA[j][i] = tmp
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

sum = 0
for i = 1 to n:
    j = 1
    while j <= n:
        sum = sum + 1
        j = j * 2
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

sum = 0
i = 1
while i <= n:
    for j = 1 to n:
        sum = sum + 1
    i = i * 2
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

Assume that array arr contains nn values, “random” takes constant time, and “sort” takes nlognn \log n time.

sum = 0
for i = 0 to n-1:
    for j = 0 to n-1:
        arr[j] = random(n)
    sort(arr)
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

Assume array arr contains a random permutation of the values from 0 to n1n-1.

sum = 0
for i = 0 to n-1:
    j = 0
    while arr[j] != i:
        sum = sum + 1
        j = j + 1
  • How much work is done by the body of the inner for loop?
  • How many times is the inner for loop executed? Multiply this by the amount of work done by the body.
  • How many times is the outer for loop executed? Multiply this by the amount of work done by the inner for loop.

Determine OO for the following code fragment. Assume that all variables are integers.

sum = 0
if EVEN(n):
    for i = 0 to n-1:
        sum = sum + 1
else:
    sum = sum + n
  • How much work is done by each branch of the if-then-else statement? Use the more expensive one.