Concept: linear selection

Suppose you wish to find both the minimum and maximum values in an
array of n values, n being odd. Consider this algorithm:

Make a pass through the array and find the minimum

Make a pass through the array and find the maximum

Report the minimum and the maximum at termination
What is the minimum number of comparisons (not including the check for
termination) that this algorithm needs to
perform?
 $2n2$
 $2n1$
 $2n$
 $2n+2$
 $2n+1$

Suppose you wish to find both the minimum and maximum values in an
array A of n values, n being odd. Consider this algorithm:

Set the maximum and minimum to the first value in the array

Make a pass through the array
(i = 1; i < n; i += 2)

Compare A[i] with A[i+1]

Update the minimum if the smaller of the two is less

Update the maximum if the larger of the two is greater

Report the minimum and the maximum at loop termination
What is the minimum number of comparisons (not including the check for
termination) that this algorithm needs to
perform?
 $3\genfrac{}{}{0.1ex}{}{n1}{2}$
 $3n1$
 $3n3$
 $2n3$
 $3\genfrac{}{}{0.1ex}{}{n1}{2}+2$
 $3n$

Consider running the linear selection algorithm on an array with $n=5k$
unique elements.
What is a tight lower bound on the number of elements less than
the median of medians?
Assume the median of medians is found with groups of
five and integer division.
 $3\genfrac{}{}{0.1ex}{}{n}{10}+3$
 $5\genfrac{}{}{0.1ex}{}{n}{10}+2$
 $3\genfrac{}{}{0.1ex}{}{n}{5}+3$
 $3\genfrac{}{}{0.1ex}{}{n}{5}+2$
 $2\genfrac{}{}{0.1ex}{}{n}{5}+3$
 $3\genfrac{}{}{0.1ex}{}{n}{10}+2$
 $2\genfrac{}{}{0.1ex}{}{n}{5}+2$
 $5\genfrac{}{}{0.1ex}{}{n}{10}+3$

Consider running the linear selection algorithm on an array with $n=3k$
unique elements.
What is a tight lower bound on the number of elements less than
the median of medians?
Assume the median of medians is found with groups of
three and integer division.
 $3\genfrac{}{}{0.1ex}{}{n}{6}+1$
 $2\genfrac{}{}{0.1ex}{}{n}{3}+2$
 $2\genfrac{}{}{0.1ex}{}{n}{3}+1$
 $3\genfrac{}{}{0.1ex}{}{n}{6}+2$
 $2\genfrac{}{}{0.1ex}{}{n}{6}+2$
 $2\genfrac{}{}{0.1ex}{}{n}{6}+1$
 $\genfrac{}{}{0.1ex}{}{n}{3}+1$
 $\genfrac{}{}{0.1ex}{}{n}{3}+2$

Consider running the linear selection algorithm on an array with $n=7k$
unique elements.
What is a tight lower bound on the number of elements less than
the median of medians?
Assume the median of medians is found with groups of
seven and integer division.
 $11\genfrac{}{}{0.1ex}{}{n}{14}+2$
 $3\genfrac{}{}{0.1ex}{}{n}{14}+2$
 $4\genfrac{}{}{0.1ex}{}{n}{14}+3$
 $3\genfrac{}{}{0.1ex}{}{n}{7}+2$
 $3\genfrac{}{}{0.1ex}{}{n}{7}+3$
 $3\genfrac{}{}{0.1ex}{}{n}{14}+3$
 $4\genfrac{}{}{0.1ex}{}{n}{14}+2$
 $11\genfrac{}{}{0.1ex}{}{n}{14}+3$

Consider running the linear selection algorithm on an array with $n={7}^{k}$
unique elements.
What is a reasonable recurrence equation to describe the
running time of the algorithm?
Assume the median of medians is found with groups of
seven.
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{10n}{14}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{11n}{14}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{5n}{7}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{4n}{7}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{4n}{14}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{7}\right)+T\left(\genfrac{}{}{0.1ex}{}{6n}{7}\right)+\theta \left(n\right)$

Consider running the linear selection algorithm on an array with $n={3}^{k}$
unique elements.
What is a reasonable recurrence equation to describe the
running time of the algorithm?
Assume the median of medians is found with groups of
three.
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{2n}{3}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{2n}{5}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{5n}{6}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{n}{6}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\theta \left(n\right)$

Consider running the linear selection algorithm on an array with $n={5}^{k}$
unique elements.
What is a reasonable recurrence equation to describe the
running time of the algorithm?
Assume the median of medians is found with groups of
five.
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{2n}{5}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{9n}{10}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{4n}{5}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{7}{10}\right)+\theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{5}\right)+T\left(\genfrac{}{}{0.1ex}{}{3n}{5}\right)+\theta \left(n\right)$

T or F:
If the linear selection algoritm uses groups of three to find the
median of medians, the asymptotic run time is still $\theta \left(n\right)$.

T or F:
If the linear selection algoritm uses groups of seven to find the
median of medians, the asymptotic run time is still $\theta \left(n\right)$.
Concept: decision trees

In proving a tight lower bound for a class of algorithms, one tries to
establish, over all possible algorithms:
 the best possible worst case
 the best possible best case
 the worst possible best case
 the worst possible worst case

In an efficient decision tree for comparison sorts of n numbers,
what is the smallest possible depth of a leaf, in the best case?
Assume the root is at depth 0.
 approximately $n\mathrm{log}n$
 $n1$
 n
 1
 $n!$
 approximately $\mathrm{log}n$

In an efficient decision tree for comparison sorts of n numbers,
what is the largest possible depth of a leaf, in the worst case?
Assume the root is at depth 0.
 approximately $n\mathrm{log}n$
 approximately $\mathrm{log}n$
 $n!$
 1
 $n1$
 n

In an efficient decision tree for comparison sorts of n numbers,
what does the shortest path from the root to a leaf represent?
 the worst case behavior of the sort
 the best case behavior of the sort
 the average case behavior of the sort
 nothing, the longest path is what's important

An efficient decision tree for comparison sorts of n numbers
has how many leaves?
 ${2}^{n}$
 $\mathrm{log}n$
 $n\mathrm{log}n$
 $n!$

Deriving a tight lower time bound for comparison sorts, based upon an
efficient decision tree, yields:
 unbounded
 $\Omega \left(n\mathrm{log}n\right)$
 $O\left(n\mathrm{log}n\right)$
 $\omega \left(n\mathrm{log}n\right)$
 $O\left(n\right)$
 $\Omega \left(n\right)$
Concept: linear sorting fundamentals

Stability in a sort means:
 the order of ties in the output reflects the input
 the sort can work on any kind of number (integers, reals, etc.)
 the asymptotic run time does not vary upon the input

The best case behavior for insertion sort is:
 quadratic
 linear
 exponential
 log linear

T or F:
A lineartime sort does not compare entire keys with one another.

T or F:
A lineartime sort must always compare entire keys with one another.
Concept: linear sorting  counting
For counting sort, assume array A holds the data to be sorted,
array B holds the sorted data, and array C holds the counts.
The index i is used to sweep arrays A and B and the
index j is used to sweep array C.

Counting sort is:
 always unstable
 always stable

stable if lower indexed elements from the input array
are transferred to higher indexed elements in the output array.

stable if higher indexed elements from the input array
are transferred to higher indexed elements in the output array.

Suppose you are to sort n numbers using counting sort.
What size should the C array be?
 greater than n
 there's not enough information
 less than n
 equal to n

Consider using a counting sort to sort the input array
[2,5,0,3,2,0,3,3]
.
After the first phase, when
C[i]
holds the number of
elements equal to i, the array C looks like:

[2,0,2,3,0,1]

[2,0,5,2,3,0,3,3]

[0,0,2,2,3,3,3,5]

[2,2,4,6,7,8]

[2,2,4,7,7,8]

Consider using a counting sort to sort the input array
[2,5,0,3,2,0,3,3]
with auxiliary array C.
After the second phase, when
C[i]
holds the number of
elements less than or equal to i, the array C looks like:

[2,0,2,3,0,1]

[2,2,4,7,7,8]

[0,0,2,2,3,3,3,5]

[2,0,5,2,3,0,3,3]

[2,2,4,6,7,8]

Consider using a stable counting sort to sort the input array
[2,5,0,3,2,0,3,3]
with destination array B.
At start of phase three, using a right to left placement,
the first element to be placed in B is:
 0, at index 1
 4, at index 5
 3, at index 6
 2, at index 3
 1, at index 0
 5, at index 7

Let n be the count of numbers in a collection of base${}_{10}$ numbers.
Suppose zero is the minimum number and
k is the maximum number in the collection.
The time complexity of counting sort is:
 $\Theta \left(nk\right)$
 $\Theta \left(n\mathrm{log}k\right)$
 $\Theta \left({n}^{k}\right)$
 $\Theta (n+k)$

