Deck 3: The Efficiency of Algorithms

Question 1

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

Answer 1

False

Question 2

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 that the loop is executed approximately n times.

Answer 2

False

Question 3

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

Answer 3

False

Question 4

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 5

The shuffle-left algorithm is not space-efficient.

Question 6

Of all the desirable properties for algorithms, efficiency is the most easily quantifiable.

Question 7

Ease of understanding, elegance, efficiency, and correctness are all characteristics of a good algorithm.

Question 8

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

Question 9

A computer program is often written to be used only once to solve a single instance of a problem.

Question 10

The brute-force bin-packing algorithm is very useful.

Question 11

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

Question 12

Binary search uses significantly more space than sequential search.

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

Anything that varies as a constant times n is said to be of order of magnitude n.

Question 15

The time/space tradeoff is the choice between algorithms where you gain something while giving up something else.

Question 16

It is sufficient for an algorithm to provide correct results for only the input values that we expect are the most likely to occur.

Question 17

The selection sort algorithm does exchanges, in addition to comparisons.

Question 18

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

Question 19

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

Question 20

Elegance is the first and foremost expectation of a proper algorithm.

Question 21

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

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

Question 22

Some algorithms must do work that is not polynomially bounded.

Question 23

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

Question 24

An ____ algorithm is called an exponential algorithm.

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

Question 25

The Hamiltonian problem is suspected to be intractable.

Question 26

The binary search algorithm is ____ in the worst case.

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

Question 27

A collection of sets and vectors is called a graph.

Question 28

The ____ case of an algorithm requires the minimum amount of work.

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

Question 29

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

A) Resourcefulness
B) Time-Space Tradeoff
C) Effectiveness
D) Efficiency

Question 30

The converging-pointers algorithm is ____ in the best case.

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

Question 31

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 32

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

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

Question 33

____ is the algorithmic equivalence of style.

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

Question 34

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

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

Question 35

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 36

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

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

Question 37

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

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

Question 38

The number of times a number n can be divided by 2 and not go below 1 is called the logarithm of n to the base 3.

Question 39

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 40

____ is the fixing of errors uncovered through repeated use of an algorithm.

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

Question 41

____ algorithms are an alternative approach for problems which no known polynomial solution algorithm exists.

A) Alternative
B) Intractable
C) Polynomial
D) Approximation

Question 42

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 43

A ____ is a path through a graph that begins and ends on the same node and goes through every node exactly once.

A) Newtonian loop
B) McCarthian path
C) Hamiltonian circuit
D) complete trip

Question 44

When does the worst case in binary search occur?

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 45

The process of timing an algorithm using the same machine but searching for different items is called ____.

A) time trials
B) benchmarking
C) comparison timing
D) intensive testing

Question 46

What is the unit of work in the data cleanup algorithm?

A) comparisons and exchanges
B) comparisons only
C) examinations and copies
D) character comparisons

Question 47

Why would an exponential algorithm be useless with a large input, n?

A) It would take too long to compute
B) It would take too much space
C) It would not be correct
D) It would not be elegant

Question 48

The problem of placing objects in alphabetical or numerical order is called ____.

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

Question 49

An algorithm with order of magnitude Q (n²) grows at the ____ of the rate of the problem size n.

A) square
B) cube
C) logarithm
D) fraction

Question 50

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