Question 1

Which of the following is an example of a quadratic algorithm?

Accepted Answer

A)   An algorithm in which work grows as a square of the problem size.
B)   An algorithm in which work grows as a power of three each time the problem size increases.
C)   An algorithm in which work grows in direct proportion to the size of the problem.
D)   An algorithm in which work grows at a rate of n^k, where k is a constant greater than 1.E) None of the above
F) A) and C) A

Question 2

What would the constant k value in an O(k^n)  algorithm be for the Fibonacci sequence?

Accepted Answer

A)   0.83
B)   1.63
C)   3.14
D)   5.24E) C) and D)
F) A) and C) B

Question 3

When using the counting instructions method of measuring efficiency, what are the two classes of instructions you must distinguish between? (Choose two.)

Accepted Answer

A)   Instructions that perform assignment operations that can be combined.
B)   Instructions that are repeated more than once in the course of the algorithm.
C)   Instructions that execute the same number of times regardless of the problem size.
D)   Instructions whose execution count varies with the problem size.E) All of the above
F) B) and C)

Question 4

In terms of order of complexity, what is the best kind of performance to have?

Accepted Answer

A)   linear
B)   quadratic
C)   constant
D)   logarithmicE) None of the above
F) A) and D)

Question 5

What is the dominant term when evaluating the amount of work in an algorithm?

Accepted Answer

A)   When expressed as time vs. work performed, the dominant term is the area where the least amount of time is expended.
B)   When expressed as a matrix of related problems, the problem that is most significant becomes the dominant term.
C)   When expressed as a quadratic function, the dominant term is the statement in the algorithm where the fastest work is performed.
D)   When expressed as a polynomial, the dominant term of an algorithm is the area where the most work is performed.E) A) and D)
F) A) and B)

Question 6

Python's minimum function returns the minimum or smallest item in a list.

Accepted Answer

A) True 
 B)False

Question 7

An order of complexity that is worse than polynomial is called quadratic.

Accepted Answer

A) True 
 B)False

Question 8

What statement accurately describes the strategy utilized by the quicksort algorithm?

Accepted Answer

A)   The quicksort algorithm repeatedly swaps elements that are out of order in a list until they are completely sorted.
B)   The quicksort algorithm repeatedly swaps the smallest element in an unsorted portion of a list with an element at the start of the unsorted portion.
C)   The quicksort algorithm repeatedly inserts the i-th element into its proper place in the first i items in the list.
D)   The quicksort algorithm partitions a list around a pivot item and sorts the resulting sublists.E) C) and D)
F) B) and C)

Question 9

As the problem size gets larger, the performance of an algorithm with the higher order of complexity becomes worse more quickly.

Accepted Answer

A) True 
 B)False

Question 10

What type of analysis involves analyzing a polynomial wherein its value approaches or approximates that of its dominant term, as the size of the problem gets very large?

Accepted Answer

A)   quadratic analysis
B)   logarithmic analysis
C)   asymptotic analysis
D)   asynchronous analysisE) None of the above
F) All of the above

Question 11

Logarithmic complexity is better than constant but worse than linear complexity.

Accepted Answer

A) True 
 B)False

Question 12

How does the constant of proportionality for an algorithm differ from focusing on the dominant term in big-O analysis?

Accepted Answer

A)   The constant of proportionality involves terms and coefficients that are usually ignored during big-O analysis.
B)   The constant of proportionality attempts to calculate the computational cost of N = NP problems.
C)   The constant of proportionality focuses on the dominant term's effects on other parts of the algorithm, rather than focusing solely on the dominant term.
D)   The constant of proportionality involves the creation of a benchmark for items that contribute to the dominant term.E) B) and C)
F) A) and D)

Question 13

When choosing an algorithm, faster run times can often be achieved at the expense of what other resource?

Accepted Answer

A)   hard drive space
B)   processing power
C)   active memory
D)   interrupt requestsE) A) and B)
F) A) and D)

Question 14

What does the "O" in big-O notation stand for?

Accepted Answer