Let n be the count of numbers in a collection of base${}_{10}$ numbers.
Suppose zero is the minimum number and
k is the maximum number in the collection.
If $k=o\left(n\right)$, then the time complexity of
counting sort is:
 $\Theta \left(k\mathrm{log}n\right)$
 $\Theta \left(n\right)$
 $\Theta \left(k\right)$
 $\Theta \left(n\mathrm{log}k\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({k}^{2}\right)$

T or F:
Suppose the
lower bound of some numbers to be sorted is not zero.
Counting sort can still be used without changing its
fundamental time bounds.

T or F:
Suppose the
lower bound of some numbers to be sorted,
LB
, is not zero.
Counting sort can still be used without changing its
fundamental time bounds, if, among other changes, the
statement
C[A[i]] += 1
is changed
to
C[A[i]LB] += 1
.

T or F:
Suppose the
lower bound of some numbers to be sorted,
LB
, is not zero.
Counting sort can still be used without changing its
fundamental time bounds, if, among other changes, the
statement
B[C[A[i]]1] = A[i]
is changed
to
B[C[A[iLB]]1] = A[i]
.

T or F: Counting sort can be used to
sort n decimal numbers uniformly distributed
over the range of zero to ${n}^{5}$ in linear time.

Consider using counting sort to
sort n numbers uniformly distributed
over the range of zero to ${n}^{k}$.
The asymptotic complexity of the sort will be
 $\theta (n+k)$
 $\theta ({n}^{k}+n)$
 $\theta \left(n\mathrm{log}k\right)$
 $\theta \left(k\mathrm{log}n\right)$
 $\theta \left(n\right)$
 $\theta \left(k\right)$
Concept: linear sorting  radix

Suppose the recurrence equation
$T(p,q)=T(p,q1)+\theta \left(p\right)$
is used to describe radix sort.
Considering only the sorting of the numbers on a particular digit,
which sort is consistent with that equation?
 counting sort
 radix sort
 mergesort sort
 selection sort

Suppose the recurrence equation
$T(p,q)=T(p,q1)+\theta \left(p\mathrm{log}p\right)$
is used to describe radix sort.
Considering only the sorting of the numbers on a particular digit,
which sort is consistent with that equation?
 counting sort
 selection sort
 mergesort sort
 radix sort

Suppose the recurrence equation
$T(p,q)=T(p,q1)+\theta \left({p}^{2}\right)$
is used to describe radix sort.
Considering only the sorting of the numbers on a particular digit,
which sort is consistent with that equation?
 mergesort sort
 selection sort
 radix sort
 counting sort

Suppose the recurrence equation
$T(p,q)=T(p,q1)+\theta \left(p\right)$
is used to describe radix sort.
Which variable in the equation refers to the number of digits?
 q
 p
 d
 n

Consider using radix sort for sorting the following numbers:
558
354
318
622
After the first pass, the order of the numbers is:
 318, 354, 558, 622
 354, 318, 558, 622
 622, 354, 558, 318
 622, 354, 318, 558
 622, 558, 318, 354
 622, 558, 354, 318

Let n be the count of numbers in a collection of positive,
base${}_{10}$ numbers.
Let m be the number of digits in the largest number in the
collection. Suppose the auxiliary sort works in $\Theta \left(n\right)$ time.
Then radix sorting takes time:
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(nm\right)$
 $\Theta \left(n\mathrm{log}m\right)$
 $\Theta \left(m\mathrm{log}n\right)$

Let n be the count of numbers in a collection of positive,
base${}_{10}$ numbers.
Let m be the number of digits in the largest number in the
collection. Suppose the auxiliary sort works in $\Theta \left(n\mathrm{log}n\right)$
time. Then radix sorting takes time:
 $\Theta \left(n\mathrm{log}\right(m+n\left)\right)$
 $\Theta \left(n\mathrm{log}\right(mn\left)\right)$
 $\Theta \left(n\mathrm{log}m\right)$
 $\Theta \left(mn\mathrm{log}n\right)$

T or F:
Suppose during one pass of radix sort, there is a tie between two numbers.
Since they are considered the same number,
it does not matter if those two numbers swap positions.

Consider the sort used for each pass of radix sort.
Must the auxiliary sort be stable?
 No, because there can be no ties in radix sort.
 No, because radix sort works even if the auxilliary sort is unstable.
 Yes, because swapping ties can undo the work of previous passes
 Yes, because swapping ties can undo the work of future passes

T or F: Radix sort can be used to
sort n decimal numbers uniformly distributed
over the range of zero to ${n}^{5}$ in linear time.
Concept: linear sorting  bucket

T or F: If bucket sort uses equallysized buckets,
then the distribution of the incoming numbers need not be
uniform for the sort to run in expected linear time.

Consider using bucket sort to sort
n numbers evenly distributed over the
range 0 to m. Roughly, how many buckets should you use?
 m
 $\genfrac{}{}{0.1ex}{}{m}{n}$
 $\genfrac{}{}{0.1ex}{}{n}{m}$
 n

Consider using bucket sort to sort
n numbers evenly distributed over the
range 0 to m. Roughly, what size bucket should you use?
 $\genfrac{}{}{0.1ex}{}{n}{m}$
 $\genfrac{}{}{0.1ex}{}{m}{n}$
 n
 m

Consider using bucket sort to sort
n nonnegative numbers evenly distributed over the
range 0 to m. The range of the first bucket should be:
 $0$ to $\genfrac{}{}{0.1ex}{}{m}{n}$
 $\genfrac{}{}{0.1ex}{}{n}{m}$ to $\genfrac{}{}{0.1ex}{}{2n}{m}$
 $\genfrac{}{}{0.1ex}{}{m}{n}$ to $2\genfrac{}{}{0.1ex}{}{m}{n}$
 0 to $\genfrac{}{}{0.1ex}{}{n}{m}$

Consider using bucket sort to sort
n nonnegative numbers evenly distributed over the
range 0 to m. The average count of numbers in a bucket is:
 $\genfrac{}{}{0.1ex}{}{m}{n}$
 0
 $\genfrac{}{}{0.1ex}{}{n}{m}$
 1

Consider a bucket sort that uses insertion sort to sort the
individual buckets.
Suppose you could bound the maximum count of numbers in a
bucket to a constant C. Then the asymptotic running time
to sort one bucket would be:
 $\Theta \left({n}^{2}\right)$, because insertion sort is quadratic in the worst case
 $\Theta \left(n\mathrm{log}n\right)$, because insertion sort is loglinear in the average case
 $\Theta \left(1\right)$
 $\Theta \left(n\right)$, because insertion sort is linear in the best case

Consider using bucket sort to sort
n nonnegative numbers evenly distributed over the
range 0 to m. The expected running time is:
 constant
 quadratic
 linear
 loglinear

Consider using bucket sort to sort
n nonnegative numbers in the
range 0 to m with no a priori knowledge of the
distribution of the numbers. Using insertion sort as
the auxilliary sort, the worst case running time is:
 linear
 cubic
 quadratic
 constant

T or F: Bucket sort can be used to
sort n decimal numbers uniformly distributed
over the range of zero to ${n}^{5}$ in linear time.
Concept: recurrence equations

Stooge sort has the following algorithm. Recursively sort
the lower twothirds of an array, then recursively sort
the upper twothirds, then recursively sort the lower
twothirds again.
The recursion stops when the array consists of two or fewer
elements. If the array size is two, the elements are swapped
if necessary. Which of the following recurrence equations
describe stooge sort?
 $T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=3T\left(2\genfrac{}{}{0.1ex}{}{n}{3}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(3\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\Theta \left(1\right)$
 $T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(\mathrm{log}n\right)$

Merge sort has the following algorithm. Recursively sort
the lower half of an array, then recursively sort
the upper half, then merge the two halves. When merging,
a single pass is made through each half.
The recursion stops when the array consists of one element.
Which of the following recurrence equations
describe merge sort?
 $T\left(n\right)=T(n1)+\Theta \left(n\right)$
 $T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$

Binary search has the following algorithm. Look at the
middle element in an array. If the element is the one
begin looked for (the target), return FOUND. Otherwise, if the
element is greater than the target, recursively search
the lower half of the array. Otherwise, recursively search
the upper half of the array. If the array consists of three
or fewer elements, perform a linear search of the array,
returning FOUND if found and MISSING otherwise.
Which of the following recurrence equations
describe binary search?
 $T\left(n\right)=2T(n1)+\Theta \left(1\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(\mathrm{log}n\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(\mathrm{log}n\right)$

Quicksort can have the following algorithm: find the median value of
the array and partition the array into two regions, one region holds
all the values less than the median and the other holds all values
greater than the median. Median finding and partitioning can both be
done in linear time.
Finally, the two regions are recursively sorted.
Which of the following recurrence equations
describe this version of quicksort?
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left({n}^{2}\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left({n}^{2}\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(\mathrm{log}n\right)$
 $T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=2T(n1)+\Theta \left(1\right)$

The recurrence equation $T\left(n\right)=T(n1)+\Theta \left(n\right)$ describes
which sort, in the worst case?
 quick sort
 heap sort
 radix sort
 merge sort

Consider using selection
sort to sort a previously sorted array.
Which of the following recurrence equations
describes this situation?
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(1\right)$
 $T\left(n\right)=T(n1)+\Theta \left(1\right)$
 $T\left(n\right)=2T(n1)+\Theta \left(1\right)$
 $T\left(n\right)=2T(n1)+\Theta \left(n\right)$
 $T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\Theta \left(n\right)$
 $T\left(n\right)=T(n1)+\Theta \left(n\right)$
Concept: identifying cases of the master recurrence theorem

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+{n}^{2}$
fall?
 case 2
 the equation is not in the correct form
 case 3
 between case 1 and case 2
 case 1
 between case 2 and case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$
fall?
 between case 2 and case 3
 case 3
 case 2
 between case 1 and case 2
 case 1
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$
fall?
 case 3
 case 1
 between case 1 and case 2
 case 2
 between case 2 and case 3
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{2}^{n}$
fall?
 case 3
 between case 2 and case 3
 between case 1 and case 2
 case 1
 the equation is not in the correct form
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)={2}^{n}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{n}$
fall?
 case 2
 case 1
 case 3
 the equation is not in the correct form
 between case 2 and case 3
 between case 1 and case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=T(n1)+1$
fall?
 case 1
 between case 2 and case 3
 between case 1 and case 2
 the equation is not in the correct form
 case 2
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=2T(n2)+n$
fall?
 the equation is not in the correct form
 case 2
 between case 2 and case 3
 between case 1 and case 2
 case 1
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n$
fall?
 the equation is not in the correct form
 case 1
 case 3
 case 2
 between case 2 and case 3
 between case 1 and case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$
fall?
 between case 1 and case 2
 between case 2 and case 3
 case 3
 the equation is not in the correct form
 case 1
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$
fall?
 case 1
 between case 2 and case 3
 between case 1 and case 2
 the equation is not in the correct form
 case 2
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$
fall?
 case 3
 between case 1 and case 2
 the equation is not in the correct form
 case 1
 between case 2 and case 3
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+{n}^{0.51}$
fall?
 case 1
 case 3
 case 2
 the equation is not in the correct form
 between case 1 and case 2
 between case 2 and case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{1}{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+1$
fall?
 case 3
 case 2
 case 1
 between case 1 and case 2
 between case 2 and case 3
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n!$
fall?
 case 1
 case 3
 case 2
 between case 1 and case 2
 between case 2 and case 3
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=\sqrt{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$
fall?
 the equation is not in the correct form
 between case 2 and case 3
 case 1
 case 3
 between case 1 and case 2
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$
fall?
 case 1
 case 2
 case 3
 between case 1 and case 2
 the equation is not in the correct form
 between case 2 and case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\sqrt{n}$
fall?
 case 3
 case 2
 the equation is not in the correct form
 between case 2 and case 3
 between case 1 and case 2
 case 1

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$
fall?
 case 2
 case 3
 between case 1 and case 2
 between case 2 and case 3
 case 1
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n\mathrm{log}n$
fall?
 case 1
 the equation is not in the correct form
 case 2
 between case 1 and case 2
 between case 2 and case 3
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\genfrac{}{}{0.1ex}{}{n}{2}$
fall?
 between case 1 and case 2
 case 2
 case 1
 between case 2 and case 3
 the equation is not in the correct form
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=6T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}\mathrm{log}n$
fall?
 the equation is not in the correct form
 between case 1 and case 2
 between case 2 and case 3
 case 2
 case 3
 case 1

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$
fall?
 case 3
 case 2
 between case 2 and case 3
 case 1
 between case 1 and case 2
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=64T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$
fall?
 case 1
 between case 2 and case 3
 case 3
 case 2
 between case 1 and case 2
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{7}}\right)+{n}^{2}$
fall?
 case 2
 case 1
 between case 2 and case 3
 the equation is not in the correct form
 between case 1 and case 2
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$
fall?
 between case 2 and case 3
 between case 1 and case 2
 case 2
 the equation is not in the correct form
 case 3
 case 1

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}$
fall?
 case 3
 the equation is not in the correct form
 case 1
 between case 2 and case 3
 between case 1 and case 2
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$
fall?
 case 1
 between case 1 and case 2
 case 3
 between case 2 and case 3
 the equation is not in the correct form
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$
fall?
 between case 1 and case 2
 the equation is not in the correct form
 between case 2 and case 3
 case 2
 case 1
 case 3

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$
fall?
 between case 2 and case 3
 case 1
 case 2
 case 3
 between case 1 and case 2
 the equation is not in the correct form

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+{n}^{3}$
fall?
 between case 2 and case 3
 case 1
 between case 1 and case 2
 case 3
 the equation is not in the correct form
 case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+\genfrac{}{}{0.1ex}{}{{n}^{3}}{\mathrm{log}n}$
fall?
 case 3
 between case 2 and case 3
 the equation is not in the correct form
 case 2
 case 1
 between case 1 and case 2

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+{n}^{2}\mathrm{log}n$
fall?
 between case 1 and case 2
 case 2
 the equation is not in the correct form
 case 3
 between case 2 and case 3
 case 1

In terms of the master recurrence theorem, where does the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+n\mathrm{log}n$
fall?
 the equation is not in the correct form
 between case 1 and case 2
 case 3
 between case 2 and case 3
 case 2
 case 1
Concept: using the master recurrence theorem

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+{n}^{2}$?
 $\Theta \left({n}^{3}\mathrm{log}n\right)$
 $\Theta \left({n}^{3}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{4}\right)$
 $\Theta \left({n}^{2}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
 $\Theta \left({n}^{\genfrac{}{}{0.1ex}{}{3}{2}}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({n}^{3}\mathrm{log}n\right)$
 $\Theta \left({n}^{3}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
 the master theorem cannot be used
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left({n}^{4}\right)$
 $\Theta \left({n}^{3}\mathrm{log}n\right)$
 $\Theta \left({n}^{3}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{2}^{n}$?
 $\Theta \left({2}^{n}\right)$
 $\Theta \left({2}^{{n}^{\mathrm{log}n}}\right)$
 the master theorem cannot be used
 $\Theta \left({2}^{n}\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)={2}^{n}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{n}$?
 $\Theta \left({n}^{n}\right)$
 $\Theta \left({2}^{n}\mathrm{log}n\right)$
 $\Theta (\left({n}^{{n}^{\mathrm{log}n}}\right)$
 $\Theta \left({n}^{n}\mathrm{log}n\right)$
 $\Theta \left({2}^{n}\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=T(n1)+1$?
 $\Theta \left(n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}{n}^{\mathrm{log}n}\right)$
 the master theorem cannot be used
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(1\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=2T(n2)+n$?
 $\Theta \left(1\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left(n\right)$
 $\Theta \left({\left(\mathrm{log}n\right)}^{2}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n$?
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$?
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left(n\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$?
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(2\right)}\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{\genfrac{}{}{0.1ex}{}{3}{2}}\right)$
 the master theorem cannot be used
 $\Theta \left(n{\mathrm{log}}_{\genfrac{}{}{0.1ex}{}{3}{2}}\right(n\left)\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(3\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$?
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$
 $\Theta \left({n}^{2}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+{n}^{0.51}$?
 $\Theta \left(n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(\sqrt{n}\mathrm{log}n\right)$
 $\Theta \left(\sqrt{n}\right)$
 $\Theta \left({n}^{0.51}\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{1}{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+1$?
 $\Theta \left(n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{2}\genfrac{}{}{0.1ex}{}{1}{2}}\right)$
 $\Theta \left({\mathrm{log}}_{2}\genfrac{}{}{0.1ex}{}{1}{2}\right)$
 the master theorem cannot be used
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left({n}^{\genfrac{}{}{0.1ex}{}{1}{2}}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n!$?
 the master theorem cannot be used
 $\Theta ({n}^{2}n!)$
 $\Theta (n!)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left(\right({n}^{2})!)$
 $\Theta (n!\mathrm{log}n)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=\sqrt{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(\sqrt{n}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}\left(2\right)}\right)$
 $\Theta \left(\sqrt{n}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
 $\Theta \left(n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(2\right)}\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(n{\mathrm{log}}_{\genfrac{}{}{0.1ex}{}{3}{2}}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(3\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\sqrt{n}$?
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left(\sqrt{n}\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}\sqrt{n}\right)$
 $\Theta \left(n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left(n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n\mathrm{log}n$?
 $\Theta \left({n}^{{\mathrm{log}}_{4}\left(3\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(4\right)}\right)$
 $\Theta \left(n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\genfrac{}{}{0.1ex}{}{n}{2}$?
 $\Theta \left(n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=6T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}\mathrm{log}n$?
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(6\right)}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(6\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{6}\left(3\right)}\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{6}\left(3\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$?
 $\Theta \left(\genfrac{}{}{0.1ex}{}{{n}^{2}}{\mathrm{log}n}\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\right)$
 the master theorem cannot be used

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=64T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$?
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\mathrm{log}n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{7}}\right)+{n}^{2}$?
 $\Theta \left(\genfrac{}{}{0.1ex}{}{n}{{\mathrm{log}}_{\sqrt{7}}\left(7\right)}\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{\sqrt{7}}\left(7\right)}\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
 $\Theta \left({n}^{{\mathrm{log}}_{7}\left(2\right)}\right)$
 $\Theta \left({n}^{2}\right)$
 $\Theta \left({n}^{2+{\mathrm{log}}_{2}\left(7\right)}\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2+{\mathrm{log}}_{7}\left(2\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(7\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}$?
 $\Theta \left({n}^{2+{\mathrm{log}}_{7}\left(3\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{7}\left(3\right)}\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{3}\left(7\right)}\right)$
 $\Theta \left({n}^{2+{\mathrm{log}}_{3}\left(7\right)}\right)$
 $\Theta \left({n}^{2}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left({n}^{2}\right)$
 the master theorem cannot be used
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(5\right)}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(5\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{5}\left(2\right)}\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{5}\left(2\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
 $\Theta \left({n}^{{\mathrm{log}}_{5}\left(2\right)}\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(5\right)}\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{2}\left(5\right)}\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{5}\left(2\right)}\mathrm{log}n\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+{n}^{3}$?
 $\Theta \left({n}^{{\mathrm{log}}_{5}\sqrt[3]{5}}\right)$
 $\Theta ({n}^{{\mathrm{log}}_{5}\sqrt[3]{5}}\times \mathrm{log}n)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{\sqrt[3]{5}}\left(5\right)}\right)$
 $\Theta \left({n}^{3}\mathrm{log}n\right)$
 $\Theta ({n}^{{\mathrm{log}}_{\sqrt[3]{5}}\left(5\right)}\times \mathrm{log}n)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+\genfrac{}{}{0.1ex}{}{{n}^{3}}{\mathrm{log}n}$?
 $\Theta \left({n}^{3}\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{\sqrt[3]{5}}\left(5\right)}\right)$
 the master theorem cannot be used
 $\Theta ({n}^{{\mathrm{log}}_{5}\sqrt[3]{5}}\times \mathrm{log}n)$
 $\Theta ({n}^{{\mathrm{log}}_{\sqrt[3]{5}}\left(5\right)}\times \mathrm{log}n)$
 $\Theta \left({n}^{{\mathrm{log}}_{5}\sqrt[3]{5}}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+{n}^{2}\mathrm{log}n$?
 $\Theta ({n}^{{\mathrm{log}}_{5}\sqrt{5}}\times \mathrm{log}n)$
 the master theorem cannot be used
 $\Theta \left({n}^{{\mathrm{log}}_{5}\sqrt{5}}\right)$
 $\Theta ({n}^{{\mathrm{log}}_{\sqrt{5}}\left(5\right)}\times \mathrm{log}n)$
 $\Theta \left({n}^{2}\mathrm{log}n\right)$
 $\Theta \left({n}^{{\mathrm{log}}_{\sqrt{5}}\left(5\right)}\right)$

Using the master recurrence theorem, what is the solution of
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+n\mathrm{log}n$?
 $\Theta \left({n}^{2+{\mathrm{log}}_{5}\sqrt{5}}\right)$
 $\Theta \left({n}^{2+{\mathrm{log}}_{\sqrt{5}}\left(5\right)}\right)$
 $\Theta ({n}^{{\mathrm{log}}_{\sqrt{5}}\left(5\right)}\times \mathrm{log}n)$
 $\Theta \left(n\mathrm{log}n\right)$
 the master theorem cannot be used
 $\Theta \left({n}^{2}\right)$
 $\Theta ({n}^{{\mathrm{log}}_{5}\sqrt{5}}\times \mathrm{log}n)$
Determining $\epsilon $ in the M.R.T.

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+\mathrm{log}n$.
What is the largest listed value of $\epsilon $ that can be used in the solution?
 0.1
 $\epsilon $ is not used in the solution
 0.5
 no legal value is listed
 0.25
 the master theorem cannot be used

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 3 is ~1.585
and the log
(base 3) of 2 is ~0.631.
 0.1
 the master theorem cannot be used
 0.25
 no legal value is listed
 0.5
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 4) of 2 is 0.5
and the log
(base 2) of 4 is 2.
 $\epsilon $ is not used in the solution
 no legal value is listed
 1.0
 the master theorem cannot be used
 0.5
 0.25

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{2}^{n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 0.5
 $\epsilon $ is not used in the solution
 no legal value is listed
 1.0
 0.1
 the master theorem cannot be used

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)={2}^{n}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 the master theorem cannot be used
 0.1
 0.5
 $\epsilon $ is not used in the solution
 1.0
 no legal value is listed

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 16) of 4 is 0.5
and log
(base 4) of 16 is 2.
 $\epsilon $ is not used in the solution
 0.5
 the master theorem cannot be used
 0.25
 no legal value is listed
 0.75

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 $\epsilon $ is not used in the solution
 no legal value is listed
 0.5
 the master theorem cannot be used
 1.0
 0.75

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 3 is ~1.585
and the log
(base 3) of 2 is ~0.631.
 1.0
 no legal value is listed
 0.25
 the master theorem cannot be used
 $\epsilon $ is not used in the solution
 0.5

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=8T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 8) of 2 is ~0.333
and the log
(base 2) of 8 is 3.
 no legal value is listed
 0.100
 the master theorem cannot be used
 0.05
 $\epsilon $ is not used in the solution
 0.025

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=2T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+{n}^{0.51}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 4) of 2 is 0.5 and log
(base 2) of 4 is 2.
 the master theorem cannot be used
 0.050
 0.100
 no legal value is listed
 0.075
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{1}{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+1$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 no legal value is listed
 0.05
 $\epsilon $ is not used in the solution
 0.01
 the master theorem cannot be used
 0.10

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=16T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n!$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 16) of 4 is 0.5
and the log
(base 4) of 16 is 2.
 no legal value is listed
 100
 the master theorem cannot be used
 $\epsilon $ is not used in the solution
 10
 1

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=\sqrt{2}T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of $\sqrt{2}$ is 0.5
and the log
(base $\sqrt{2}$) of 2 is 2.
 no legal value is listed
 0.50
 0.25
 the master theorem cannot be used
 1.0
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 3) of 2 is ~0.631
and the log
(base 2) of 3 is ~1.585.
 0.25
 0.10
 1.0
 no legal value is listed
 the master theorem cannot be used
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\sqrt{n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 no legal value is listed
 0.3
 0.9
 the master theorem cannot be used
 0.6
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 4 is 2
and the log
(base 4) of 2 is 0.5.
 0.9
 0.3
 the master theorem cannot be used
 $\epsilon $ is not used in the solution
 no legal value is listed
 0.6

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{4}\right)+n\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 3) of 4 is ~1.262
and the log
(base 4) of 3 is ~0.792.
 0.6
 no legal value is listed
 $\epsilon $ is not used in the solution
 0.9
 the master theorem cannot be used
 0.3

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=3T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+\genfrac{}{}{0.1ex}{}{n}{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
 no legal value is listed
 0.9
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 0.6
 0.3

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=6T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 3) of 6 is ~1.631
and the log
(base 6) of 3 is ~0.613.
 no legal value is listed
 the master theorem cannot be used
 $\epsilon $ is not used in the solution
 0.5
 0.4
 0.3

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 4) of 2 is 0.5
and the log
(base 2) of 4 is 2.
 0.5
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 1.0
 no legal value is listed
 0.25

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=64T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)\genfrac{}{}{0.1ex}{}{n}{\mathrm{log}n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 8) of 64 is 2
and the log
(base 64) of 8 is 0.5.
 no legal value is listed
 0.25
 0.5
 the master theorem cannot be used
 1.0
 $\epsilon $ is not used in the solution

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{7}}\right)+{n}^{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 7) of $\sqrt{7}$ is 0.5
and the log
(base $\sqrt{7}$) of 7 is 2.
 no legal value is listed
 $\epsilon $ is not used in the solution
 1.0
 0.5
 0.25
 the master theorem cannot be used

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+{n}^{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 7 is ~2.807
and the log
(base 7) of 2 is ~0.356.
 0.8
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 1.0
 0.6
 no legal value is listed

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{3}\right)+{n}^{2}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 3) of 7 is ~0.565
and the log
(base 7) of 3 is ~1.771.
 no legal value is listed
 0.8
 the master theorem cannot be used
 $\epsilon $ is not used in the solution
 1.0
 0.6

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=4T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 4 is 2
and the log
(base 4) of 2 is 0.5.
 2.0
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 0.5
 1.0
 no legal value is listed

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 5) of 2 is ~0.431
and the log
(base 2) of 5 is ~2.322.
 1.0
 $\epsilon $ is not used in the solution
 no legal value is listed
 the master theorem cannot be used
 0.5
 2.0

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{2}\right)+n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 2) of 5 is ~2.322
and the log
(base 5) of 2 is ~0.431.
 0.5
 1.0
 no legal value is listed
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 2.0

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+{n}^{3}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 5) of $\sqrt[3]{5}$ is ~0.333
and the log
(base $\sqrt[3]{5}$) of 5 is 3.
 no legal value is listed
 1.0
 0.5
 2.0
 $\epsilon $ is not used in the solution
 the master theorem cannot be used

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt[3]{5}}\right)+\genfrac{}{}{0.1ex}{}{{n}^{3}}{\mathrm{log}n}$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base $\sqrt[3]{5}$) of 5 is 3
and the log
(base 5) of $\sqrt[3]{5}$ is ~0.333.
 0.5
 $\epsilon $ is not used in the solution
 2.0
 the master theorem cannot be used
 1.0
 no legal value is listed

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+{n}^{2}\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base 5) of $\sqrt{5}$ is 0.5
and the log
(base $\sqrt{5}$) of 5 is 2.
 2.0
 0.5
 no legal value is listed
 $\epsilon $ is not used in the solution
 the master theorem cannot be used
 1.0

