Chapter 24 - Developing Efficient Algorithms

Question 1

What is the problem with measuring algorithm efficiency by testing the running time of the programs?

Answer 1

1. Many tasks run concurrently on a computer. The execution time of a particular program depends on the system load.
2. The execution time depends on specific input. Consider, for example, linear search and binary search. If an element to be searched happens to be the first in the list, linear search will find the element quicker than binary search.

Question 2

What is “the big O notation”?

Answer 2

Computer scientists use the Big O notation to represent the “order of magnitude”. Using this notation, the complexity of the linear search algorithm is O(n), pronounced as “order of n”.

Question 3

What do we measure algorithm efficiency by?

Answer 3

We measure their growth rates in relation to input growth/size.

Question 4

What is best-case input and worst-case input?

Answer 4

An input that results in the shortest execution time possible is called the best-case input.
An input that results in the longest execution time possible is called the worst-case input.

Question 5

What are best-case and worst-case analysis good for?

Answer 5

They are not representative, but worst-case analysis is very useful, because you can be assured that the algorithm will never be slower than the worst case.

Question 6

What is average-case analysis?

Answer 6

Average-case analysis attempts to determine the average amount of time among all possible inputs of the same size. Average-case analysis is ideal, but difficult to perform, because for many problems it is hard to determine the relative probabilities and distributions of various input instances. Worst-case analysis is easier to perform, so the analysis is generally conducted for the worst case.

Question 7

The linear search algorithm requires n comparisons in the worst case and n/2 comparisons in the average case if you are nearly always looking for something known to be in the list.
Using the Big O notation, what are the algorithmic complexity of n and n/2 respectively?

Answer 7

Both cases require O(n) time. The multiplicative constant (1/2) can be omitted. Algorithm analysis is focused on growth rate. The multiplicative constants have no impact on growth rates. The growth rate for n/2 or 100n is the same as for n.

Question 8

When do we need algorithm analysis?

Answer 8

When there’s a possibility for large input sizes we should perform algorithm analysis. If the input size is small, there is no significance in estimating an algorithm’s efficiency.

Question 9

What is the complexity of an algorithm that takes n - 1 time to execute?

Answer 9

The Big O notation allows you to ignore the nondominating part (e.g., -1 in the expression n - 1) and highlight the important part (e.g., n in the expression n - 1). Therefore, the complexity of this algorithm is O(n).

Question 10

What is meant by “complexity of contant time”?

Answer 10

The Big O notation estimates the execution time of an algorithm in relation to the input size. If the time is not related to the input size, the algorithm is said to take constant time with the notation O(1). For example, a method that retrieves an element at a given index in an array takes constant time, because the time does not grow as the size of the array increases.

Question 11

What is the algorithmic complexity of.
1+2+3+…+(n-2)+(n-1) = (n(n-1))/2
?

Answer 11

O(n^2)

Question 12

Consider the time complexity for the following loop:

