Deck 3: The Efficiency of Algorithms

Question 1

Sequential search is an order-n algorithm in the average case.

Answer 1

True

Question 2

No one has yet found a solution algorithm that works in polynomial time, but neither has anyone proved that such an algorithm does not exist.

Answer 2

True

Question 3

The selection sort algorithm can recognize whether or not the list is already sorted at the beginning.

Answer 3

False

Question 4

The study of the efficiency of algorithms is called the ____ of algorithms.

A) design
B) analysis
C) implementation
D) testing

Question 5

If we were to run the sequential search algorithm many times, with random input values occurring at various places in the list, we would find the average number of comparisons done to be approximately n/2.

Question 6

First and foremost, we expect elegance from our algorithms._________________________

Question 7

With sequential search, the bigger the list of items, the more work that must be done to search it._________________________

Question 8

In the sequential search algorithm, the worst case occurs when the value being searched for is the first value in the list._________________________

Question 9

In the sequential search algorithm, the minimum amount of work is done if the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last

Question 10

A collection of nodes and connecting edges is called a(n) vector._________________________

Question 11

The properties that make better algorithms are very similar to the properties we look for when purchasing a car.

Question 12

____ involves the fixing of errors that are uncovered through repeated usage with different input values.

A) Program maintenance
B) Recycling
C) Data cleanup
D) Garbage collection

Question 13

If an Θ(n2) algorithm and an Θ(n) algorithm exist for the same task, then for large enough n, the Θ(n2) algorithm does more work and takes longer to execute, regardless of the constant factors for peripheral work.

Question 14

The sequential search and selection sort algorithms are different methods to get the same thing done.

Question 15

The shuffle-left algorithm is not space-efficient._________________________

Question 16

____ are useful for rating one machine against another and for rating how sensitive a particular algorithm is with respect to variations in input on one particular machine.

A) Time trials
B) Benchmarks
C) Comparison times
D) Intensive tests

Question 17

The time an algorithm takes on a particular machine is the best way for comparing two algorithms that do the same task.

Question 18

Given a sorted list, the sequential search algorithm is more efficient than the binary search.

Question 19

____ is the algorithmic equivalence of style.

A) Efficiency
B) Elegance
C) Aesthetics
D) Complexity

Question 20

Binary search uses significantly more space than sequential search.

Question 21

Sequential search is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)

Question 22

The worst case in binary search occurs ____.

A) when the object to be searched is in the middle of the list
B) when the object to be searched is at the end of the list
C) when the object to be searched is at the beginning of the list
D) when the object to be searched is not in the list

Question 23

The ____ sort algorithm performs the task of sorting a list by growing a sorted subsection of the list from the back to the front.

A) selection
B) sequential
C) shuffle-left
D) binary

Question 24

The copy-over algorithm is ____ in time efficiency in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)

Question 25

An ____ algorithm is called an exponential algorithm.

A) Θ(lg n)
B) Θ(n)
C) Θ(n2)
D) Θ(2n)

Question 26

Part of the job of program ____ is to make clear any assumptions or restrictions about the input size the program was designed to handle.

A) design
B) implementation
C) documentation
D) maintenance

Question 27

The converging-pointers algorithm is Θ(n) in the ____________________ case.

Question 28

In the sequential search algorithm, the worst case occurs when the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last

Question 29

Binary search does ____ comparisons in the worst case.

A) Θ(1)
B) Θ(lg n)
C) Θ(n)
D) Θ(n2)

Question 30

The shuffle-left algorithm is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)

Question 31

____________________ is the term to describe an algorithm's careful use of resources.

Question 32

A(n) ____________________ is a path through a graph that begins and ends at the same node and goes through all other nodes exactly once.

Question 33

The ____ case of an algorithm requires the least work.

A) best
B) worst
C) smallest
D) largest

Question 34

____________________ problems are solvable, but the solution algorithms all require so much work as to be virtually useless.

Question 35

Θ(lg n), Θ(n) and Θ(n2) are ____ in the amount of work they do as n increases.

A) restricted
B) useful
C) polynomially bounded
D) exponential

Question 36

Problems for which no known polynomial solution algorithm exists are sometimes approached via ____ algorithms.

A) alternative
B) intractable
C) polynomial
D) approximation

Question 37

The number of comparisons done by the selection sort algorithm does not grow at the same rate as the problem size n, instead it grows at approximately the ____________________ of that rate.

Question 38

Placing a list of items into alphabetical or numerical order is called ____.

A) simplifying
B) searching
C) sorting
D) pattern matching

Question 39

Selection sort is a(n) ____ algorithm in all cases.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)

Question 40

A surprising number of problems fall into the "____" category.

A) suspected intractable
B) approximation algorithm
C) bin-packing
D) declared intractable

Question 41

If an algorithm is more time efficient and less space efficient, what is this called?

Question 42

Discuss at length the measurement of the time and space consumed by an algorithm in order to determine its efficiency.

Question 43

Explain the sentence: The selection sort algorithm not only does comparisons; it also does exchanges.

Question 44

How do you approach problems for which no known polynomial solution algorithm exists?

Question 45

Explain the term "brute force" as it applies to algorithms.

Question 46

Given the data cleanup problem described in the text, write the pseudocode for the converging-pointers algorithm for data cleanup.

Question 47

What is the definition of order of magnitude n?

Question 48

Discuss at length both the best and worst case of the pattern-matching algorithm.

Question 49

Discuss at length the "people aspect" of the practical considerations for the development of algorithms.Include the concepts of program maintenance and ease of understanding in your response.

Question 50

What is the logarithm of n to the base 2?