Consider using the master recurrence theorem to solve the equation
$T\left(n\right)=5T\left(\genfrac{}{}{0.1ex}{}{n}{\sqrt{5}}\right)+n\mathrm{log}n$?
What is the largest listed value of $\epsilon $ that can be used in the solution?
The log
(base $\sqrt{5}$) of 5 is 2
and the log
(base 5) of $\sqrt{5}$ is 0.5.
 the master theorem cannot be used
 1.0
 no legal value is listed
 0.5
 $\epsilon $ is not used in the solution
 2.0
Determining c for M.R.T., case 3

Consider using the master recurrence theorem and the regularity condition
for case 3 to solve the equation
$T\left(n\right)=8T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)+{n}^{2}$.
What is the smallest legal value
of the constant c listed for the solution?
 no legal value is listed
 case 3 does not apply
 $\genfrac{}{}{0.1ex}{}{1}{9}$
 $\genfrac{}{}{0.1ex}{}{1}{7}$
 $\genfrac{}{}{0.1ex}{}{1}{5}$

Consider using the master recurrence theorem and the regularity condition
for case 3 to solve the equation
$T\left(n\right)=7T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)+{n}^{2}$.
What is the smallest legal value
of the constant c listed for the solution?
 no legal value is listed
 case 3 does not apply
 $\genfrac{}{}{0.1ex}{}{9}{64}$
 $\genfrac{}{}{0.1ex}{}{11}{64}$
 $\genfrac{}{}{0.1ex}{}{7}{64}$

