Chapter 22

Question 1

Analyzing algorithm efficiency is ________.

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

Answer 1

C.

to estimate their growth function

Question 2

An input that results in the shortest execution time is called the _____________.

	A.
best-case input
	B.
worst-case input
	C.
average-case input

Answer 2

A.

best-case input

Question 3

On an average, linear search searches

	A.
the whole list
	B.
half of the list
	C.
just one element in the list
	D.
one fourth of the list

Answer 3

B.

half of the list

Question 4

What is the number of iterations in the following loop:

intcount =5;
while(count < n) {
count = count +3;
}
	A.
n - 5
	B.
n - 3
	C.
n / 3 - 1
	D.
(n - 5) / 3
	E.
the ceiling of (n - 5) / 3

Answer 4

E.

the ceiling of (n - 5) / 3

Question 5

For a sorted list of 1024 elements, a binary search takes at most _______ comparisons.

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

Answer 5

A.

11

Question 6

O(1) is \_\_\_\_\_\_\_\_.
	A.
constant time
	B.
logarithmic time
	C.
linear time
	D.
log-linear time

Answer 6

A.

constant time

Question 7

The time complexity for the Towers of Hanoi algorithm in the text is ________.

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

Answer 7

D.

O(2^n)

Question 8

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 8

B.

O(n^2)

Question 9

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 9

B.

O(n^2)

Question 10

______________ approach is the process of solving subproblems, then combining the solutions of the subproblems to obtain an overall solution. This naturally leads to a recursive solution. However, it would be inefficient to use recursion, because the subproblems overlap. 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.

	A.
Divide-and-conquer
	B.
Dynamic programming
	C.
Brutal-force
	D.
Backtracking

Answer 10

B.

Dynamic programming

Question 11

The time complexity for the recursive Fibonacci algorithm in the text is ________.

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

Answer 11

D.

O(2^n)

Question 12

The time complexity for the algorithm using the dynamic programming approach is ________.

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

Answer 12

A.

O(n)

Question 13

The time complexity for the Euclid?s algorithm is ________.

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

Answer 13

C.

O(logn)

Question 14

The time complexity for the Sieve of Eratosthenes algorithm is ________.

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

Answer 14

B.

O(n^(1.5)/logn)

Question 15

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 15

B.

O(nlogn)

Question 16

______________ 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 ________ 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.

	A.
Divide-and-conquer/dynamic programming
	B.
Dynamic programming/divide-and-conquer
	C.
Brutal-force/divide-and-conquer
	D.
Backtracking/dynamic programming

Answer 16

A.

Divide-and-conquer/dynamic programming

Question 17

The ________ 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.

	A.
Divide-and-conquer
	B.
Dynamic programming
	C.
Brutal-force
	D.
Backtracking

Answer 17

D.

Backtracking

Question 18

The gift-wrapping algorithm for finding a convex hull takes ______________ time.

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

Answer 18

D.

O(n^2)

Question 19

The Graham?s algorithm for finding a convex hull takes ______________ time.

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

Answer 19

B.

O(nlogn)