Deck 11: Computer Science Thinking: Recursion, Searching, Sorting and Big O

Question 1

Which of the following statements is false?

A) The xe "Fibonacci series"Fibonacci series, 0, 1, 1, 2, 3, 5, 8, 13, 21, …
Begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two.
B) This series occurs in nature and describes a form of xe "spiral"spiral.
C) The xe "ratio of successive Fibonacci numbers"ratio of successive Fibonacci numbers converges on a constant value of 1.618…, a number that has been called the golden ratio or the golden mean. Humans tend to find the golden mean aesthetically pleasing.
D) The xe "Fibonacci series:defined recursively"Fibonacci series may be defined recursively as follows: Base case: fibonacci(0) is defined to be 0
Recursion step: fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Answer 1

D

Question 2

Which of the following statements about the binary search of an array in ascending order is false?

A) In the worst-case scenario, searching a sorted array of 1023 elements takes only 10 comparisons when using a xe "binary search:algorithm"bxe "efficiency of:binary search"inary search. The number 1023 (which is 2¹⁰ - 1) is divided by 2 only 10 times to get the value 0, which indicates that there are no more elements to test.
B) Dividing by 2 is equivalent to one comparison in the binary search algorithm. Thus, an array of 1,048,575 (2²⁰ - 1) elements takes a maximum of 20 comparisons to find the key, and an array of about one billion elements takes a maximum of 30 comparisons to find the key. This is a tremendous performance improvement over the xe "linear search algorithm"linear search.
C) For a one-billion-element array, the increase in performance of a binary search over a linear search is a difference between an average of five million comparisons for the linear search and a maximum of only 30 comparisons for the binary search!
D) The binary search's big O is xe "Big O notation"O(log n), which also is known as logarithmic run time and pronounced as "order log n." Of course, this assumes the array is sorted, though, which could take substantial time.

Answer 2

C

Question 3

Which of the following statements about binary search of an array in ascending order is false?

A) The binary search algorithm is more efficient than linear search, but the linear search requires a sorted array.
B) The first iteration of this algorithm tests the middle element in the array. If this matches the search key, the algorithm ends.
C) If the search key is less than the middle element, it cannot match any element in the second half of the array so the algorithm continues with only the first half of the array (i.e., the first element up to, but not including, the middle element).
D) If the search key is greater than the middle element, it cannot match any element in the first half of the array so the algorithm continues with only the second half of the array (i.e., the element after the middle element through the last element).

Answer 3

A

Question 4

What should the question mark (?) in the following for statement be replaced with, so that the statements will calculate 5!? In [1]: factorial = 1
In [2]: for number in range(5, 0, ?):
)..: factorial *= number
)..:
In [3]: factorial
Out[3]: 120

A) 1
B) 0
C) -1
D) None of the above.

Question 5

Which of the following statements is false?

A) The xe "efficiency of:linear search"linear search algorithm runs in O(n) time.
B) The worst case in the linear search algorithm is that every element must be checked to determine whether the search item exists in the array. If the size of the array is doubled, the number of comparisons that the algorithm must perform is quadrupled.
C) Linear search can provide outstanding performance if the element matching the search key happens to be at or near the front of the array.
D) Linear search is easy to program, but it can be slow compared to other search algorithms. If a program needs to perform many searches on large arrays, it's better to implement a more efficient algorithm, such as the binary search.

Question 6

Which of the following statements a), b) or c) is false?

A) For big data applications, you'll also want to choose algorithms that are easy to sequentialize-that will enable you to put lots of processors to work simultaneously.
B) The simplest and most apparent algorithms often perform poorly-developing more sophisticated algorithms can lead to superior performance.
C) Big O notation concisely classifies algorithms by how hard they have to work to get the job done-it helps you compare the efficiency of algorithms.
D) All of the above statements are true.

Question 7

Which of the following statements is false?

A) Both xe "iteration"iteration and recursion are based on a xe "control statement"control statement: Iteration uses an xe "iteration:statement"iteration statement (e.g., for or while), whereas recursion uses a selection statement (e.g., if or if…else or if…elif…else).
B) Iteration and recursion each involve a xe "termination test"termination test: Iteration terminates when the loop-continuation condition fails, whereas recursion terminates when a base case is reached.
C) Iteration with xe "counter-controlled iteration[counter controlled iteration]"counter-controlled iteration and recursion both gradually approach termination: Counter-controlled iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation condition fail, whereas recursion keeps producing smaller versions of the original problem until the base case is reached.
D) Only iteration can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false.

Question 8

The following code implements a simple linear search. In [1]: def linear_search(data, search_key):
)..: for index, value in enumerate(data):
)..: if value == search_key:
)..: return ***
)..: return -1
)..:
)..:
In the statement return ***, what should replace *** to indicate where the search key was found?

A) data
B) search_key
C) index
D) None of the above

Question 9

Which of the following statements a), b) or c) is false?

A) Recursive functions (or methods) call themselves, either directly or indirectly through other functions (or methods).
B) Recursion might help you solve problems more naturally when an iterative solution is not apparent.
C) Sorting unique values is a fascinating problem, because no matter what algorithms you use, the final result is the same. So you'll want to choose algorithms that perform "the best"-usually, the ones that run the fastest or use the most memory.
D) All of the above statements are true.