Consider using the master recurrence theorem and the regularity condition
for case 3 to solve the equation
$T\left(n\right)=6T\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)+{n}^{2}$.
What is the smallest legal value
of the constant c listed for the solution?
 no legal value is listed
 $\genfrac{}{}{0.1ex}{}{1}{64}$
 $\genfrac{}{}{0.1ex}{}{5}{64}$
 case 3 does not apply
 $\genfrac{}{}{0.1ex}{}{3}{64}$

Consider using the master recurrence theorem and the regularity condition
for case 3 to solve the equation
$T\left(n\right)=64\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)+{n}^{2}$.
What is the smallest legal value
of the constant c listed for the solution?
 no legal value is listed
 $\genfrac{}{}{0.1ex}{}{65}{64}$
 case 3 does not apply
 $\genfrac{}{}{0.1ex}{}{61}{64}$
 $\genfrac{}{}{0.1ex}{}{63}{64}$

Consider using the master recurrence theorem and the regularity condition
for case 3 to solve the equation
$T\left(n\right)=32\left(\genfrac{}{}{0.1ex}{}{n}{8}\right)+{n}^{2}$.
What is the smallest legal value
of the constant c listed for the solution?
 $\genfrac{}{}{0.1ex}{}{16}{64}$
 $\genfrac{}{}{0.1ex}{}{63}{64}$
 case 3 does not apply
 $\genfrac{}{}{0.1ex}{}{8}{64}$
 no legal value is listed
