Deck 11: Searching Sorting and Complexity Analysis

Question 1

Whenever the amount of work of an algorithm is expressed as a polynomial, we focus on one term as dominant.

Answer 1

True

Question 2

Python's is operator is implemented as a method named __contains__ in the list class.

Answer 2

False

Question 3

Binary search is less efficient than linear search.

Answer 3

False

Question 4

Algorithms with linear behavior do less work than algorithms with quadratic behavior for most problem sizes n.

Question 5

When analyzing an algorithm, one must be careful to determine that any instructions do not hide a loop that depends on a variable problem size.

Question 6

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

Question 7

When you count instructions to estimate the efficiency of an algorithm, you count the instructions in the executable machine language program.

Question 8

Algorithms describe processes that run on real computers with finite resources.

Question 9

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

Question 10

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

Question 11

The constant of proportionality involves the terms and coefficients that are usually ignored during big-O analysis.

Question 12

An algorithm coded in Python usually runs slightly faster than the same algorithm coded in C.

Question 13

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

Question 14

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

Question 15

The time() function of the time module can be used to track the running time of a program.

Question 16

Some algorithms require more memory as the problem size gets larger.

Question 17

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

Question 18

A binary search is necessary for data that are not arranged in any particular order.

Question 19

Sequential search is also called polynomial search.

Question 20

In general, we worry more about average and best-case performances than about worst-case performances.

Question 21

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

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.

Question 22

Selection sort starts at the beginning of the list and compares pairs of data items as it moves down to the end.

Question 23

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

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.

Question 24

What function can you use to record the start and end times of a block of code, and then use the difference between the resulting values to determine the elapsed time in seconds?

A) time.ctime()
B) time.time()
C) time.count()
D) time.epoch()

Question 25

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

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.

Question 26

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?

A) sequential search
B) modular search
C) linear search
D) binary search

Question 27

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

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.

Question 28

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

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.

Question 29

Bubble sort's worst-case behavior for exchanges is greater than linear.

Question 30

Of the numerous sorting algorithms, what algorithm employs a recursive, divide-and-conquer strategy that breaks a list in two at the middle point and recursively sorts the lists?

A) quicksort
B) insertion sort
C) bubble sort
D) merge sort

Question 31

What statement accurately describes the strategy utilized by the selection sort algorithm?

A) The selection sort algorithm repeatedly swaps elements that are out of order in a list until they are completely sorted.
B) The selection sort 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 selection sort algorithm repeatedly inserts the i-th element into its proper place in the first i items in the list.
D) The selection sort algorithm partitions a list around a pivot item and sorts the resulting sublists.

Question 32

O(n log n) running times are better than O(n^2) running times.

Question 33

What is NOT one of the three Python functions that are associated with the merge sort algorithm?

A) mergeSort
B) mergeSortHelper
C) merge
D) mergeSplit

Question 34

Of the techniques that can be used to determine the efficiency of an algorithm, which is based on a calculated average of average run time?

A) benchmarking
B) instruction counting
C) set analyzing
D) process profiling

Question 35

What statement accurately describes the strategy utilized by the bubble sort algorithm?

A) The bubble sort algorithm repeatedly swaps elements that are out of order in a list until they are completely sorted.
B) The bubble sort 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 bubble sort algorithm repeatedly inserts the i-th element into its proper place in the first i items in the list.
D) The bubble sort algorithm partitions a list around a pivot item and sorts the resulting sublists.

Question 36

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.

Question 37

The first two numbers in the Fibonacci sequence are 1 and 2.

Question 38

Python's in operator is implemented as a method by what name in the list class?

A) __in__
B) __contains__
C) __present__
D) __within__

Question 39

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

A) linear
B) quadratic
C) constant
D) logarithmic

Question 40

What statement accurately describes the strategy utilized by the insertion sort algorithm?

A) The insertion sort algorithm repeatedly swaps elements that are out of order in a list until they are completely sorted.
B) The insertion sort 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 insertion sort algorithm repeatedly inserts the i-th element into its proper place in the first i items in the list.
D) The insertion sort algorithm partitions a list around a pivot item and sorts the resulting sublists.

Question 41

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

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.

Question 42

What are the two major problems with the benchmark technique of measuring algorithm efficiency?

A) Different hardware platforms have different processing speeds, meaning the running times will differ.
B) A benchmark test does not account for differences in the size of data sets.
C) The test cannot be performed without modifying the code for which the benchmark will be performed on.
D) It can be impractical to determine the running time for algorithms with very large data sets.

Question 43

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

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.

Question 44

The insertion, bubble, and selection sort algorithms are all examples of algorithms that have what big-O notation run times?

A) O(n log n)
B) O(n^n)
C) O(n**2)
D) O(n**3)

Question 45

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

A) 0.83
B) 1.63
C) 3.14
D) 5.24

Question 46

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

A) hard drive space
B) processing power
C) active memory
D) interrupt requests

Question 47

The process of determining the running time and memory cost of an algorithm by reading the code and creating a mathematical formula expressing this cost is known by what term?

A) pattern analysis
B) complexity analysis
C) cost analysis
D) micro analysis

Question 48

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

A) best case
B) worst case
C) average case
D) mediocre case

Question 49

What statement regarding the development of fast algorithms is accurate?

A) As a rule, any reduction in the order of magnitude of complexity is preferable to a tweak in code that reduces the constant of proportionality.
B) As a rule, any reduction in the constant of proportionality is preferable to a tweak that reduces the order of magnitude in complexity.
C) As a rule, any reduction in the lines of code required to make an algorithm function is desirable to that of faster run times.
D) As a rule, any reduction in the use of memory required by an algorithm is preferred over a tweak that improves run times.

Question 50

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?

A) quadratic analysis
B) logarithmic analysis
C) asymptotic analysis
D) asynchronous analysis

Question 51

What programming technique involves saving intermediate values when they are computed so they can be reused when they are needed again?

A) memoization
B) prioritization
C) amortization
D) memorization