Question 10

Suppose you have an algorithm that tests whether any element of an array is duplicated elsewhere in the array. The first element must be compared with all the other array elements. The second element must be compared with all the other array elements except the first (it was already compared to the first). The third element must be compared with all the other array elements except the first two. In the end, this algorithm makes (n - 1) + (n - 2) + … + 2 + 1
Or
N²/2 - n/2
Comparisons. Which of the following statements a), b) or c) is false?

A) As n increases, the n² term dominates, and the n term becomes inconsequential. O(n²) notation highlights the n² term, ignoring n/2. O(n²) is referred to as xe "quadratic run time"quadratic run time and pronounced "on the order of n-squared" or more simply "order n-squared."
B) Big O is concerned with how an algorithm's run time grows in relation to the number of items, n, processed. When n is small, O(n²) algorithms (on today's super-fast computers) will not noticeably affect performance, but as n grows, you'll start to notice performance degradation.
C) An O(n²) algorithm operating on a billion-element array (not unusual in today's big-data applications) would require a quintillion operations, which on today's desktop computers all the other array elements could take approximately 13.3 years to complete! O(n²) algorithms, unfortunately, are easy to write.
D) All of the above statements are true.

Question 11

Which of the following statements a), b) or c) is false?

A) Searching data involves determining whether a value (referred to as the search key) is present in the data and, if so, finding its location.
B) Two popular search algorithms are the simple binary search and the faster but more complex linear search.
C) Sorting places data in ascending or descending order, based on one or more sort keys.
D) All of the above statements are true.

Question 12

Which of the following statements a), b) or c) is false?

A) The amount of memory in a computer is finite, so only a certain amount of memory can be used to store activation records on the function-call stack.
B) If more recursive function calls occur than can have their activation records stored on the stack, a fatal error known as an infinite loop occurs.
C) Running out of memory for the function-call stack typically is the result of infinite recursion, which can be caused by omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case.
D) All of the above statements are true.

Question 13

Which of the following statements a), b) or c) is false?

A) When you call a recursive function to solve a problem, it's actually capable of solving only the base case(s). If you call the recursive function with a base case, it immediately returns a result.
B) The recursion step executes while the original function call is still active (i.e., it has not finished executing).
C) For the recursion to eventually terminate, each time the function calls itself with a simpler version of the original problem, the sequence of smaller and smaller problems must xe "converge on a base case"converge on a recursion step.
D) All of the above statements are true.

Question 14

Suppose an algorithm is designed to test whether the first element of an array is equal to the second. If the array has 10 elements, this algorithm requires one comparison. If the array has 1000 elements, it still requires only one comparison. Which of the following statements is false:

A) The algorithm is completely independent of the number of elements in the array.
B) This algorithm is said to have a constant run time, which is represented in Big O notation as O(1) and pronounced as "order one."
C) An algorithm that's O(1) does not necessarily require only one comparison. O(1) simply means that the number of comparisons is constant-it does not grow as the size of the array increases.
D) An algorithm that tests whether the first element of an array is equal to any of the next three elements is O(3).

Question 15

Which of the following statements a), b) or c) is false?

A) The xe "factorial"factorial of a positive integer n is written n! and pronounced "n factorial."
B) n! is the product n · (n - 1) · (n - 2) · … · 1
With 1! equal to 1 and 0! defined to be 1.
C) 4! is the product 4 · 3 · 2 · 1, which is equal to 24.
D) All of the above statements are true.

Question 16

Which of the following statements a), b) or c) is false?

A) The linear search algorithm searches each element in an array sequentially.
B) If the search key does not match an element in the array, the algorithm informs the user that the search key is not present.
C) If the search key is in the array, the algorithm tests each element until it finds one that matches the search key and returns the index of that element.
D) All of the above statements are true.

Question 17

An algorithm that tests whether the first array element is equal to any of the other array elements requires at most n - 1 comparisons, where n is the number of array elements. Which of the following statements is false?

A) If the array has 10 elements, this algorithm requires up to nine comparisons.
B) If the array has 1000 elements, it requires up to 999 comparisons.
C) As n grows larger, the n part of the expression n - 1 "dominates," and subtracting 1 becomes inconsequential. Big O is designed to highlight these dominant terms and ignore terms that become unimportant as n grows.
D) An algorithm that requires a total of n - 1 comparisons is said to be O(n - 1) and is said to have a linear run time.

Question 18

The following fibonacci function calculates the nth Fibonacci number recursively: In [1]: def fibonacci(n):
)..: if n in (0, 1): # base cases
)..: return n
)..: else:
)..: return fibonacci(n - 1) + fibonacci(n - 2)
)..:
Which of the following statements is false?

A) Because fibonacci is a xe "recursion:recursive call"recursive function, all calls to fibonacci are recursive.
B) Each time you call fibonacci, it immediately tests for the xe "base case"base cases-n equal to 0 or n equal to 1, which the fibonacci function tests simply by checking whether n is in the tuple (0, 1).
C) If a base case is detected, fibonacci simply returns n, because fibonacci(0) is 0 and fibonacci(1) is 1.
D) Interestingly, if n is greater than 1, the xe "recursion:recursion step"recursion step generates two recursive calls, each for a slightly smaller problem than the original call to fibonacci.