Inductive Proofs
Here is a recursive version of mergesort, which works for all
arrays with size one or greater:
mergeSort(array, start, end)
{
if (endstart < 2) return;
m = (start + end) / 2;
mergesort(array,start,m);
mergesort(array,m,end);
merge(array,start,m,end);
}
Assume that the recurrence for merge sort is described as:
$T\left({2}^{0}\right)=1$
$T\left({2}^{n}\right)=2T\left({2}^{n1}\right)+{2}^{n}$
Consider a proof, by induction, that $T\left({2}^{n}\right)=(n+1){2}^{n}$
where ${2}^{n}$ is the size of the array and b is the base case value of n.

To completely prove the base case value b, you would need to show:
 $2T\left({2}^{b1}\right)+{2}^{b}=(b+1){2}^{b}$
 $T\left({2}^{b}\right)=4$
 $2T\left({2}^{b1}\right)=2$
 $b{2}^{b}={2}^{b+1}$
 $2T\left({2}^{b1}\right)={2}^{b}$
 $b{2}^{b}=2$

Assuming b is the largest base case value and
you wish to prove the inductive case n,
an inductive hypothesis for a strong inductive proof would be:
 Assume true for $i\le n$.
 Assume true for $n$.
 Assume true for $i<n$.
 Assume true for $n+1$.
 Assume true for $b<i\le n$.
 Assume true for $b<i<n$.

Assuming b is the largest base case value and
you wish to prove the inductive case n+1,
an inductive hypothesis for a weak inductive proof would be:
 Assume true for $n+2$.
 Assume true for $n+1$.
 Assume true for $n$.
 Assume true for $n1$.

Assuming you wish to prove the inductive case n,
the first line of the inductive case for a strong inductive
proof would be:
 $T\left({2}^{n}\right)=(n+1){2}^{n}$
 $T\left({2}^{n}\right)=2T\left({2}^{n1}\right)+{2}^{n}$
 $T\left({2}^{n1}\right)=\left(\right(n1)+1){2}^{n1}$
 $T\left({2}^{n1}\right)=2T\left({2}^{(n1)1}\right)+{2}^{n1}$
 $T\left({2}^{n+1}\right)=2T\left({2}^{(n+1)1}\right)+{2}^{n+1}$
 $T\left({2}^{n+1}\right)=\left(\right(n+1)+1){2}^{n+1}$

Assuming you wish to prove the inductive case n+1,
the first line of the inductive case for a weak inductive
proof would be:
 $T\left({2}^{n1}\right)=\left(\right(n1)+1){2}^{n1}$
 $T\left({2}^{n+1}\right)=2T\left({2}^{(n+1)1}\right)+{2}^{n+1}$
 $T\left({2}^{n1}\right)=2T\left({2}^{(n1)1}\right)+{2}^{n1}$
 $T\left({2}^{n}\right)=2T\left({2}^{n1}\right)+{2}^{n}$
 $T\left({2}^{n+1}\right)=\left(\right(n+1)+1){2}^{n+1}$
 $T\left({2}^{n}\right)=(n+1){2}^{n}$

Assuming you wish to prove the inductive case n,
the inductive step for a strong inductive proof would be:
 substitute $T\left({2}^{n1}\right)$ for $n{2}^{n1}$
 substitute $(n1){2}^{n2}$ for $T\left({2}^{(n1)1}\right)$
 substitute $T\left({2}^{(n1)1}\right)$ for $(n1){2}^{n2}$
 substitute $(n+1){2}^{n}$ for $T\left({2}^{(n+1)1}\right)$
 substitute $n{2}^{n1}$ for $T\left({2}^{n1}\right)$
 substitute $T\left({2}^{(n+1)1}\right)$ for $(n+1){2}^{n}$

Assuming you wish to prove the inductive case n+1,
the inductive step for a weak inductive proof would be:
 substitute $n{2}^{n1}$ for $T\left({2}^{n1}\right)$
 substitute $(n+1){2}^{n}$ for $T\left({2}^{(n+1)1}\right)$
 substitute $T\left({2}^{(n+1)1}\right)$ for $(n+1){2}^{n}$
 substitute $(n1){2}^{n2}$ for $T\left({2}^{(n1)1}\right)$
 substitute $T\left({2}^{(n1)1}\right)$ for $(n1){2}^{n2}$
 substitute $T\left({2}^{n1}\right)$ for $n{2}^{n1}$

T or F:
For strong inductive proofs, proving the inductive case
makes use of the previously proved base cases.

T or F:
Weak inductive proofs are more closely related to
recursive functions than strong inductive proofs.

The more formal names for weak and strong inductive
proofs are:
 complete and mathematical
 simple and complex
 mathematical and complete
 complex and simple
 simple and mathematical
 mathematical and simple
Concept: inductive proofs

