Chapter 12 review. Are the following statements true or false? Explain why or why not.

a. A Turing machine is a mechanical device invented by Alan Turing.
False. A Turing machine is an abstract device, developed by Turing to discover the boundaries of computability.

b. Complexity in a program is highly desirable because complex programs are more powerful.
False. Complex programs are often powerful, but their complexity makes them hard to understand, correct, and maintain. Complex programs also tend to be much slower.

c. A linear search is a highly efficient way to search an array.
False. For example, the entire array must be searched to discover that a desired value is not in the array.

d. "Hashing" is what is done in a diner.
False. For our purposes, it’s a method of storing data in an array so they can be efficiently found.

e. Hashing, ignoring what happens in diners, is always more efficient than linear search.
False. In worst cases, it can amount to a linear search.

f. A binary search is substantially more efficient that a linear search.
True. Whereas finding a value in an array averages roughly N/2 steps in a linear search, it takes roughly log₂(N)/2 steps in a binary search.

g. An array should always be sorted before searching in it.
False. It depends on how often the array is to be searched. Since sorts are more costly that searches, sorting a very large array before searching it only once would be very inefficient.

h. A bubble sort is so-called because it was invented by "Bubbles" Ort, an early programmer.
False. Rather, in this algorithm, values "bubble up" to their correct places in the array.

i. A bubble sort is conceptually a very complicated type of sort.
False. It’s one of the easiest--both to explain and to write. But it’s often one of the slowest to run.

j. A selection sort is roughly twice as efficient as a bubble sort.
True. In worst cases, the cost of a bubble sort is just under 2.5 times the cost of a selection sort.

k. In the worst case, an insertion sort is about as efficient as a selection sort.
False. In the worst case, the selection sort is about twice as efficient

l. In the best or average cases, an insertion sort is a good deal better than a selection sort.
True. In the best case, the insertion sort is much better. In the average case, the cost of an insertion sort is about 85% of the cost of a selection sort.

m. All of the sorts we considered involve nested loops.
True. Certain blocks of statements must be repeated inside larger blocks, which are themselves repeated.

n. Quicksort is fundamentally different from the bubble, selection, and insertion sorts.
True. It is based on recursion, while the others are not.

o. Quicksort is more efficient than the bubble, selection, or insertion sorts.
True. The efficiency of the quicksort is on the order of N*log(N)--substantially better than any of the others.

p. An algorithm which is O(N*log(N)) is more efficient than one which is O(N²).
True. Since O(log(N)) is less than O(N), O(N*log(N)) is less than O(N²).

q. O(log₂(N)) is smaller than O(log₁₀(N)).
False. Although log₂(N) is larger than log₁₀(N), since log2(N) = log2(10)*log10(N), it is nevertheless the case that O(log₂(N)) = O(log₁₀(N)).

r. A Turing machine’s tape is used for input, memory, and output.
True. That’s what makes a Tm so conceptually simple, but so tedious to program.

s. Every Turing machine is a total machine—i.e., has an output for every input.
False. In fact, in some sense, most Turing machines aren’t total. But in the strict mathematical sense, there are exactly as many partial machines as total machines.

t. A Turing machine can do arithmetic, but not symbolic processing.
False. In fact, the way a Turing machine does arithmetic is by symbolic processing!

u. A finite-state machine can be seen as a special kind of Turing machine.
True. It’s a Turing machine with no storage memory.

v. A finite-state machine cannot recognize strings of the form aⁿbⁿ.
True. In a certain sense, it can’t count and remember the length of an arbitrarily long leading string of a’s.

w. A finite-state machine has no external memory, but a pushdown-store machine does.
True. The memory of a PDM is called a stack; storage and retrieval are only from the "top" of the stack.

x. Information at the bottom of a stack can never be recovered.
False. It can, but only at the cost of removing (and perhaps losing) everything stored above it.

y. A pushdown-store machine can recognize strings of the form aⁿbⁿ, but not aⁿbⁿcⁿ.
True. The pushdown memory can count and remember the length of the leading string of a’s and compare it against the length of the middle string of b’s, but it can’t then compare that against the length of the string of c’s.

z. A Universal machine can simulate any Turing machine.
True. That’s exactly why Turing called it a Universal machine.

z’: Knobby has all the computational capacity of a universal machine.
True. Running a "Universal Knobby" program, when presented with a situation file representing a Knobby program P and a situation I, Knobby will simulate his own behavior running program P on situation I.