Deck 3: The Efficiency of Algorithms

Question 1

With sequential search, the smaller the list of items, the less work must be done to search it. _________________________

Answer 1

True

Question 2

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

Answer 2

True

Question 3

Binary search is able to search any kind of list, regardless of whether or not it is sorted.

Answer 3

False

Question 4

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

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 6

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

Question 7

Time algorithms taken across multiple machines is the best way for comparing two algorithms that do the same task.

Question 8

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 9

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

Question 10

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

____ is the algorithmic equivalence of miles per gallon or use of space in cars.

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

Question 12

The things we look for in a new car are similar to the things we look for in a good algorithm.

Question 13

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

Question 14

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

Question 15

Binary search uses significantly more space than sequential search.

Question 16

First and foremost, we expect ease of understanding from our algorithms. _________________________

Question 17

It is well known that solution algorithms that work in polynomial do exist.

Question 18

The shuffle-left algorithm is not space efficient. _________________________

Question 19

The study of the _______ of algorithms is called the analysis of algorithms.

A)design
B)efficiency
C)implementation
D)complexity

Question 20

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

Question 21

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

Question 22

The selection sort algorithm performs the task of sorting a list by growing a sorted subsection of the list from the _____ to the _____.

A)front / back
B)top / bottom
C)back / front
D)lowest / highest

Question 23

An ____ algorithm is called an exponential algorithm.

A)Θ(lg n )
B)Θ( n )
C)Θ( n ²)
D)Θ(2 ⁿ )

Question 24

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

Question 25

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 26

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 27

The shuffle-left algorithm is an ____ algorithm in the worst case.

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

Question 28

The ____ case of an algorithm requires the least work.

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

Question 29

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 30

A Hamiltonian circuit is a path through a graph that begins and ends at the same node and goes through all other nodes exactly ________.

Question 31

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

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

Question 32

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

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

Question 33

_______ sort is an Θ( n ²)algorithm in all cases.

A)Selection
B)Shuffle
C)Sequential
D)Shuffle-left

Question 34

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

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

Question 35

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

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

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

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

Question 38

Binary search does ____ comparisons in the worst case.

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

Question 39

Sequential search is an ____ algorithm in the worst case.

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

Question 40

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

A)binary
B)bubble
C)shuffle
D)sequential

Question 41

What is the logarithm of n to the base 2?

Question 42

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

Question 43

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

Question 44

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

Question 45

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 46

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

Question 47

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

Question 48

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

Question 49

What is the definition of order of magnitude n?

Question 50

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