(6 pts) Prove by strong induction, with n as the inductive case, that
$\displaystyle \sum _{k=1}^{n}}k=\genfrac{}{}{0.1ex}{}{n(n+1)}{2$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction, with n as the inductive case, that
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{n(n+1)}{2}$, where:
$T\left(0\right)=0$
$T\left(n\right)=T(n1)+n$
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction, with n as the inductive case, that
$\displaystyle \sum _{k=0}^{n}}{k}^{2}=\genfrac{}{}{0.1ex}{}{n(n+1)(2n+1)}{6$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction, with n as the inductive case, that
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{n(n+1)(2n+1)}{6}$, where:
$T\left(0\right)=0$
$T\left(n\right)=T(n1)+{n}^{2}$
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
$\displaystyle \sum _{k=0}^{n}}{k}^{3}=\genfrac{}{}{0.1ex}{}{{n}^{2}{(n+1)}^{2}}{4$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
$T\left(n\right)=\genfrac{}{}{0.1ex}{}{{n}^{2}{(n+1)}^{2}}{4}$,
where:
$T\left(0\right)=0$
$T\left(n\right)=T(n1)+{n}^{3}$
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
$\displaystyle \sum _{k=0}^{n}}{x}^{k}=\genfrac{}{}{0.1ex}{}{{x}^{n+1}1}{x1$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
$T(x,n)=\genfrac{}{}{0.1ex}{}{{x}^{n+1}1}{x1}$,
where:
$T\left(x\mathrm{,0}\right)=1$
$T(x,n)=T(x,n1)+{x}^{n}$
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
the number of nodes in a perfect binary tree with $n$ levels is
${2}^{n}1$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
the number of nodes in a perfect quaternary tree with $n$ levels is
$\genfrac{}{}{0.1ex}{}{{4}^{n}1}{3}$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
the number of nodes in a perfect binary tree with $n$ levels is ${2}^{n}1$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
the number of interior nodes in a perfect binary tree with $n$ levels is
${2}^{n1}1$.
Base case:
Inductive Hypothesis:
Inductive Case:

(6 pts) Prove by strong induction that
the number of child pointers in an arbitrary binary tree
with $n$ nodes is $n1$.
Base case:
Inductive Hypothesis:
Inductive Case:
Concept: rotations in a BST

Which of the following is true for rotations in a BST:
 the number of leaf nodes always increases
 the number of leaf nodes always decreases
 BSTordering is always preserved
 the tree always becomes more balanced

Consider a rightrotation of a node n
upwards in a BST. The former right child of n, if it exists:
 becomes the sibling of n
 becomes the left child of n
 becomes the niece or nephew of n
 becomes the right child of the former parent of n
 remains the right child of n
 becomes the left child of the former parent of n

Consider a rightrotation of a node n
upwards in a BST. The former left child of n, if it exists:
 remains the left child of n
 becomes the niece or nephew of n
 becomes the left child of the former parent of n
 becomes the right child of the former parent of n
 becomes the sibling of n
 becomes the right child of n

Consider a rightrotation of a node n upwards
in a BST.
The former parent of n, assuming it exists:
 becomes the sibling of n
 becomes the right child of n
 becomes the niece or nephew of n
 remains the parent of n
 becomes the left child of n

Consider a rightrotation of a
node n upwards in a BST.
The former sibling of n, assuming it exists:
 becomes the left child of n
 becomes the right child of n
 becomes a grandchild of n
 remains the sibling of n
 becomes the niece or nephew of n
Concept: redblack trees

The number of rotations that occur
after an insertion into
a redblack tree is:
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(n\right)$

The maximum number of rotations that occur
after an insertion into
a redblack tree is:
 $\sim \mathrm{log}n$
 1
 3
 $2$

The maximum number of rotations that occur
after a deletion from
a redblack tree is:
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(\mathrm{log}n\right)$

The maximum number of rotations that occur
after a deletion from
a redblack tree is:
 $3$
 1
 $2$
 $\sim \mathrm{log}n$

Consider a node n in a redblack tree and all paths
from n to a leaf.
Which of the following is a constraint on these trees?
 the number of nodes (red or black) on each path is the same
 each path must start with a black node
 the number of black nodes on each path is the same
 the number of red nodes on each path is the same

Consider a node n in a redblack tree and all paths
from n to a leaf.
Which of the following is a constraint on these trees?
 no black node can have a black parent
 no black node can have a red parent
 no red node can have a black parent
 no red node can have a red parent

Consider a black interior node n in a
redblack tree and any path
from n to a leaf.
Which of the following is a constraint on these trees,
where R is the number of red nodes and B is the
number of black nodes?
 $R\le B$
 $B<R$
 $R\le B+1$
 $B\le R$
 $R=B$
 $B\le R+1$

Consider a red node n in a redblack tree
and the length of
the shortest possible path from n to a leaf, S,
and the length of
the longest possible path from n to a leaf, L.
Which of the following is a constraint on these trees?
 $L=2S$
 $L=2S+1$
 $L=2S1$
 $L=2S2$
 $L=2S+2$

Inserting a value in a redblack tree
and a regular BST, respectively, takes time:
 $\Theta \left(\mathrm{log}n\right)$ and $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(n\right)$ and $\Theta \left(n\right)$
 $\Theta \left(\mathrm{log}n\right)$ and $\Theta \left(n\right)$
 $\Theta \left(1\right)$ and $\Theta \left(\mathrm{log}n\right)$

Suppose one wished to allow more red nodes in a redblack tree,
but still wished this new tree to have the same asymptotic behavior as
before. One could allow more red nodes on any path to a leaf
as long as:
 the number of black nodes between any two red nodes is bounded by a constant.
 the number of red nodes between any two black nodes is bounded by a constant.
 no red node could have a red sibling.
 no black node could have a red parent.

T or F:
A black node in a redblack tree can have one child.

T or F:
A red node in a redblack tree can have one child.

T or F:
A red node in a redblack tree can have a red parent.

T or F:
A black node in a redblack tree can have a black parent.

Choose an order of insertion for seven consecutive integers
such that a redblack tree performs no rotations for any of
the insertions.
 3 2 6 1 0 5 4
 3 2 5 0 1 4 6
 3 2 6 0 1 4 5
 3 1 5 2 0 4 6
 3 2 5 1 0 4 6

Choose an order of insertion for seven consecutive integers
such that a redblack tree performs one rotation for one of the
insertions and no rotations for the other insertions.
 3 2 6 1 0 5 4
 3 1 5 2 0 4 6
 3 2 5 0 1 4 6
 3 2 6 0 1 4 5
 3 2 5 1 0 4 6

Choose an order of insertion for seven consecutive integers
such that a redblack tree performs two rotations for one of the
insertions and no rotations for the other insertions.
 3 2 6 0 1 4 5
 3 1 5 2 0 4 6
 3 2 5 0 1 4 6
 3 2 5 1 0 4 6
 3 2 6 1 0 5 4

Choose an order of insertion for seven consecutive integers
such that a redblack tree performs one rotation for two of the
insertions and no rotations for the other insertions.
 3 2 6 0 1 4 5
 3 2 5 1 0 4 6
 3 2 5 0 1 4 6
 3 1 5 2 0 4 6
 3 2 6 1 0 5 4

Choose an order of insertion for seven consecutive integers
such that a redblack tree performs no rotations
for any of the insertions and yields the most unbalanced
tree.

T or F:
Inserting the following numbers, in the order given,
into an empty BST:
0 4 3 8 1 2 6 5 9 7
yields a tree whose shape is consistent with a redblack tree.

Consider inserting the following numbers, in the order given,
into an empty BST and then coloring the root black and the
other nodes such that
no red node has a red parent:
each node:
0 4 3 8 1 2 6 5 9 7
What is the minimum / maximum number of red nodes possible?
 3 / 4
 3 / 5
 0 / 4
 0 / 5
 the correct answer is not listed
 0 / 6
 0 / 3
 3 / 3

Consider an node with a single child in a redblack tree. If that node has
a sibling and you wish to maximize the number of descendants the sibling
has, what
color is the sibling and how many descendants does it have?
Do not include the null children.
Choose the best answer.
 either black or red / 4
 red / 2
 black / 2
 either black or red / 2
 red / 6
 black / 6
 either black or red / 5
 the correct answer is not listed

Consider inserting the following numbers, in the order given,
into an empty redblack tree:
5 3 8 1 7 6 4
How many rotations and how many node recolorings are performed?
Don't forget what happens on the initial insertion.
 0 / 5
 the correct answer is not listed
 0 / 6
 1 / 6
 1 / 5
 0 / 7
 1 / 7

Consider inserting the following numbers, in the order given,
into an empty BST:
0 4 3 8 1 2 6 5 9 7
What is the minimum number of rotations
that would yield a tree with a shape
consistent with a redblack tree?
 1
 4
 2
 3
 0
 the correct answer is not listed
 5

Consider inserting the following numbers, in the order given,
into an empty redblack tree:
0 4 3 8 1 2 6 5 9 7
After which insertion value does the redblack tree make its first rotation?
 8
 1
 4
 0
 2
 6
 3
 the correct answer is not listed

Consider inserting the following numbers, in the order given,
into an empty redblack tree:
0 4 3 8 1 2 6 5 9 7
Which values, when inserted, cause a rotation?
 3 2 6
 3 2 7
 the correct answer is not listed
 6 7
 2 6 7
 none

Consider inserting the following numbers, in the order given,
into an empty redblack tree:
0 4 3 8 1 2 6 5 9 7
Which values, when inserted, cause a double rotaion?
 2 7
 3 7
 7
 the correct answer is not listed
 6
 3 6
 2 6
Concept: AVL trees

Consider a node n in an AVL tree
and the height of the left subtree of n, LH
and the height of the right subtree of n, RH.
Assuming $LH>RH$,
which of the following is a constraint on these trees?
 $LHRH<2$
 $LHRH<3$
 $LHRH=2$
 $LHRH=1$
 $LHRH=0$

The number of rotations that occur after an insertion into
an AVL tree is, in the worst case:
 $\Theta \left(n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}\phantom{\rule{0.278em}{0ex}}\mathrm{log}n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(\mathrm{log}n\right)$

The number of rotations that occur after an insertion into
an AVL tree is, in the worst case:
 $\Theta \left(\mathrm{log}n\right)$
 1
 $\Theta \left(n\right)$
 2

The number of rotations that occur after an deletion in
an AVL tree is, in the worst case:
 $\Theta \left(n\right)$
 $\Theta \left(n\mathrm{log}n\right)$
 $\Theta \left(1\right)$
 $\Theta \left(\mathrm{log}n\right)$
 $\Theta \left(\mathrm{log}\phantom{\rule{0.278em}{0ex}}\mathrm{log}n\right)$

The number of rotations that occur after an deletion into
an AVL tree is, in the worst case:
 $\Theta \left(n\right)$
 $\Theta \left(\mathrm{log}n\right)$
 2
 1

The minimum number of rotations that occur after an deletion into
an AVL tree is:
 $\Theta \left(\mathrm{log}n\right)$
 1
 2
 $\Theta \left(n\right)$
 0

T or F:
Inserting the following numbers, in the order given,
into an empty BST:
0 4 3 8 1 2 6 5 9 7
yields a tree whose shape is consistent with an AVL tree.

Consider inserting the following numbers, in the order given,
into an empty BST and then computing the balance factors of
each node:
0 4 3 8 1 2 6 5 9 7
What nodes are out of balance, with respect to AVL balance factors?
 0 3 8
 2 5 6 7 9
 0 3
 0 1 2 3
 0 4 3
 the correct answer is not listed
 0 1 3 8

Consider an node with a single child in an AVL tree. If that node has
a sibling, what is the
least / most number of descendants the sibling can have?
 1 / 7
 0 / 6
 0 / 4
 the correct answer is not listed
 0 / 7
 1 / 4
 1 / 5
 1 / 6
 0 / 5

Consider inserting the following numbers, in the order given,
into an empty BST and then computing the balance factors of
each node:
0 4 3 8 1 2 6 5 9 7
Performing a level order traversal of the
tree in which balance factors are displayed,
which of the following sequences of balance factors
is consistent with the above tree?
Assume the height of a null child is zero.
Do not include the null children in the output.
 the correct answer is not listed
 1 0 1 1 1 0 0 0 0 0
 1 0 1 1 1 0 0 0 0 0
 4 0 2 1 1 0 0 0 0 0
 9 2 2 2 1 0 0 0 0 0

Consider inserting the following numbers, in the order given,
into an empty BST and then computing the heights of
each node:
0 4 3 8 1 2 6 5 9 7
Performing a level order traversal of the
tree in which node heights are displayed,
which of the following sequences of heights
is consistent with the above tree?
Assume the height of a null child is zero.
Do not include the null children in the output.
 5 4 3 3 2 2 2 1 1 1
 4 4 3 3 2 2 1 1 0 0
 4 3 2 2 1 1 1 0 0 0
 5 5 4 4 3 3 2 2 1 1
 the correct answer is not listed

Consider inserting the following numbers, in the order given,
into an empty BST:
0 4 3 8 1 2 6 5 9 7
What is the minimum number of rotations
that would yield a tree with balance factors
consistent with an AVL tree?
 the correct answer is not listed
 2
 4
 0
 1
 3
 5

Consider inserting the following numbers, in the order given,
into an empty AVL tree:
0 4 3 8 1 2 6 5 9 7
After which insertion value causes the AVL tree's first rotation?
 2
 the correct answer is not listed
 8
 9
 7
 1
 3
 6
 5

Consider inserting the following numbers, in the order given,
into an empty AVL tree:
0 4 3 8 1 2 6 5 9 7
Which values, when inserted, cause rotations?
 3 7 2 6
 7 2 6
 the correct answer is not listed
 7 6
 3 7 2

Consider inserting the following numbers, in the order given,
into an empty AVL tree:
0 4 3 8 1 2 6 5 9 7
Which values, when inserted, cause a double rotaion?
 7
 2 6
 2
 3 7
 6
 3
 the correct answer is not listed

Choose an order of insertion for seven consecutive integers
such that an AVL tree performs no rotations for any of
the insertions.

Choose an order of insertion for seven consecutive integers
such that an AVL tree performs one rotation for one of the
insertions and no rotations for the other insertions.

Choose an order of insertion for seven consecutive integers
such that an AVL tree performs two rotations for one of the
insertions and no rotations for the other insertions.

Choose an order of insertion for seven consecutive integers
such that an AVL tree performs one rotation each for two of the
insertions and no rotations for the other insertions.

Choose an order of insertion for seven consecutive integers
such that an AVL tree performs no rotations
for any of the insertions and yields the most unbalanced
tree.
Concept: amortized analysis

Suppose a dynamic array was implemented so that growing the
array increased the capacity by 1000 elements.
What is the worstcase cost of the append operation?
 constant
 quadratic
 log linear
 linear

Suppose a dynamic array was implemented so that growing the
array increased the capacity by 2%. What is the
amortized and worstcase costs of the append operation?
 log and linear
 constant and linear
 quadratic and quadratic
 linear and linear

Suppose a dynamic array was implemented so that growing the
array increased the capacity by 100 elements. What is the
amortized and worstcase costs of the append operation?
 log and linear
 quadratic and quadratic
 constant and linear
 linear and linear

Consider a dynamic fillable array which grows by doubling in size.
Which is a valid equation for calculating the total cost incurred
when insertion ${2}^{i}+1$ is made?
Assume the individual cost of an insert when there is room is 1 and
the individual cost of an insert when there is no room is ${2}^{i}+1$.
 $3n2$
 $3n1$
 $2n2$
 $2n1$
 $2n3$
 $3n3$

Consider a dynamic fillable array which grows from size n
to size $2n+1$ each time the array is filled.
Which is a valid equation for calculating the total cost incurred
when insertion ${2}^{i}$ is made?
Assume the individual cost of an insert when there is room is 1 and
the individual cost of an insert when there is no room is ${2}^{i}$.
 $3n3$
 $3n6$
 $3n\mathrm{log}n2$
 $2n$
 $3n1$
 $2n1$

Consider a dynamic fillable array which grows by doubling in size.
Let S represent the number of filled slots and E, the number
of empty slots, and C, the capacity of the array.
Which is a valid potential function for proving the amoritized
cost of an insert is constant?
 $E+2C$
 $2SC$
 $SE$
 $S+2E$
 $2SE$
 $S+E$

Consider implementing a queue with two stacks. Enqueues are
translated to pushes onto the first stack. For a dequeue,
if the second stack is empty,
each element on the first stack is popped and
pushed, in turn, onto the second stack.
In either case,
the item popped from the second stack is returned.
The worstcase times for enqueue and dequeue are:
 $\Theta \left(1\right)$ and $\Theta \left(n\right)$
 $\Theta \left(n\right)$ and $\Theta \left(1\right)$
 $\Theta \left(n\right)$ and $\Theta \left(n\right)$
 $\Theta \left(1\right)$ and $\Theta \left(1\right)$

Consider implementing a queue with two stacks. Enqueues are
translated to pushes onto the first stack, V. For a dequeue,
if the second stack, W, is empty,
each element on the first stack is popped and
pushed, in turn, onto the second stack.
The total work of this transfer is the number of elements popped plus the
number of elements pushed.
In either case,
the item popped from the second stack is returned.
The number of elements on stack V is denoted ${V}_{S}$ and the
number of elements on stack W is denoted ${W}_{S}$.
Which of the following potential functions can be used to
show an amortized bound of $\Theta \left(1\right)$ for operations
on this kind of queue?
 $\Phi ={V}_{s}$
 $\Phi =2{V}_{s}$
 $\Phi ={V}_{s}+{W}_{s}$
 $\Phi ={V}_{s}+2{W}_{s}$

Suppose a data structure has
operation A with a real cost of 1 and
operation B with a real cost of $2n+1$.
After an A operation, n increases by 1 while
after a B operation, n decreases to zero.
Which of the following potential functions can be used to
show an amortized bound of $\Theta $(1) for operations A and B
on this data structure?
 $Phi=n.$
 $\Phi =3n$
 $Phi=2n.$

Suppose a data structure has
operation A with a real cost of $3n+1$ and
operation B with a real cost of $\genfrac{}{}{0.1ex}{}{3}{2}n+1$.
After an A operation, n decreases to $\genfrac{}{}{0.1ex}{}{1}{4}n$ while
after a B operation, n decreases to $\genfrac{}{}{0.1ex}{}{5}{8}n$.
Which of the following potential functions can be used to
show an amortized bound of $\Theta $(1) for operations A and B
on this data structure?
 $\Phi =\genfrac{}{}{0.1ex}{}{3}{2}n$
 $\Phi =4n$
 $\Phi =3n$

Suppose a data structure has
operation A with a real cost of 1 and
operation B with a real cost of $k+n$.
After an A operation, n increases by 1.
After a B operation, n decreases to $k+1$.
Which of the following potential functions can be used to
show an amortized bound of $\Theta $(1) for A operations
and $\Theta \left(k\right)$ for B operations?
 $\Phi =n$
 $\Phi =3n$
 $\Phi =2n$
Concept: Graphs

What is the primary characteristic of a directed graph?
 the vertices are all reachable
 at least one vertex is unreachable
 the edges are bidirectional
 the edges are unidirectional

What is the primary characteristic of a weighted graph?
 the edge count exceeds vertex count
 the vertex count exceeds some threshold
 each vertex has an associated weight
 each edge has an associated weight

What is the primary characteristic of an undirected, simple graph?
 there is at most one edge between any two vertices
 the edge count exceeds or equals the vertex count
 the edge count is less than the vertex count
 the termini of an edge may be the same vertex

What is the degree of a vertex in an undirected, simple graph?
 the total number of paths emanating from the vertex
 the total number of edges emanating from the vertex
 the count of vertices reachable from that vertex
 the count of vertices not reachable from that vertex

What is the primary characteristic of a undirected, simple, connected graph?
 each vertex has a edge that connects to itself
 a path exists between every pair of vertices
 there is at least one edge
 an edge exists between every pair of vertices

What is the primary characteristic of an undirected, simple, regular graph?
 all vertices have the same weight
 all edges have the same weight
 all edges terminate at the same vertex
 all vertices have the same degree

What is the primary characteristic of an undirected, simple, complete graph?
Choose the most general answer.
 all vertices have a degree greater than some threshold
 there exists an edge between every pair of vertices
 each vertex has two edges or no edges
 there exists a path between every pair of vertices

What is the primary characteristic of an undirected, simple, connected,
acyclic graph?
Choose the most general answer.
 the vertex count is one greater than the edge count
 no edge has a single vertex as its termini
 there are at least two unique paths between any two vertices
 the vertex count is equal to the edge count

What is the primary characteristic of a planar graph?
 the maximum degree of a vertex is 4
 it can be drawn in a plane with no crossed edges
 when drawn in a plane, it must have crossed edges
 the maximum degree of a vertex is 3
Graph traversals

What is a walk?
Choose the most general answer.
 a sequence of edges such that ${e}_{i}$ and ${e}_{i+1}$ have no common vertex
 a sequence of vertices with an edge between ${v}_{i}$ and ${v}_{i+1}$
 a set of edges that have one vertex in common
 a sequence of vertices with no edge between ${v}_{i}$ and ${v}_{i+1}$

What is a trail?
Choose the most general answer.
 a walk with no edge appearing more than once
 a walk with at least one edge appearing twice (or more)
 a walk with at least one vertex appearing twice (or more)
 a walk with no vertex appearing more than once

What is the primary characteristic of a path?
 a trail with all edges appearing at least once
 a trail with no vertex appearing more than twice
 a trail with all vertices appearing at least once
 a trail with no vertex appearing more than once

What is an Euler trail?
Choose the most general answer.
 the longest trail in a graph
 a trail which invovles every vertex, except one, exactly once
 a trail which invovles every vertex exactly once
 a trail which invovles every edge exactly once

What is a Hamiltonian path?
Choose the most general answer.
 the longest path in a graph
 the shortest path in a graph
 a path which involves every edge
 a path which involves every vertex

T or F:
An Euler trail is always the longest trail in an undirected graph.

T or F:
A Hamiltonian path, if it exists,
is always the longest path in an undirected graph.

The longest path in an undirected graph is bounded by:
 the maximum degree of a graph
 the number of edges
 the number of vertices
 the minimum degree of a graph

T or F:
All connected, undirected graphs have a spanning tree.

Refering to graphs, Kruskal's algorithm is used to find:
 the shortest path between two vertices
 allpairs shortest paths
 a minimum spanning tree
 the longest path with the least weight

Refering to graphs, Dijkstra's algorithm is used to find:
 allpairs shortest paths
 the longest path with the least weight
 a minimum spanning tree
 the shortest path between a source vertex and the other vertices

Refering to graphs, Prim's algorithm is used to find:
 allpairs shortest paths
 the longest path with the least weight
 the shortest path between two vertices
 a minimum spanning tree

Refering to graphs, the FloydWarshall algorithm is used to find:
 the longest path with the least weight
 a minimum spanning tree
 allpairs shortest paths
 the shortest path

Suppose $E=\omega \left(V\right)$. What is the asymptotic running
time of Kruskal's Algorithm? Choose the simplest answer.
 $\Theta (E\mathrm{log}E+V\mathrm{log}E)$
 $\Theta (E\mathrm{log}E+V\mathrm{log}V)$
 $\Theta (E+V\mathrm{log}V)$
 $\Theta \left(E\right)$
 $\Theta \left(E\mathrm{log}E\right)$
 $\Theta (E+V)$

Suppose $E=\Theta \left(V\right)$. What is the asymptotic running
time of Prim's Algorithm? Choose the simplest answer.
 $\Theta (E\mathrm{log}E+V\mathrm{log}V)$
 $\Theta (E+V\mathrm{log}V)$
 $\Theta (E+V)$
 $\Theta \left(E\right)$
 $\Theta (E\mathrm{log}E+V\mathrm{log}E)$
 $\Theta \left(E\mathrm{log}E\right)$

T or F:
Suppose you kept track of the level number for each vertex w in
a breadthfirst search of a simple, undirected, unweighted graph, starting
from a vertex v. The level numbers of each w would correspond
to the shortest path distance.

T or F:
For a simple, undirected graph, $\Theta \left(E\mathrm{log}E\right)=\Theta \left(E\mathrm{log}V\right)$

Consider running Kruskal's algorithm on the complete graph ${K}_{n}$,
processing the first i edges.
What is the smallest value of i that could yield the final result?
 $\genfrac{}{}{0.1ex}{}{n(n+1)}{2}$
 $\genfrac{}{}{0.1ex}{}{n(n+1)}{2}1$
 $\genfrac{}{}{0.1ex}{}{n(n1)}{2}$
 n
 $\genfrac{}{}{0.1ex}{}{n(n1)}{2}1$
 n1

Consider running Dijkstra's algorithm using a linked list (with a tail
pointer) as the basis for a priority queue. What is the asymptotic run time
for the algorithm?
 $\Theta \left({V}^{3}E\right)$
 the correct answer is not listed
 $\Theta \left(V{E}^{2}\right)$
 $\Theta \left({V}^{3}\mathrm{log}V\right)$
 $\Theta \left({V}^{2}\mathrm{log}V\right)$
 $\Theta \left({V}^{2}E\right)$