A)   The "O" stands for "on the order of," which is a reference to the order of complexity of the work of the algorithm.
B)   The "O" stands for "Organization of," which is a reference to the organization of complex functions at work in the algorithm.
C)   The "O" stands for "on the ontology of," which is a reference to the structure of the algorithm itself.
D)   The "O" stands for "on the openness of," which is a reference to the ability to discern from code how the algorithm functions.E) A) and B)
F) A) and C) A

Question 15

In asymptotic analysis, the value of a polynomial asymptotically approaches or approximates the value of its largest term as n becomes very large.

Accepted Answer

A) True 
 B)False

Question 16

Although recursive Fibonacci is elegant in its design, there is a less beautiful but much faster version that uses a loop to run in linear time.

Accepted Answer

A) True 
 B)False

Question 17

What two terms are used to refer to a search in which each value in a sequence is examined until a target value is found or the end of the sequence is reached?

Accepted Answer

A)   sequential search
B)   modular search
C)   linear search
D)   binary searchE) None of the above
F) A) and C)

Question 18

The performance of some algorithms depends on the placement of the data that are processed.

Accepted Answer

A) True 
 B)False

Question 19

When performing a thorough analysis of an algorithm's complexity, what two cases are of the most concern in general? (Choose two.)

Accepted Answer

A)   best case
B)   worst case
C)   average case
D)   mediocre caseE) B) and D)
F) A) and B)

Question 20

Which of the following is an example of a linear algorithm?

Accepted Answer

A)   An algorithm in which work grows exponentially in relation to the size of the problem.
B)   An algorithm in which work grows as a power of three each time the problem size increases.
C)   An algorithm in which work grows in direct proportion to the size of the problem.
D)   An algorithm in which work grows at a rate of n^k, where k is a constant greater than 1.E) B) and C)
F) A) and B)

Exam 11: Searching Sorting and Complexity Analysis

Which of the following is an example of a quadratic algorithm?

Correct AnswerverifiedA

What would the constant k value in an O(k^n) algorithm be for the Fibonacci sequence?

Correct AnswerverifiedB

When using the counting instructions method of measuring efficiency, what are the two classes of instructions you must distinguish between? (Choose two.)

Correct AnswerverifiedShow Answer

In terms of order of complexity, what is the best kind of performance to have?

Correct AnswerverifiedShow Answer

What is the dominant term when evaluating the amount of work in an algorithm?

Correct AnswerverifiedShow Answer

Python's minimum function returns the minimum or smallest item in a list.

Correct AnswerverifiedShow Answer

An order of complexity that is worse than polynomial is called quadratic.

Correct AnswerverifiedShow Answer

What statement accurately describes the strategy utilized by the quicksort algorithm?

Correct AnswerverifiedShow Answer

As the problem size gets larger, the performance of an algorithm with the higher order of complexity becomes worse more quickly.

Correct AnswerverifiedShow Answer

What type of analysis involves analyzing a polynomial wherein its value approaches or approximates that of its dominant term, as the size of the problem gets very large?

Correct AnswerverifiedShow Answer

Logarithmic complexity is better than constant but worse than linear complexity.

Correct AnswerverifiedShow Answer

How does the constant of proportionality for an algorithm differ from focusing on the dominant term in big-O analysis?

Correct AnswerverifiedShow Answer

When choosing an algorithm, faster run times can often be achieved at the expense of what other resource?

Correct AnswerverifiedShow Answer

What does the "O" in big-O notation stand for?

Correct AnswerverifiedA

In asymptotic analysis, the value of a polynomial asymptotically approaches or approximates the value of its largest term as n becomes very large.

Correct AnswerverifiedShow Answer

Although recursive Fibonacci is elegant in its design, there is a less beautiful but much faster version that uses a loop to run in linear time.

Correct AnswerverifiedShow Answer

What two terms are used to refer to a search in which each value in a sequence is examined until a target value is found or the end of the sequence is reached?

Correct AnswerverifiedShow Answer

The performance of some algorithms depends on the placement of the data that are processed.

Correct AnswerverifiedShow Answer

When performing a thorough analysis of an algorithm's complexity, what two cases are of the most concern in general? (Choose two.)

Correct AnswerverifiedShow Answer

Which of the following is an example of a linear algorithm?

Correct AnswerverifiedShow Answer

Correct Answer
verified
A

Correct Answer
verified
B

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
A

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified