Deck 3: The Efficiency of Algorithms

Question 1

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

Answer 1

False

Question 2

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

Answer 2

True

Question 3

____ 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

Answer 3

A

Question 4

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.

Question 5

Binary search uses significantly more space than sequential search.

Question 6

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 7

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

Question 8

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

Question 9

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

Question 10

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

Question 11

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

Question 12

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 13

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

Question 14

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

Question 15

____ is the algorithmic equivalence of style.

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

Question 16

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

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

Question 17

____ 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 18

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

Question 19

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

Question 20

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

Question 21

The ____ case of an algorithm requires the least work.

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

Question 22

Binary search does ____ comparisons in the worst case.

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

Question 23

An ____ algorithm is called an exponential algorithm.

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

Question 24

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

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

Question 25

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

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

Question 26

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 27

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

Question 28

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 29

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

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

Question 30

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

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

Question 31

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 32

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 33

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

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

Question 34

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

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

Question 35

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 36

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

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

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

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

Question 40

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

Question 41

What is the definition of order of magnitude n?

Question 42

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 43

What is the logarithm of n to the base 2?

Question 44

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

Question 45

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

Question 46

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

Question 47

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

Question 48

Discuss at length how binary search operates.

Question 49

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

Question 50

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