Concept: The classes $\mathcal{P}$ and $NP$

A problem can be in $\mathcal{P}$ and not in $NP$.
 True
 Not known
 False

A problem can be in $NP$ and not in $\mathcal{P}$.
 True
 Not known
 False

All problems are in $\mathcal{P}$.
 False
 True
 Not known

All problems are in $NP$.
 Not known
 False
 True

$NP$ stands for:
 Nondeterministic Polynomial.
 Nonintractable Program.
 Nonexponential Program.
 NonPolynomial.

T or F:
A constant time algorithm is in $\mathcal{P}$.

T or F:
A linear time algorithm is in $\mathcal{P}$.

T or F:
A constant time algorithm is in $NP$.

T or F:
A linear time algorithm is in $NP$.

Someone shows you a correct algorithm for problem A
whose solution can be verified in polynomial time.
You can conclude:
 problem A is in $NP$
 nothing about whether problem A is in $NP$ or not.
 problem A is not in $NP$

Someone proves that for a correct algorithm for problem A,
solutions must be verified in at least exponential time.
You can conclude:
 problem A is in $NP$
 nothing about whether problem A is in $NP$ or not.
 problem A is not in $NP$

Someone shows you a correct polynomial time algorithm for problem A.
You can conclude:
 nothing about whether problem A is in $\mathcal{P}$ or not.
 problem A is in $\mathcal{P}$
 problem A is not in $\mathcal{P}$

