Question 1

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.

Accepted Answer

A linear algorithm is one in which the amount of time it takes to complete the algorithm grows in direct proportion to the size of the problem. This means that as the problem size doubles, the amount of work required also doubles. Choice C describes an algorithm that grows linearly, while the other choices describe algorithms that grow either exponentially or as a power of a constant.

Question 2

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

Accepted Answer

Selection sort works by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. It does not compare pairs of data items as it moves down the list; instead, it selects the smallest (or largest, depending on sorting order) element from the unsorted section and swaps it with the element at the beginning of the unsorted section.

Question 3

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.

Accepted Answer

The "O" in big-O notation stands for "on the order of," which is a reference to the order of complexity of the work of the algorithm.

Question 4

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()

Accepted Answer

We can use the time.time() function to record the start and end times of a block of code and then subtract the resulting values to determine the elapsed time in seconds. This function returns the current time in seconds since the epoch as a floating-point value, which can be used for timing purposes.

Question 5

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.

Accepted Answer

A quadratic algorithm is one in which the amount of work required grows as a square of the problem size. This is represented by an equation of the form f(n) = n^2, where n is the size of the problem input. Option A describes this type of algorithm, while the other options describe algorithms with different growth rates.

Question 6

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

Accepted Answer

Sequential search and linear search both refer to the process of examining each value in a sequence one by one until the target value is found or the end of the sequence is reached.

Question 7

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.

Accepted Answer

The quicksort algorithm partitions the list around a pivot item and sorts the resulting sublists. It chooses a pivot element and divides the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The sub-lists are then sorted recursively.

Question 8

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.

Accepted Answer

When expressed as a polynomial, the dominant term of an algorithm is the area where the most work is performed. This is because the dominant term has the highest degree and therefore has the largest impact on the overall runtime of the algorithm. By focusing on reducing the work done in this dominant term, the algorithm can be optimized and made more efficient.

Question 9

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

Accepted Answer

Bubble sort has a worst-case time complexity of O(n^2) which means that the number of comparisons and exchanges required to sort an array increases exponentially as the input size increases. Therefore, the worst-case behavior for exchanges is greater than linear.

Question 10

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

Accepted Answer

Merge sort is the sorting algorithm that employs a recursive, divide-and-conquer strategy to sort a list by breaking it into two halves, sorting each half individually and then merging them back together to form the final sorted list. It has a time complexity of O(n log n) and is considered efficient for large data sets. Quick sort also employs a similar divide-and-conquer strategy but has a worst-case time complexity of O(n^2) which makes it less efficient. Insertion sort and bubble sort have a time complexity of O(n^2) which makes them less efficient than merge sort for large data sets.

Question 11

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.

Accepted Answer

The selection sort algorithm selects the smallest element in an unsorted portion of a list and swaps it with an element at the start of the unsorted portion until the entire list is sorted. This is known as a selection process, hence the name "selection" sort.

Question 12

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

Accepted Answer

O(n log n) running times are more efficient than O(n^2) running times, as the former grows at a slower rate with increasing input size compared to the latter. Therefore, we can conclude that O(n log n) algorithms are generally better than O(n^2) algorithms.

Question 13

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

Accepted Answer

There are three Python functions that are commonly associated with the merge sort algorithm: mergeSort, mergeSortHelper, and merge. "mergeSplit" is not a valid function used in merge sort algorithm.

Question 14

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

Accepted Answer

Benchmarking involves running the algorithm multiple times and calculating the average run time, which is based on a calculated average. Instruction counting involves counting the number of instructions executed by the algorithm, while set analyzing involves analyzing the worst-case scenario for the algorithm. Process profiling involves analyzing the behavior of the algorithm during runtime. Therefore, benchmarking is the best choice for this question.

Question 15

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.

Accepted Answer

The strategy utilized by the bubble sort algorithm is to repeatedly swap adjacent elements that are out of order in a list until the list is completely sorted. This is known as a bubble sort because the larger elements "bubble up" to the end of the list while the smaller elements "bubble down" to the beginning. Option B describes the strategy of selection sort, option C describes the strategy of insertion sort, and option D describes the strategy of quicksort.

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

The iterative version of the Fibonacci algorithm runs in linear time, meaning it is much faster than the recursive version which has exponential time complexity. While it may not be as elegant in design, it is more efficient in terms of time and space complexity.

Question 17

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

Accepted Answer

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

Question 18

Python's in operator is implemented as a method by what name in the list class?
A) __in__
B) __contains__
C) __present__
D) __within__

Accepted Answer

The in operator is implemented as the __contains__() method in the list class, which returns True if the given element is present in the list, and False otherwise. Therefore, the correct choice is B) __contains__.

Question 19

In terms of order of complexity, what is the best kind of performance to have?
A) linear
B) quadratic
C) constant
D) logarithmic

Accepted Answer

Constant performance is the best kind of performance in terms of order of complexity because it takes the same amount of time to complete the task regardless of the input size. This means that as the input grows larger, the algorithm does not slow down or become less efficient.

Question 20

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.

Accepted Answer

The insertion sort algorithm repeatedly inserts the i-th element into its proper place in the first i items in the list. This is done by comparing each element to its previous neighbor and inserting it in the correct position in the already sorted list.

Quiz 11: Searching Sorting and Complexity Analysis

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

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

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

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?

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

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?

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

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

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

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?

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

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

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

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?

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

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.

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

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

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

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