for (i = 1, i

Answer 12

It is a constant time, c, for executing
k = k + 5;
Since the loop is executed n times, the time complexity for the loop is
T(n) = (a constant c) * n = O(n)

Question 13

What is a quadratic algorithm?

Answer 13

An algorithm with the O(n^2) time complexity is called a quadratic algorithm. The quadratic algorithm grows quickly as the problem size increases. If you double the input size, the time for the algorithm is quadrupled. Algorithms with a nested loop are often quadratic.

Question 14

What is the time complexity of the following selection statement?
if ( list.contains(e)) {
-   System.out.println(e);
}
else
-   for (Object t: list) {
-   System.out.println(t);
-   }

Answer 14

Suppose the list contains n elements. The execution time for list.contains(e) is O(n). The loop in the else clause takes O(n) time. Hence, the time complexity for the entire statement is
T(n) = if test time + worst-case time(if clause, else clause)
= O(n) + O(n) = O(n)

Question 15

Consider the computation of a^n for an integer n. A simple algorithm would multiply a n times, as follows:
result = 1;
for (int i = 1; i

Answer 15

The algorithm takes O(n) time. Without loss of generality, assume n = 2^k. You can improve the algorithm using the following scheme:
result = a;
for (int i = 1; i

Question 16

What is a logarithmic algorithm?

Answer 16

An algorithm with the O(log(n)) time complexity is called a logarithmic algorithm. The logarithmic algorithm grows slowly as the problem size increases. If you square the input size of any logarithmic time algorithm, you only double the time of execution. So a logarithmic-time algorithm is very efficient.

Question 17

What is an exponential algorithm?

Answer 17

An algorithm with O(2^n) time complexity is called an exponential algorithm. As the input size increases, the time for the exponential algorithm grows exponentially. Exponential algorithms are not practical for large input sizes.
The Tower of Hanoi algorithm is exponential. Suppose the disk is moved at a rate of 1 per second. It would take 136 years to move 32 disks, and 585 billion years to move 64 disks.

Question 18

What is dynamic programming?

Answer 18

Dynamic programming is the process of solving subproblems that overlap, then combining the solutions of the subproblems to obtain an overall solution.
The key idea behind dynamic programming is to solve each subproblem only once and store the results for subproblems for later use to avoid redundant computing of the subproblems.

Question 19

What is a brute-force algorithm?

Answer 19

Brute force refers to an algorithmic approach that solves a problem in the simplest or most direct or obvious way. As a result, such an algorithm can end up doing far more work to solve a given problem than a cleverer or more sophisticated algorithm might do. On the other hand, a brute-force algorithm is often easier to implement than a more sophisticated one and, because of this simplicity, sometimes it can be more efficient.

Question 20

Is there any practical considerations when comparing two algorithms of equal time complexity?

Answer 20

The Big O notation provides a good theoretical estimate of algorithm efficiency. However, two algorithms of the same time complexity are not necessarily equally efficient.

Question 21

What is the divide-and-conquer approach?

Answer 21

The divide-and-conquer approach divides the problem into subproblems, solves the subproblems, then combines the solutions of the subproblems to obtain the solution for the entire problem. Unlike the dynamic programming approach, the subproblems in the divide-and-conquer approach don’t overlap. A subproblem is like the original problem with a smaller size, so you can apply recursion to solve the problem.

Question 22

What is the backtracking approach?

Answer 22

Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options.
The backtracking approach searches for a candidate solution incrementally, abandoning that option as soon as it determines that the candidate cannot possibly be a valid solution, and then looks for a new candidate.

Question 23

What is computational geometry?

Answer 23

Computational geometry is to study the algorithms for geometrical problems. It has applications in computer graphics, games, pattern recognition, image processing, robotics, geographical information systems, and computer-aided design and manufacturing.

Question 24

Estimating algorithm efficiency is ___

A. to measure their actual execution time.
B. to estimate their execution time.
C. to estimate their growth function.

Answer 24

C. to estimate their growth function.

Question 25

Which of the following complexity is O(nlogn)

A. 300n + 400nn
B. 23nlogn + 50
C. 45n + 45nlogn + 503
D. nn*n + nlogn

Answer 25

B and C are correct

Question 26

What is the number of iterations in the following loop:

int count = 5;
while (count

Answer 26

The correct answer is E
Explanation: Consider n = 5, 0 iteration. Consider n = 6, 1 iteration. Consider n = 7, 1 iteration. Consider n = 8, 1 iteration. Consider n = 9, 2 iterations. Consider n = 10, 2 iterations. Consider n = 11, 2 iterations. Consider n = 12, 3 iterations. Consider n = 13, 3 iterations. Consider n = 14, 3 iterations. Consider n = 15, 4 iterations. (ceiling((15-5)/3) = 4.

Question 27

For a sorted list of 1024 elements, a binary search takes at most ___ comparisons. Note that to check whether an element is greater than, equal to, or less than the other element is considered as one comparison here.

A. 11
B. 100
C. 512
D. 6

Answer 27

A. 11.

Question 28

O(1) is __

A. constant time
B. logarithmic time
C. linear time
D. log-linear time

Answer 28

A. constant time

Question 29

The time complexity for the selection sort algorithm in the text is __

A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)

Answer 29

B. O(n^2)

Question 30

The time complexity for the insertion sort algorithm in the text is ___

A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)

Answer 30

B. O(n^2)

Question 31

The time complexity for the recursive Fibnacci algorithm in the text is __

A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)

Answer 31

D. O(2^n)

Question 32

The time complexity for the Euclid?s algorithm is __

A. O(n)
B. O(n^2)
C. O(logn)
D. O(2^n)

Answer 32

C. O(logn)

Question 33

The time complexity for the Sieve of Eratosthenes algorithm is __

A. O(n)
B. O(n^(1.5)/logn)
C. O(logn)

Answer 33

B. O(n^(1.5)/logn)

Question 34

The time complexity for the the closest pair of points problem using divide-and-conquer is __

A. O(n)
B. O(nlogn)
C. O(logn)
D. O(2^n)

Answer 34

B. O(nlogn)

Question 35

The gift-wrapping algorithm for finding a convex hull takes __

A. O(n)
B. O(nlogn)
C. O(logn)
D. O(n^2)

Answer 35

D. O(n^2)

Question 36

The Graham’s algorithm for finding a convex hull takes ___

A. O(n)
B. O(nlogn)
C. O(logn)
D. O(n^2)

Answer 36

B. O(nlogn)