3.9* Review
This final section contains some review questions about the contents of this chapter.
3.9.1 Quiz: Introduction to algorithm analysis
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.
3.9.2 Quiz: 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 n in one hour, what size input can XYZ’s computer execute in one hour for an algorithm whose growth rate is n^2?
- If the XYZ Corp. computer runs 100 times faster, then if the Prunes computer does S computations in an hour, the XYZ Corp. computer does 100S computations in an hour.
- Assume that the Prunes computer can solve a problem size of at most P in an hour. This means it makes about P^2 = S computations.
- How much bigger size than P can run in 100S, given that the growth rate of the algorithm on input size P is T(P) = P^2?
- If P \approx S, then T(10P) = (10P)^2 \approx 100S.
Suppose that a particular algorithm has time complexity T(n) = 3 \times 2^n and that executing an implementation of it on a particular machine takes t seconds for n 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 t 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 t, the machine that is 64 times faster can only do a problem size that is 6 larger in the same amount of time (because \log(64) = 6).
- If the slower computer does S computations in time t, then the faster computer does 64S computations in time t.
- Assume that the slower computer can solve a problem size of at most n in time t. This means it makes about n^2 = S computations.
- How much bigger size than n can run in 64S, given that the growth rate of the algorithm on input size n is T(n) = n^2?
- If n^2 \approx S, then T(8P) = (8P)^2 \approx 64S.
Suppose that a particular algorithm has time complexity T(n) = 8n and that executing an implementation of it on a particular machine takes t seconds for n 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 t seconds?
- If the slower computer does S computations in time t, then the faster computer does 64S computations in time t.
- Assume that the slower computer can solve a problem size of at most n in time t. This means it makes about 8n = S computations.
- How much bigger size than n can run in 64S, given that the growth rate of the algorithm on input size n is T(n) = 8n?
- If 8n \approx S, then T(64n) = 64*8n \approx 64S.
3.9.3 Quiz: 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(n^2) when the fragment is O(n).
Determine O 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 O for the following code fragment. Assume that all variables are integers.
sum = 0
for i in 0 .. 2:
for j in 0 .. n-1:
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 O for the following code fragment. Assume that all variables are integers.
sum = 0
for i in 0 .. n*n-1:
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 O for the following code fragment. Assume that all variables are integers.
for i in 0 .. n-2:
for j in i+1 .. 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 O for the following code fragment. Assume that all variables are integers.
sum = 0
for i in 1 .. n:
j = 1
while j <= n:
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 O for the following code fragment. Assume that all variables are integers.
sum = 0
i = 1
while i <= n:
for j in 1 .. n:
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 O for the following code fragment. Assume that all variables are integers.
Assume that array arr contains n values, “random” takes constant time, and
“sort” takes n \log(n) time.
sum = 0
for i in 0 .. n-1:
for j in 0 .. 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 O for the following code fragment. Assume that all variables are integers.
Assume array arr contains a random permutation of the
values from 0 to n-1.
sum = 0
for i in 0 .. n-1:
j = 0
while arr[j] != i:
sum += 1
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 O for the following code fragment. Assume that all variables are integers.
sum = 0
if EVEN(n):
for i in 0 .. n-1:
sum += 1
else:
sum += n- How much work is done by each branch of the if-then-else statement? Use the more expensive one.