Someone shows you a correct exponential time algorithm for problem A
whose solution can be verified in polynomial time.
You can conclude:
 nothing about whether problem A is in $\mathcal{P}$ or not.
 problem A is not in $\mathcal{P}$
 problem A is in $\mathcal{P}$

Someone shows you a correct polynomial time algorithm for problem A.
You can conclude:
 nothing about whether problem A is in $NP$ or not.
 problem A is in $NP$
 problem A is not in $NP$

Which one of the following is not a valid way to prove
a problem is in $NP$:
 show that a solution can be verified in polynomial time on a nondeterministic computer.
 show that a solution can be found in polynomial time on a nondeterministic computer.
 show that a solution can be verified in polynomial time on a deterministic computer.
 show that a solution can be found in polynomial time on a deterministic computer.
Concept: $NP$completeness

To show that a problem A is $NP$complete, one task is to:
 show A is not in $NP$.
 show A is not in $\mathcal{P}$.
 show A is in $\mathcal{P}$.
 show A is in $NP$.

Suppose B is an $NP$complete problem.
To show that a problem A is $NP$complete, one could:
 show a polynomial time/space reduction from A to B.
 show a exponential time/space reduction from B to A.
 show an exponential time/space reduction from A to B.
 show a polynomial time/space reduction from B to A.

Another way of stating “a reduction from A to B” is:
 convert an algorithm for B to an algorithm for A
 solve Atype problems with an algorithm for B
 solve Btype problems with an algorithm for A
 convert an algorithm for A to an algorithm for B
Concept: If $\mathcal{P}=NP$?

If $\mathcal{P}$ = $NP$, then all problems in $\mathcal{P}$ are in $NP$.
 Not known
 True
 False

If $\mathcal{P}$ = $NP$, then all problems in $NP$ are in $\mathcal{P}$.
 True
 Not known
 False

If $\mathcal{P}$ != $NP$, then there exist problems in $\mathcal{P}$ that are not in $NP$.
 True
 Not known
 False

If $\mathcal{P}$ != $NP$, then there exist problems in $NP$ that are not in $\mathcal{P}$.
 True
 False
 Not known
Concept: Proving $\mathcal{P}=NP$.

Factoring is in $NP$. Currently, the best known algorithm on a
conventional computer takes exponential time. If factoring is
proved to take at least exponential time, what is the effect on
the question $\mathcal{P}$ = $NP$?
 $\mathcal{P}$ != $NP$
 $\mathcal{P}$ = $NP$
 the question is still unanswered

Factoring is in $NP$. Currently, the best known algorithm on a
conventional computer takes exponential time. If factoring is
shown to take take polynomial time, what is the effect on
the question $\mathcal{P}$ = $NP$?
 $\mathcal{P}$ = $NP$
 the question is still unanswered
 $\mathcal{P}$ != $NP$

Factoring is in $NP$ and the best known
algorithm takes exponential time. In the past, a linear time algorithm
was discovered for quantum computers.
What is the effect on the question $\mathcal{P}$ = $NP$?
 $\mathcal{P}$ = $NP$? is still unanswered.
 $\mathcal{P}$ != $NP$, but just for quantum computers
 $\mathcal{P}$ != $NP$ for all types of computers.
 $\mathcal{P}$ = $NP$ for all types of computers.
 $\mathcal{P}$ = $NP$, but just for quantum computers

Subset Sum is $NP$complete.
Currently, the best known algorithm on a
conventional computer takes exponential time. If Subset Sum is
proved to take at least exponential time,
what is the effect on the question $\mathcal{P}$ = $NP$?
 $\mathcal{P}$ = $NP$
 the question is still unanswered
 $\mathcal{P}$ != $NP$

Subset Sum is $NP$complete.
Currently, the best known algorithm on a
conventional computer takes exponential time. If solving Subset Sum
can be
shown to take polynomial time, what is the effect on
the question $\mathcal{P}$ = $NP$?
 $\mathcal{P}$ != $NP$
 $\mathcal{P}$ = $NP$
 the question is still unanswered

In the past, it was shown how to solve Hamiltonian Path
(an $NP$complete
problem) in linear time, using a DNAbased computer. However,
the algorithm takes a factorial number of DNA strands, which need
to be created each time. This means:
 $\mathcal{P}$ = $NP$ for all types of computers.
 $\mathcal{P}$ != $NP$, but just for DNAbased computers
 $\mathcal{P}$ != $NP$ for all types of computers.
 $\mathcal{P}$ = $NP$? is still unanswered.
 $\mathcal{P}$ = $NP$, but just for DNAbased computers

T or F:
$\mathcal{P}$ = $NP$ is just another way of saying,
for problems in $NP$,
finding a solution is no harder than verifying a solution.