Prerequisite Concepts for Data Structures

Algorithms (Version 4)
Printable Version

Concept: linear selection

  1. Suppose you wish to find both the minimum and maximum values in an array of n values, n being odd. Consider this algorithm:
    1. Make a pass through the array and find the minimum
    2. Make a pass through the array and find the maximum
    3. 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?
    1. 2 n - 2
    2. 2 n - 1
    3. 2 n
    4. 2 n + 2
    5. 2 n + 1
  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:
    1. Set the maximum and minimum to the first value in the array
    2. Make a pass through the array (i = 1; i < n; i += 2)
    3. Compare A[i] with A[i+1]
    4. Update the minimum if the smaller of the two is less
    5. Update the maximum if the larger of the two is greater
    6. 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?
    1. 3 n - 1 2
    2. 3 n - 1
    3. 3 n - 3
    4. 2 n - 3
    5. 3 n - 1 2 + 2
    6. 3 n
  1. Consider running the linear selection algorithm on an array with n = 5 k 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.
    1. 3 n 10 + 3
    2. 5 n 10 + 2
    3. 3 n 5 + 3
    4. 3 n 5 + 2
    5. 2 n 5 + 3
    6. 3 n 10 + 2
    7. 2 n 5 + 2
    8. 5 n 10 + 3
  1. Consider running the linear selection algorithm on an array with n = 3 k 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.
    1. 3 n 6 + 1
    2. 2 n 3 + 2
    3. 2 n 3 + 1
    4. 3 n 6 + 2
    5. 2 n 6 + 2
    6. 2 n 6 + 1
    7. n 3 + 1
    8. n 3 + 2
  1. Consider running the linear selection algorithm on an array with n = 7 k 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.
    1. 11 n 14 + 2
    2. 3 n 14 + 2
    3. 4 n 14 + 3
    4. 3 n 7 + 2
    5. 3 n 7 + 3
    6. 3 n 14 + 3
    7. 4 n 14 + 2
    8. 11 n 14 + 3
  1. 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.
    1. T ( n ) = T ( n 7 ) + T ( 10 n 14 ) + θ ( n )
    2. T ( n ) = T ( n 7 ) + T ( 11 n 14 ) + θ ( n )
    3. T ( n ) = T ( n 7 ) + T ( 5 n 7 ) + θ ( n )
    4. T ( n ) = T ( n 7 ) + T ( 4 n 7 ) + θ ( n )
    5. T ( n ) = T ( n 7 ) + T ( 4 n 14 ) + θ ( n )
    6. T ( n ) = T ( n 7 ) + T ( 6 n 7 ) + θ ( n )
  1. 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.
    1. T ( n ) = T ( n 3 ) + T ( n 3 ) + θ ( n )
    2. T ( n ) = T ( n 3 ) + T ( 2 n 3 ) + θ ( n )
    3. T ( n ) = T ( n 3 ) + T ( 2 n 5 ) + θ ( n )
    4. T ( n ) = T ( n 3 ) + T ( 5 n 6 ) + θ ( n )
    5. T ( n ) = T ( n 3 ) + T ( n 6 ) + θ ( n )
    6. T ( n ) = T ( n 3 ) + T ( n 2 ) + θ ( n )
  1. 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.
    1. T ( n ) = T ( n 5 ) + T ( 2 n 5 ) + θ ( n )
    2. T ( n ) = T ( n 5 ) + T ( 9 n 10 ) + θ ( n )
    3. T ( n ) = T ( n 5 ) + T ( n 2 ) + θ ( n )
    4. T ( n ) = T ( n 5 ) + T ( 4 n 5 ) + θ ( n )
    5. T ( n ) = T ( n 5 ) + T ( 7 10 ) + θ ( n )
    6. T ( n ) = T ( n 5 ) + T ( 3 n 5 ) + θ ( n )
  1. T or F: If the linear selection algoritm uses groups of three to find the median of medians, the asymptotic run time is still θ ( n ) .
  1. T or F: If the linear selection algoritm uses groups of seven to find the median of medians, the asymptotic run time is still θ ( n ) .

Concept: decision trees

  1. In proving a tight lower bound for a class of algorithms, one tries to establish, over all possible algorithms:
    1. the best possible worst case
    2. the best possible best case
    3. the worst possible best case
    4. the worst possible worst case
  1. 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.
    1. approximately n log n
    2. n - 1
    3. n
    4. 1
    5. n !
    6. approximately log n
  1. 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.
    1. approximately n log n
    2. approximately log n
    3. n !
    4. 1
    5. n - 1
    6. n
  1. In an efficient decision tree for comparison sorts of n numbers, what does the shortest path from the root to a leaf represent?
    1. the worst case behavior of the sort
    2. the best case behavior of the sort
    3. the average case behavior of the sort
    4. nothing, the longest path is what's important
  1. An efficient decision tree for comparison sorts of n numbers has how many leaves?
    1. 2 n
    2. log n
    3. n log n
    4. n !
  1. Deriving a tight lower time bound for comparison sorts, based upon an efficient decision tree, yields:
    1. unbounded
    2. Ω ( n log n )
    3. O ( n log n )
    4. ω ( n log n )
    5. O ( n )
    6. Ω ( n )

Concept: linear sorting fundamentals

  1. Stability in a sort means:
    1. the order of ties in the output reflects the input
    2. the sort can work on any kind of number (integers, reals, etc.)
    3. the asymptotic run time does not vary upon the input
  1. The best case behavior for insertion sort is:
    1. quadratic
    2. linear
    3. exponential
    4. log linear
  1. T or F: A linear-time sort does not compare entire keys with one another.
  1. T or F: A linear-time 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.
  1. Counting sort is:
    1. always unstable
    2. always stable
    3. stable if lower indexed elements from the input array are transferred to higher indexed elements in the output array.
    4. stable if higher indexed elements from the input array are transferred to higher indexed elements in the output array.
  1. Suppose you are to sort n numbers using counting sort. What size should the C array be?
    1. greater than n
    2. there's not enough information
    3. less than n
    4. equal to n
  1. 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:
    1. [2,0,2,3,0,1]
    2. [2,0,5,2,3,0,3,3]
    3. [0,0,2,2,3,3,3,5]
    4. [2,2,4,6,7,8]
    5. [2,2,4,7,7,8]
  1. 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:
    1. [2,0,2,3,0,1]
    2. [2,2,4,7,7,8]
    3. [0,0,2,2,3,3,3,5]
    4. [2,0,5,2,3,0,3,3]
    5. [2,2,4,6,7,8]
  1. 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:
    1. 0, at index 1
    2. 4, at index 5
    3. 3, at index 6
    4. 2, at index 3
    5. 1, at index 0
    6. 5, at index 7
  1. 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:
    1. Θ ( n k )
    2. Θ ( n log k )
    3. Θ ( n k )
    4. Θ ( n + k )
  1. 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 ( n ) , then the time complexity of counting sort is:
    1. Θ ( k log n )
    2. Θ ( n )
    3. Θ ( k )
    4. Θ ( n log k )
    5. Θ ( n 2 )
    6. Θ ( k 2 )
  1. 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.
  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 C[A[i]] += 1 is changed to C[A[i]-LB] += 1.
  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[i-LB]]-1] = A[i].
  1. 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.
  1. 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
    1. θ ( n + k )
    2. θ ( n k + n )
    3. θ ( n log k )
    4. θ ( k log n )
    5. θ ( n )
    6. θ ( k )

Concept: linear sorting -- radix

  1. Suppose the recurrence equation T ( p , q ) = T ( p , q - 1 ) + θ ( p ) is used to describe radix sort. Considering only the sorting of the numbers on a particular digit, which sort is consistent with that equation?
    1. counting sort
    2. radix sort
    3. mergesort sort
    4. selection sort
  1. Suppose the recurrence equation T ( p , q ) = T ( p , q - 1 ) + θ ( p log p ) is used to describe radix sort. Considering only the sorting of the numbers on a particular digit, which sort is consistent with that equation?
    1. counting sort
    2. selection sort
    3. mergesort sort
    4. radix sort
  1. Suppose the recurrence equation T ( p , q ) = T ( p , q - 1 ) + θ ( p 2 ) is used to describe radix sort. Considering only the sorting of the numbers on a particular digit, which sort is consistent with that equation?
    1. mergesort sort
    2. selection sort
    3. radix sort
    4. counting sort
  1. Suppose the recurrence equation T ( p , q ) = T ( p , q - 1 ) + θ ( p ) is used to describe radix sort. Which variable in the equation refers to the number of digits?
    1. q
    2. p
    3. d
    4. n
  1. Consider using radix sort for sorting the following numbers:
        558
        354
        318
        622
    
    After the first pass, the order of the numbers is:
    1. 318, 354, 558, 622
    2. 354, 318, 558, 622
    3. 622, 354, 558, 318
    4. 622, 354, 318, 558
    5. 622, 558, 318, 354
    6. 622, 558, 354, 318
  1. 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 Θ ( n ) time. Then radix sorting takes time:
    1. Θ ( n log n )
    2. Θ ( n m )
    3. Θ ( n log m )
    4. Θ ( m log n )
  1. 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 Θ ( n log n ) time. Then radix sorting takes time:
    1. Θ ( n log ( m + n ) )
    2. Θ ( n log ( m n ) )
    3. Θ ( n log m )
    4. Θ ( m n log n )
  1. 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.
  1. Consider the sort used for each pass of radix sort. Must the auxiliary sort be stable?
    1. No, because there can be no ties in radix sort.
    2. No, because radix sort works even if the auxilliary sort is unstable.
    3. Yes, because swapping ties can undo the work of previous passes
    4. Yes, because swapping ties can undo the work of future passes
  1. 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

  1. T or F: If bucket sort uses equally-sized buckets, then the distribution of the incoming numbers need not be uniform for the sort to run in expected linear time.
  1. Consider using bucket sort to sort n numbers evenly distributed over the range 0 to m. Roughly, how many buckets should you use?
    1. m
    2. m n
    3. n m
    4. n
  1. Consider using bucket sort to sort n numbers evenly distributed over the range 0 to m. Roughly, what size bucket should you use?
    1. n m
    2. m n
    3. n
    4. m
  1. Consider using bucket sort to sort n non-negative numbers evenly distributed over the range 0 to m. The range of the first bucket should be:
    1. 0 to m n
    2. n m to 2 n m
    3. m n to 2 m n
    4. 0 to n m
  1. Consider using bucket sort to sort n non-negative numbers evenly distributed over the range 0 to m. The average count of numbers in a bucket is:
    1. m n
    2. 0
    3. n m
    4. 1
  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:
    1. Θ ( n 2 ) , because insertion sort is quadratic in the worst case
    2. Θ ( n log n ) , because insertion sort is log-linear in the average case
    3. Θ ( 1 )
    4. Θ ( n ) , because insertion sort is linear in the best case
  1. Consider using bucket sort to sort n non-negative numbers evenly distributed over the range 0 to m. The expected running time is:
    1. constant
    2. quadratic
    3. linear
    4. log-linear
  1. Consider using bucket sort to sort n non-negative 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:
    1. linear
    2. cubic
    3. quadratic
    4. constant
  1. 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

  1. Stooge sort has the following algorithm. Recursively sort the lower two-thirds of an array, then recursively sort the upper two-thirds, then recursively sort the lower two-thirds 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?
    1. T ( n ) = 3 T ( n 2 ) + Θ ( n )
    2. T ( n ) = 3 T ( 2 n 3 ) + Θ ( 1 )
    3. T ( n ) = 2 T ( 3 n 2 ) + Θ ( 1 )
    4. T ( n ) = 2 T ( n 3 ) + Θ ( 1 )
    5. T ( n ) = 3 T ( n 2 ) + Θ ( log n )
  1. 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?
    1. T ( n ) = T ( n - 1 ) + Θ ( n )
    2. T ( n ) = 4 T ( n 2 ) + Θ ( 1 )
    3. T ( n ) = 2 T ( n 2 ) + Θ ( 1 )
    4. T ( n ) = 2 T ( n 2 ) + Θ ( n )
  1. 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?
    1. T ( n ) = 2 T ( n - 1 ) + Θ ( 1 )
    2. T ( n ) = T ( n 2 ) + Θ ( 1 )
    3. T ( n ) = 2 T ( n 2 ) + Θ ( n )
    4. T ( n ) = 2 T ( n 2 ) + Θ ( log n )
    5. T ( n ) = 2 T ( n 2 ) + Θ ( 1 )
    6. T ( n ) = T ( n 2 ) + Θ ( n )
    7. T ( n ) = T ( n 2 ) + Θ ( log n )
  1. 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?
    1. T ( n ) = 2 T ( n 2 ) + Θ ( 1 )
    2. T ( n ) = 2 T ( n 2 ) + Θ ( n )
    3. T ( n ) = 2 T ( n 2 ) + Θ ( n 2 )
    4. T ( n ) = T ( n 2 ) + Θ ( n 2 )
    5. T ( n ) = T ( n 2 ) + Θ ( log n )
    6. T ( n ) = T ( n 2 ) + Θ ( n )
    7. T ( n ) = 2 T ( n - 1 ) + Θ ( 1 )
  1. The recurrence equation T ( n ) = T ( n - 1 ) + Θ ( n ) describes which sort, in the worst case?
    1. quick sort
    2. heap sort
    3. radix sort
    4. merge sort
  1. Consider using selection sort to sort a previously sorted array. Which of the following recurrence equations describes this situation?
    1. T ( n ) = 2 T ( n 2 ) + Θ ( 1 )
    2. T ( n ) = T ( n - 1 ) + Θ ( 1 )
    3. T ( n ) = 2 T ( n - 1 ) + Θ ( 1 )
    4. T ( n ) = 2 T ( n - 1 ) + Θ ( n )
    5. T ( n ) = 2 T ( n 2 ) + Θ ( n )
    6. T ( n ) = T ( n - 1 ) + Θ ( n )

Concept: identifying cases of the master recurrence theorem

  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 4 T ( n 4 ) + n 2 fall?
    1. case 2
    2. the equation is not in the correct form
    3. case 3
    4. between case 1 and case 2
    5. case 1
    6. between case 2 and case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 2 ) + n 2 fall?
    1. between case 2 and case 3
    2. case 3
    3. case 2
    4. between case 1 and case 2
    5. case 1
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 4 T ( n 2 ) + n 2 fall?
    1. case 3
    2. case 1
    3. between case 1 and case 2
    4. case 2
    5. between case 2 and case 3
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = T ( n 2 ) + 2 n fall?
    1. case 3
    2. between case 2 and case 3
    3. between case 1 and case 2
    4. case 1
    5. the equation is not in the correct form
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 n T ( n 2 ) + n n fall?
    1. case 2
    2. case 1
    3. case 3
    4. the equation is not in the correct form
    5. between case 2 and case 3
    6. between case 1 and case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = T ( n - 1 ) + 1 fall?
    1. case 1
    2. between case 2 and case 3
    3. between case 1 and case 2
    4. the equation is not in the correct form
    5. case 2
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 T ( n - 2 ) + n fall?
    1. the equation is not in the correct form
    2. case 2
    3. between case 2 and case 3
    4. between case 1 and case 2
    5. case 1
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 16 T ( n 4 ) + n fall?
    1. the equation is not in the correct form
    2. case 1
    3. case 3
    4. case 2
    5. between case 2 and case 3
    6. between case 1 and case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 T ( n 2 ) + n log n fall?
    1. between case 1 and case 2
    2. between case 2 and case 3
    3. case 3
    4. the equation is not in the correct form
    5. case 1
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 2 ) + n log n fall?
    1. case 1
    2. between case 2 and case 3
    3. between case 1 and case 2
    4. the equation is not in the correct form
    5. case 2
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 T ( n 2 ) + n log n fall?
    1. case 3
    2. between case 1 and case 2
    3. the equation is not in the correct form
    4. case 1
    5. between case 2 and case 3
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 T ( n 4 ) + n 0.51 fall?
    1. case 1
    2. case 3
    3. case 2
    4. the equation is not in the correct form
    5. between case 1 and case 2
    6. between case 2 and case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 1 2 T ( n 2 ) + 1 fall?
    1. case 3
    2. case 2
    3. case 1
    4. between case 1 and case 2
    5. between case 2 and case 3
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 16 T ( n 4 ) + n ! fall?
    1. case 1
    2. case 3
    3. case 2
    4. between case 1 and case 2
    5. between case 2 and case 3
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 2 T ( n 2 ) + log n fall?
    1. the equation is not in the correct form
    2. between case 2 and case 3
    3. case 1
    4. case 3
    5. between case 1 and case 2
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 2 ) + n fall?
    1. case 1
    2. case 2
    3. case 3
    4. between case 1 and case 2
    5. the equation is not in the correct form
    6. between case 2 and case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 3 ) + n fall?
    1. case 3
    2. case 2
    3. the equation is not in the correct form
    4. between case 2 and case 3
    5. between case 1 and case 2
    6. case 1
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 4 T ( n 2 ) + n fall?
    1. case 2
    2. case 3
    3. between case 1 and case 2
    4. between case 2 and case 3
    5. case 1
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 4 ) + n log n fall?
    1. case 1
    2. the equation is not in the correct form
    3. case 2
    4. between case 1 and case 2
    5. between case 2 and case 3
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 3 T ( n 3 ) + n 2 fall?
    1. between case 1 and case 2
    2. case 2
    3. case 1
    4. between case 2 and case 3
    5. the equation is not in the correct form
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 6 T ( n 3 ) + n 2 log n fall?
    1. the equation is not in the correct form
    2. between case 1 and case 2
    3. between case 2 and case 3
    4. case 2
    5. case 3
    6. case 1
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 4 T ( n 2 ) + n log n fall?
    1. case 3
    2. case 2
    3. between case 2 and case 3
    4. case 1
    5. between case 1 and case 2
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 64 T ( n 8 ) - n log n fall?
    1. case 1
    2. between case 2 and case 3
    3. case 3
    4. case 2
    5. between case 1 and case 2
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 7 T ( n 7 ) + n 2 fall?
    1. case 2
    2. case 1
    3. between case 2 and case 3
    4. the equation is not in the correct form
    5. between case 1 and case 2
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 7 T ( n 2 ) + n 2 fall?
    1. between case 2 and case 3
    2. between case 1 and case 2
    3. case 2
    4. the equation is not in the correct form
    5. case 3
    6. case 1
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 7 T ( n 3 ) + n 2 fall?
    1. case 3
    2. the equation is not in the correct form
    3. case 1
    4. between case 2 and case 3
    5. between case 1 and case 2
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 4 T ( n 2 ) + log n fall?
    1. case 1
    2. between case 1 and case 2
    3. case 3
    4. between case 2 and case 3
    5. the equation is not in the correct form
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 2 ) + log n fall?
    1. between case 1 and case 2
    2. the equation is not in the correct form
    3. between case 2 and case 3
    4. case 2
    5. case 1
    6. case 3
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 2 ) + n fall?
    1. between case 2 and case 3
    2. case 1
    3. case 2
    4. case 3
    5. between case 1 and case 2
    6. the equation is not in the correct form
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 5 3 ) + n 3 fall?
    1. between case 2 and case 3
    2. case 1
    3. between case 1 and case 2
    4. case 3
    5. the equation is not in the correct form
    6. case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 5 3 ) + n 3 log n fall?
    1. case 3
    2. between case 2 and case 3
    3. the equation is not in the correct form
    4. case 2
    5. case 1
    6. between case 1 and case 2
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 5 ) + n 2 log n fall?
    1. between case 1 and case 2
    2. case 2
    3. the equation is not in the correct form
    4. case 3
    5. between case 2 and case 3
    6. case 1
  1. In terms of the master recurrence theorem, where does the equation T ( n ) = 5 T ( n 5 ) + n log n fall?
    1. the equation is not in the correct form
    2. between case 1 and case 2
    3. case 3
    4. between case 2 and case 3
    5. case 2
    6. case 1

Concept: using the master recurrence theorem

  1. Using the master recurrence theorem, what is the solution of T ( n ) = 4 T ( n 4 ) + n 2 ?
    1. Θ ( n 3 log n )
    2. Θ ( n 3 )
    3. Θ ( n 2 log n )
    4. the master theorem cannot be used
    5. Θ ( n 4 )
    6. Θ ( n 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 2 ) + n 2 ?
    1. Θ ( n 3 2 )
    2. Θ ( n 2 log n )
    3. the master theorem cannot be used
    4. Θ ( n 2 )
    5. Θ ( n 3 log n )
    6. Θ ( n 3 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 4 T ( n 2 ) + n 2 ?
    1. the master theorem cannot be used
    2. Θ ( n 2 )
    3. Θ ( n 2 log n )
    4. Θ ( n 4 )
    5. Θ ( n 3 log n )
    6. Θ ( n 3 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = T ( n 2 ) + 2 n ?
    1. Θ ( 2 n )
    2. Θ ( 2 n log n )
    3. the master theorem cannot be used
    4. Θ ( 2 n log n )
    5. Θ ( n 2 )
    6. Θ ( n 2 log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 n T ( n 2 ) + n n ?
    1. Θ ( n n )
    2. Θ ( 2 n log n )
    3. Θ ( ( n n log n )
    4. Θ ( n n log n )
    5. Θ ( 2 n )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = T ( n - 1 ) + 1?
    1. Θ ( n )
    2. Θ ( n log n )
    3. Θ ( log n log n )
    4. the master theorem cannot be used
    5. Θ ( log n )
    6. Θ ( 1 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 T ( n - 2 ) + n?
    1. Θ ( 1 )
    2. Θ ( n log n )
    3. Θ ( log n )
    4. the master theorem cannot be used
    5. Θ ( n )
    6. Θ ( ( log n ) 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 16 T ( n 4 ) + n?
    1. Θ ( log n )
    2. Θ ( n )
    3. Θ ( n 2 )
    4. Θ ( n 2 log n )
    5. Θ ( n log n )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 T ( n 2 ) + n log n?
    1. Θ ( n log n )
    2. Θ ( log n )
    3. Θ ( n 2 )
    4. Θ ( n )
    5. Θ ( n 2 log n )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 2 ) + n log n?
    1. Θ ( n log 3 ( 2 ) )
    2. Θ ( n log n )
    3. Θ ( n 3 2 )
    4. the master theorem cannot be used
    5. Θ ( n log 3 2 ( n ) )
    6. Θ ( n log 2 ( 3 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 T ( n 2 ) + n log n ?
    1. Θ ( n log n )
    2. the master theorem cannot be used
    3. Θ ( n 2 log n )
    4. Θ ( log n )
    5. Θ ( n )
    6. Θ ( n 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 T ( n 4 ) + n 0.51 ?
    1. Θ ( n )
    2. Θ ( log n )
    3. Θ ( n log n )
    4. Θ ( n )
    5. Θ ( n 0.51 )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 1 2 T ( n 2 ) + 1?
    1. Θ ( n )
    2. Θ ( n log 2 1 2 )
    3. Θ ( log 2 1 2 )
    4. the master theorem cannot be used
    5. Θ ( log n )
    6. Θ ( n 1 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 16 T ( n 4 ) + n !?
    1. the master theorem cannot be used
    2. Θ ( n 2 n ! )
    3. Θ ( n ! )
    4. Θ ( n 2 )
    5. Θ ( ( n 2 ) ! )
    6. Θ ( n ! log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 2 T ( n 2 ) + log n?
    1. Θ ( log n )
    2. Θ ( n log n )
    3. the master theorem cannot be used
    4. Θ ( n log n )
    5. Θ ( n log ( 2 ) )
    6. Θ ( n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 2 ) + n?
    1. Θ ( n )
    2. Θ ( n log 3 ( 2 ) )
    3. Θ ( n log n )
    4. Θ ( n log 3 2 n )
    5. the master theorem cannot be used
    6. Θ ( n log 2 ( 3 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 3 ) + n ?
    1. Θ ( log n )
    2. Θ ( n log n )
    3. the master theorem cannot be used
    4. Θ ( n log n )
    5. Θ ( n log n )
    6. Θ ( n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 4 T ( n 2 ) + n?
    1. Θ ( n log n )
    2. the master theorem cannot be used
    3. Θ ( n 2 )
    4. Θ ( log n )
    5. Θ ( n 2 log n )
    6. Θ ( n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 4 ) + n log n?
    1. Θ ( n log 4 ( 3 ) )
    2. Θ ( n log 3 ( 4 ) )
    3. Θ ( n )
    4. Θ ( n log n )
    5. Θ ( log n )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 3 T ( n 3 ) + n 2 ?
    1. Θ ( n )
    2. Θ ( log n )
    3. Θ ( n 2 log n )
    4. the master theorem cannot be used
    5. Θ ( n log n )
    6. Θ ( n 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 6 T ( n 3 ) + n 2 log n?
    1. Θ ( n 2 log n )
    2. Θ ( n log 3 ( 6 ) log n )
    3. the master theorem cannot be used
    4. Θ ( n log 3 ( 6 ) )
    5. Θ ( n log 6 ( 3 ) log n )
    6. Θ ( n log 6 ( 3 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 4 T ( n 2 ) + n log n ?
    1. Θ ( n 2 log n )
    2. Θ ( log n )
    3. Θ ( n log n )
    4. Θ ( n 2 log n )
    5. Θ ( n 2 )
    6. the master theorem cannot be used
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 64 T ( n 8 ) - n log n ?
    1. Θ ( log n )
    2. Θ ( n )
    3. Θ ( n 2 )
    4. Θ ( n log n )
    5. the master theorem cannot be used
    6. Θ ( n 2 log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 7 T ( n 7 ) + n 2 ?
    1. Θ ( n log 7 ( 7 ) )
    2. the master theorem cannot be used
    3. Θ ( n 2 )
    4. Θ ( n log n )
    5. Θ ( n log 7 ( 7 ) )
    6. Θ ( n 2 log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 7 T ( n 2 ) + n 2 ?
    1. Θ ( n log 7 ( 2 ) )
    2. Θ ( n 2 )
    3. Θ ( n 2 + log 2 ( 7 ) )
    4. the master theorem cannot be used
    5. Θ ( n 2 + log 7 ( 2 ) )
    6. Θ ( n log 2 ( 7 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 7 T ( n 3 ) + n 2 ?
    1. Θ ( n 2 + log 7 ( 3 ) )
    2. Θ ( n log 7 ( 3 ) )
    3. the master theorem cannot be used
    4. Θ ( n log 3 ( 7 ) )
    5. Θ ( n 2 + log 3 ( 7 ) )
    6. Θ ( n 2 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 4 T ( n 2 ) + log n?
    1. Θ ( n log n )
    2. Θ ( n 2 log n )
    3. Θ ( n 2 )
    4. the master theorem cannot be used
    5. Θ ( log n )
    6. Θ ( n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 2 ) + log n?
    1. Θ ( n log 2 ( 5 ) log n )
    2. the master theorem cannot be used
    3. Θ ( n log 2 ( 5 ) )
    4. Θ ( n log 5 ( 2 ) log n )
    5. Θ ( log n )
    6. Θ ( n log 5 ( 2 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 2 ) + n?
    1. Θ ( n log 5 ( 2 ) )
    2. Θ ( n log 2 ( 5 ) )
    3. Θ ( n log n )
    4. Θ ( n log 2 ( 5 ) log n )
    5. the master theorem cannot be used
    6. Θ ( n log 5 ( 2 ) log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 5 3 ) + n 3 ?
    1. Θ ( n log 5 5 3 )
    2. Θ ( n log 5 5 3 × log n )
    3. the master theorem cannot be used
    4. Θ ( n log 5 3 ( 5 ) )
    5. Θ ( n 3 log n )
    6. Θ ( n log 5 3 ( 5 ) × log n )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 5 3 ) + n 3 log n ?
    1. Θ ( n 3 log n )
    2. Θ ( n log 5 3 ( 5 ) )
    3. the master theorem cannot be used
    4. Θ ( n log 5 5 3 × log n )
    5. Θ ( n log 5 3 ( 5 ) × log n )
    6. Θ ( n log 5 5 3 )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 5 ) + n 2 log n?
    1. Θ ( n log 5 5 × log n )
    2. the master theorem cannot be used
    3. Θ ( n log 5 5 )
    4. Θ ( n log 5 ( 5 ) × log n )
    5. Θ ( n 2 log n )
    6. Θ ( n log 5 ( 5 ) )
  1. Using the master recurrence theorem, what is the solution of T ( n ) = 5 T ( n 5 ) + n log n?
    1. Θ ( n 2 + log 5 5 )
    2. Θ ( n 2 + log 5 ( 5 ) )
    3. Θ ( n log 5 ( 5 ) × log n )
    4. Θ ( n log n )
    5. the master theorem cannot be used
    6. Θ ( n 2 )
    7. Θ ( n log 5 5 × log n )

Determining ε in the M.R.T.

  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 4 T ( n 4 ) + log n. What is the largest listed value of ε that can be used in the solution?
    1. 0.1
    2. ε is not used in the solution
    3. 0.5
    4. no legal value is listed
    5. 0.25
    6. the master theorem cannot be used
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 2 ) + n 2 ? What is the largest listed value of ε 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.1
    2. the master theorem cannot be used
    3. 0.25
    4. no legal value is listed
    5. 0.5
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 4 T ( n 2 ) + n 2 ? What is the largest listed value of ε 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.
    1. ε is not used in the solution
    2. no legal value is listed
    3. 1.0
    4. the master theorem cannot be used
    5. 0.5
    6. 0.25
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = T ( n 2 ) + 2 n ? What is the largest listed value of ε that can be used in the solution?
    1. 0.5
    2. ε is not used in the solution
    3. no legal value is listed
    4. 1.0
    5. 0.1
    6. the master theorem cannot be used
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 2 n T ( n 2 ) + n n ? What is the largest listed value of ε that can be used in the solution?
    1. the master theorem cannot be used
    2. 0.1
    3. 0.5
    4. ε is not used in the solution
    5. 1.0
    6. no legal value is listed
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 16 T ( n 4 ) + n? What is the largest listed value of ε that can be used in the solution? The log (base 16) of 4 is 0.5 and log (base 4) of 16 is 2.
    1. ε is not used in the solution
    2. 0.5
    3. the master theorem cannot be used
    4. 0.25
    5. no legal value is listed
    6. 0.75
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 2 T ( n 2 ) + n log n? What is the largest listed value of ε that can be used in the solution?
    1. ε is not used in the solution
    2. no legal value is listed
    3. 0.5
    4. the master theorem cannot be used
    5. 1.0
    6. 0.75
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 2 ) + n log n? What is the largest listed value of ε 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. 1.0
    2. no legal value is listed
    3. 0.25
    4. the master theorem cannot be used
    5. ε is not used in the solution
    6. 0.5
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 8 T ( n 2 ) + n? What is the largest listed value of ε 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.
    1. no legal value is listed
    2. 0.100
    3. the master theorem cannot be used
    4. 0.05
    5. ε is not used in the solution
    6. 0.025
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 2 T ( n 4 ) + n 0.51 ? What is the largest listed value of ε that can be used in the solution? The log (base 4) of 2 is 0.5 and log (base 2) of 4 is 2.
    1. the master theorem cannot be used
    2. 0.050
    3. 0.100
    4. no legal value is listed
    5. 0.075
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 1 2 T ( n 2 ) + 1? What is the largest listed value of ε that can be used in the solution?
    1. no legal value is listed
    2. 0.05
    3. ε is not used in the solution
    4. 0.01
    5. the master theorem cannot be used
    6. 0.10
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 16 T ( n 4 ) + n !? What is the largest listed value of ε 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.
    1. no legal value is listed
    2. 100
    3. the master theorem cannot be used
    4. ε is not used in the solution
    5. 10
    6. 1
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 2 T ( n 2 ) + log n? What is the largest listed value of ε that can be used in the solution? The log (base 2) of 2 is 0.5 and the log (base 2 ) of 2 is 2.
    1. no legal value is listed
    2. 0.50
    3. 0.25
    4. the master theorem cannot be used
    5. 1.0
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 2 ) + n? What is the largest listed value of ε 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.
    1. 0.25
    2. 0.10
    3. 1.0
    4. no legal value is listed
    5. the master theorem cannot be used
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 3 ) + n ? What is the largest listed value of ε that can be used in the solution?
    1. no legal value is listed
    2. 0.3
    3. 0.9
    4. the master theorem cannot be used
    5. 0.6
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 4 T ( n 2 ) + n? What is the largest listed value of ε 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.
    1. 0.9
    2. 0.3
    3. the master theorem cannot be used
    4. ε is not used in the solution
    5. no legal value is listed
    6. 0.6
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 4 ) + n log n? What is the largest listed value of ε 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.
    1. 0.6
    2. no legal value is listed
    3. ε is not used in the solution
    4. 0.9
    5. the master theorem cannot be used
    6. 0.3
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 3 T ( n 3 ) + n 2 ? What is the largest listed value of ε that can be used in the solution?
    1. no legal value is listed
    2. 0.9
    3. ε is not used in the solution
    4. the master theorem cannot be used
    5. 0.6
    6. 0.3
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 6 T ( n 3 ) + n 2 log n? What is the largest listed value of ε 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.
    1. no legal value is listed
    2. the master theorem cannot be used
    3. ε is not used in the solution
    4. 0.5
    5. 0.4
    6. 0.3
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 4 T ( n 2 ) + n log n ? What is the largest listed value of ε 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.
    1. 0.5
    2. ε is not used in the solution
    3. the master theorem cannot be used
    4. 1.0
    5. no legal value is listed
    6. 0.25
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 64 T ( n 8 ) - n log n ? What is the largest listed value of ε 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.
    1. no legal value is listed
    2. 0.25
    3. 0.5
    4. the master theorem cannot be used
    5. 1.0
    6. ε is not used in the solution
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 7 T ( n 7 ) + n 2 ? What is the largest listed value of ε that can be used in the solution? The log (base 7) of 7 is 0.5 and the log (base 7 ) of 7 is 2.
    1. no legal value is listed
    2. ε is not used in the solution
    3. 1.0
    4. 0.5
    5. 0.25
    6. the master theorem cannot be used
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 7 T ( n 2 ) + n 2 ? What is the largest listed value of ε 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.
    1. 0.8
    2. ε is not used in the solution
    3. the master theorem cannot be used
    4. 1.0
    5. 0.6
    6. no legal value is listed
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 7 T ( n 3 ) + n 2 ? What is the largest listed value of ε 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.
    1. no legal value is listed
    2. 0.8
    3. the master theorem cannot be used
    4. ε is not used in the solution
    5. 1.0
    6. 0.6
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 4 T ( n 2 ) + log n? What is the largest listed value of ε 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.
    1. 2.0
    2. ε is not used in the solution
    3. the master theorem cannot be used
    4. 0.5
    5. 1.0
    6. no legal value is listed
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 2 ) + log n? What is the largest listed value of ε 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. 1.0
    2. ε is not used in the solution
    3. no legal value is listed
    4. the master theorem cannot be used
    5. 0.5
    6. 2.0
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 2 ) + n? What is the largest listed value of ε 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.
    1. 0.5
    2. 1.0
    3. no legal value is listed
    4. ε is not used in the solution
    5. the master theorem cannot be used
    6. 2.0
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 5 3 ) + n 3 ? What is the largest listed value of ε that can be used in the solution? The log (base 5) of 5 3 is ~0.333 and the log (base 5 3 ) of 5 is 3.
    1. no legal value is listed
    2. 1.0
    3. 0.5
    4. 2.0
    5. ε is not used in the solution
    6. the master theorem cannot be used
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 5 3 ) + n 3 log n ? What is the largest listed value of ε that can be used in the solution? The log (base 5 3 ) of 5 is 3 and the log (base 5) of 5 3 is ~0.333.
    1. 0.5
    2. ε is not used in the solution
    3. 2.0
    4. the master theorem cannot be used
    5. 1.0
    6. no legal value is listed
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 5 ) + n 2 log n? What is the largest listed value of ε that can be used in the solution? The log (base 5) of 5 is 0.5 and the log (base 5 ) of 5 is 2.
    1. 2.0
    2. 0.5
    3. no legal value is listed
    4. ε is not used in the solution
    5. the master theorem cannot be used
    6. 1.0
  1. Consider using the master recurrence theorem to solve the equation T ( n ) = 5 T ( n 5 ) + n log n? What is the largest listed value of ε that can be used in the solution? The log (base 5 ) of 5 is 2 and the log (base 5) of 5 is 0.5.
    1. the master theorem cannot be used
    2. 1.0
    3. no legal value is listed
    4. 0.5
    5. ε is not used in the solution
    6. 2.0

Determining c for M.R.T., case 3

  1. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T ( n ) = 8 T ( n 8 ) + n 2 . What is the smallest legal value of the constant c listed for the solution?
    1. no legal value is listed
    2. case 3 does not apply
    3. 1 9
    4. 1 7
    5. 1 5
  1. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T ( n ) = 7 T ( n 8 ) + n 2 . What is the smallest legal value of the constant c listed for the solution?
    1. no legal value is listed
    2. case 3 does not apply
    3. 9 64
    4. 11 64
    5. 7 64
  1. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T ( n ) = 6 T ( n 8 ) + n 2 . What is the smallest legal value of the constant c listed for the solution?
    1. no legal value is listed
    2. 1 64
    3. 5 64
    4. case 3 does not apply
    5. 3 64
  1. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T ( n ) = 64 ( n 8 ) + n 2 . What is the smallest legal value of the constant c listed for the solution?
    1. no legal value is listed
    2. 65 64
    3. case 3 does not apply
    4. 61 64
    5. 63 64
  1. Consider using the master recurrence theorem and the regularity condition for case 3 to solve the equation T ( n ) = 32 ( n 8 ) + n 2 . What is the smallest legal value of the constant c listed for the solution?
    1. 16 64
    2. 63 64
    3. case 3 does not apply
    4. 8 64
    5. 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 (end-start < 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 ( 2 0 ) = 1
T ( 2 n ) = 2 T ( 2 n - 1 ) + 2 n

Consider a proof, by induction, that T ( 2 n ) = ( n + 1 ) 2 n where 2 n is the size of the array and b is the base case value of n.
  1. To completely prove the base case value b, you would need to show:
    1. 2 T ( 2 b - 1 ) + 2 b = ( b + 1 ) 2 b
    2. T ( 2 b ) = 4
    3. 2 T ( 2 b - 1 ) = 2
    4. b 2 b = 2 b + 1
    5. 2 T ( 2 b - 1 ) = 2 b
    6. b 2 b = 2
  1. 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:
    1. Assume true for i n.
    2. Assume true for n.
    3. Assume true for i < n.
    4. Assume true for n + 1.
    5. Assume true for b < i n.
    6. Assume true for b < i < n.
  1. 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:
    1. Assume true for n + 2.
    2. Assume true for n + 1.
    3. Assume true for n.
    4. Assume true for n - 1.
  1. Assuming you wish to prove the inductive case n, the first line of the inductive case for a strong inductive proof would be:
    1. T ( 2 n ) = ( n + 1 ) 2 n
    2. T ( 2 n ) = 2 T ( 2 n - 1 ) + 2 n
    3. T ( 2 n - 1 ) = ( ( n - 1 ) + 1 ) 2 n - 1
    4. T ( 2 n - 1 ) = 2 T ( 2 ( n - 1 ) - 1 ) + 2 n - 1
    5. T ( 2 n + 1 ) = 2 T ( 2 ( n + 1 ) - 1 ) + 2 n + 1
    6. T ( 2 n + 1 ) = ( ( n + 1 ) + 1 ) 2 n + 1
  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:
    1. T ( 2 n - 1 ) = ( ( n - 1 ) + 1 ) 2 n - 1
    2. T ( 2 n + 1 ) = 2 T ( 2 ( n + 1 ) - 1 ) + 2 n + 1
    3. T ( 2 n - 1 ) = 2 T ( 2 ( n - 1 ) - 1 ) + 2 n - 1
    4. T ( 2 n ) = 2 T ( 2 n - 1 ) + 2 n
    5. T ( 2 n + 1 ) = ( ( n + 1 ) + 1 ) 2 n + 1
    6. T ( 2 n ) = ( n + 1 ) 2 n
  1. Assuming you wish to prove the inductive case n, the inductive step for a strong inductive proof would be:
    1. substitute T ( 2 n - 1 ) for n 2 n - 1
    2. substitute ( n - 1 ) 2 n - 2 for T ( 2 ( n - 1 ) - 1 )
    3. substitute T ( 2 ( n - 1 ) - 1 ) for ( n - 1 ) 2 n - 2
    4. substitute ( n + 1 ) 2 n for T ( 2 ( n + 1 ) - 1 )
    5. substitute n 2 n - 1 for T ( 2 n - 1 )
    6. substitute T ( 2 ( n + 1 ) - 1 ) for ( n + 1 ) 2 n
  1. Assuming you wish to prove the inductive case n+1, the inductive step for a weak inductive proof would be:
    1. substitute n 2 n - 1 for T ( 2 n - 1 )
    2. substitute ( n + 1 ) 2 n for T ( 2 ( n + 1 ) - 1 )
    3. substitute T ( 2 ( n + 1 ) - 1 ) for ( n + 1 ) 2 n
    4. substitute ( n - 1 ) 2 n - 2 for T ( 2 ( n - 1 ) - 1 )
    5. substitute T ( 2 ( n - 1 ) - 1 ) for ( n - 1 ) 2 n - 2
    6. substitute T ( 2 n - 1 ) for n 2 n - 1
  1. T or F: For strong inductive proofs, proving the inductive case makes use of the previously proved base cases.
  1. T or F: Weak inductive proofs are more closely related to recursive functions than strong inductive proofs.
  1. The more formal names for weak and strong inductive proofs are:
    1. complete and mathematical
    2. simple and complex
    3. mathematical and complete
    4. complex and simple
    5. simple and mathematical
    6. mathematical and simple

Concept: inductive proofs

  1. (6 pts) Prove by strong induction, with n as the inductive case, that k = 1 n k = n ( n + 1 ) 2 .

    Base case:



    Inductive Hypothesis:


    Inductive Case:












  1. (6 pts) Prove by strong induction, with n as the inductive case, that T ( n ) = n ( n + 1 ) 2 , where:
    T ( 0 ) = 0
    T ( n ) = T ( n - 1 ) + n


    Base case:



    Inductive Hypothesis:


    Inductive Case:











  1. (6 pts) Prove by strong induction, with n as the inductive case, that k = 0 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 .

    Base case:



    Inductive Hypothesis:


    Inductive Case:












  1. (6 pts) Prove by strong induction, with n as the inductive case, that T ( n ) = n ( n + 1 ) ( 2 n + 1 ) 6 , where:
    T ( 0 ) = 0
    T ( n ) = T ( n - 1 ) + n 2


    Base case:



    Inductive Hypothesis:


    Inductive Case:











  1. (6 pts) Prove by strong induction that k = 0 n k 3 = n 2 ( n + 1 ) 2 4 .

    Base case:



    Inductive Hypothesis:


    Inductive Case:













  1. (6 pts) Prove by strong induction that T ( n ) = n 2 ( n + 1 ) 2 4 , where:
    T ( 0 ) = 0
    T ( n ) = T ( n - 1 ) + n 3


    Base case:



    Inductive Hypothesis:


    Inductive Case:











  1. (6 pts) Prove by strong induction that k = 0 n x k = x n + 1 - 1 x - 1 .

    Base case:



    Inductive Hypothesis:


    Inductive Case:













  1. (6 pts) Prove by strong induction that T ( x , n ) = x n + 1 - 1 x - 1 , where:
    T ( x ,0 ) = 1
    T ( x , n ) = T ( x , n - 1 ) + x n


    Base case:



    Inductive Hypothesis:


    Inductive Case:












  1. (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:













  1. (6 pts) Prove by strong induction that the number of nodes in a perfect quaternary tree with n levels is 4 n - 1 3 .

    Base case:



    Inductive Hypothesis:


    Inductive Case:













  1. (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:













  1. (6 pts) Prove by strong induction that the number of interior nodes in a perfect binary tree with n levels is 2 n - 1 - 1.

    Base case:



    Inductive Hypothesis:


    Inductive Case:













  1. (6 pts) Prove by strong induction that the number of child pointers in an arbitrary binary tree with n nodes is n - 1.

    Base case:



    Inductive Hypothesis:


    Inductive Case:












Concept: rotations in a BST

  1. Which of the following is true for rotations in a BST:
    1. the number of leaf nodes always increases
    2. the number of leaf nodes always decreases
    3. BST-ordering is always preserved
    4. the tree always becomes more balanced
  1. Consider a right-rotation of a node n upwards in a BST. The former right child of n, if it exists:
    1. becomes the sibling of n
    2. becomes the left child of n
    3. becomes the niece or nephew of n
    4. becomes the right child of the former parent of n
    5. remains the right child of n
    6. becomes the left child of the former parent of n
  1. Consider a right-rotation of a node n upwards in a BST. The former left child of n, if it exists:
    1. remains the left child of n
    2. becomes the niece or nephew of n
    3. becomes the left child of the former parent of n
    4. becomes the right child of the former parent of n
    5. becomes the sibling of n
    6. becomes the right child of n
  1. Consider a right-rotation of a node n upwards in a BST. The former parent of n, assuming it exists:
    1. becomes the sibling of n
    2. becomes the right child of n
    3. becomes the niece or nephew of n
    4. remains the parent of n
    5. becomes the left child of n
  1. Consider a right-rotation of a node n upwards in a BST. The former sibling of n, assuming it exists:
    1. becomes the left child of n
    2. becomes the right child of n
    3. becomes a grandchild of n
    4. remains the sibling of n
    5. becomes the niece or nephew of n

Concept: red-black trees

  1. The number of rotations that occur after an insertion into a red-black tree is:
    1. Θ ( log n )
    2. Θ ( n log n )
    3. Θ ( 1 )
    4. Θ ( n )
  1. The maximum number of rotations that occur after an insertion into a red-black tree is:
    1. log n
    2. 1
    3. 3
    4. 2
  1. The maximum number of rotations that occur after a deletion from a red-black tree is:
    1. Θ ( n log n )
    2. Θ ( n )
    3. Θ ( 1 )
    4. Θ ( log n )
  1. The maximum number of rotations that occur after a deletion from a red-black tree is:
    1. 3
    2. 1
    3. 2
    4. log n
  1. Consider a node n in a red-black tree and all paths from n to a leaf. Which of the following is a constraint on these trees?
    1. the number of nodes (red or black) on each path is the same
    2. each path must start with a black node
    3. the number of black nodes on each path is the same
    4. the number of red nodes on each path is the same
  1. Consider a node n in a red-black tree and all paths from n to a leaf. Which of the following is a constraint on these trees?
    1. no black node can have a black parent
    2. no black node can have a red parent
    3. no red node can have a black parent
    4. no red node can have a red parent
  1. Consider a black interior node n in a red-black 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?
    1. R B
    2. B < R
    3. R B + 1
    4. B R
    5. R = B
    6. B R + 1
  1. Consider a red node n in a red-black 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?
    1. L = 2 S
    2. L = 2 S + 1
    3. L = 2 S - 1
    4. L = 2 S - 2
    5. L = 2 S + 2
  1. Inserting a value in a red-black tree and a regular BST, respectively, takes time:
    1. Θ ( log n ) and Θ ( log n )
    2. Θ ( n ) and Θ ( n )
    3. Θ ( log n ) and Θ ( n )
    4. Θ ( 1 ) and Θ ( log n )
  1. Suppose one wished to allow more red nodes in a red-black 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:
    1. the number of black nodes between any two red nodes is bounded by a constant.
    2. the number of red nodes between any two black nodes is bounded by a constant.
    3. no red node could have a red sibling.
    4. no black node could have a red parent.
  1. T or F: A black node in a red-black tree can have one child.
  1. T or F: A red node in a red-black tree can have one child.
  1. T or F: A red node in a red-black tree can have a red parent.
  1. T or F: A black node in a red-black tree can have a black parent.
  1. Choose an order of insertion for seven consecutive integers such that a red-black tree performs no rotations for any of the insertions.
    1. 3 2 6 1 0 5 4
    2. 3 2 5 0 1 4 6
    3. 3 2 6 0 1 4 5
    4. 3 1 5 2 0 4 6
    5. 3 2 5 1 0 4 6
  1. Choose an order of insertion for seven consecutive integers such that a red-black tree performs one rotation for one of the insertions and no rotations for the other insertions.
    1. 3 2 6 1 0 5 4
    2. 3 1 5 2 0 4 6
    3. 3 2 5 0 1 4 6
    4. 3 2 6 0 1 4 5
    5. 3 2 5 1 0 4 6
  1. Choose an order of insertion for seven consecutive integers such that a red-black tree performs two rotations for one of the insertions and no rotations for the other insertions.
    1. 3 2 6 0 1 4 5
    2. 3 1 5 2 0 4 6
    3. 3 2 5 0 1 4 6
    4. 3 2 5 1 0 4 6
    5. 3 2 6 1 0 5 4
  1. Choose an order of insertion for seven consecutive integers such that a red-black tree performs one rotation for two of the insertions and no rotations for the other insertions.
    1. 3 2 6 0 1 4 5
    2. 3 2 5 1 0 4 6
    3. 3 2 5 0 1 4 6
    4. 3 1 5 2 0 4 6
    5. 3 2 6 1 0 5 4
  1. Choose an order of insertion for seven consecutive integers such that a red-black tree performs no rotations for any of the insertions and yields the most unbalanced tree.
  1. 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 red-black tree.
  1. 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?
    1. 3 / 4
    2. 3 / 5
    3. 0 / 4
    4. 0 / 5
    5. the correct answer is not listed
    6. 0 / 6
    7. 0 / 3
    8. 3 / 3
  1. Consider an node with a single child in a red-black 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.
    1. either black or red / 4
    2. red / 2
    3. black / 2
    4. either black or red / 2
    5. red / 6
    6. black / 6
    7. either black or red / 5
    8. the correct answer is not listed
  1. Consider inserting the following numbers, in the order given, into an empty red-black 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.
    1. 0 / 5
    2. the correct answer is not listed
    3. 0 / 6
    4. 1 / 6
    5. 1 / 5
    6. 0 / 7
    7. 1 / 7
  1. 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 red-black tree?
    1. 1
    2. 4
    3. 2
    4. 3
    5. 0
    6. the correct answer is not listed
    7. 5
  1. Consider inserting the following numbers, in the order given, into an empty red-black tree:
        0 4 3 8 1 2 6 5 9 7
    
    After which insertion value does the red-black tree make its first rotation?
    1. 8
    2. 1
    3. 4
    4. 0
    5. 2
    6. 6
    7. 3
    8. the correct answer is not listed
  1. Consider inserting the following numbers, in the order given, into an empty red-black tree:
        0 4 3 8 1 2 6 5 9 7
    
    Which values, when inserted, cause a rotation?
    1. 3 2 6
    2. 3 2 7
    3. the correct answer is not listed
    4. 6 7
    5. 2 6 7
    6. none
  1. Consider inserting the following numbers, in the order given, into an empty red-black tree:
        0 4 3 8 1 2 6 5 9 7
    
    Which values, when inserted, cause a double rotaion?
    1. 2 7
    2. 3 7
    3. 7
    4. the correct answer is not listed
    5. 6
    6. 3 6
    7. 2 6

Concept: AVL trees

  1. 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 L H > R H, which of the following is a constraint on these trees?
    1. L H - R H < 2
    2. L H - R H < 3
    3. L H - R H = 2
    4. L H - R H = 1
    5. L H - R H = 0
  1. The number of rotations that occur after an insertion into an AVL tree is, in the worst case:
    1. Θ ( n )
    2. Θ ( n log n )
    3. Θ ( log log n )
    4. Θ ( 1 )
    5. Θ ( log n )
  1. The number of rotations that occur after an insertion into an AVL tree is, in the worst case:
    1. Θ ( log n )
    2. 1
    3. Θ ( n )
    4. 2
  1. The number of rotations that occur after an deletion in an AVL tree is, in the worst case:
    1. Θ ( n )
    2. Θ ( n log n )
    3. Θ ( 1 )
    4. Θ ( log n )
    5. Θ ( log log n )
  1. The number of rotations that occur after an deletion into an AVL tree is, in the worst case:
    1. Θ ( n )
    2. Θ ( log n )
    3. 2
    4. 1
  1. The minimum number of rotations that occur after an deletion into an AVL tree is:
    1. Θ ( log n )
    2. 1
    3. 2
    4. Θ ( n )
    5. 0
  1. 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.
  1. 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?
    1. 0 3 8
    2. 2 5 6 7 9
    3. 0 3
    4. 0 1 2 3
    5. 0 4 3
    6. the correct answer is not listed
    7. 0 1 3 8
  1. 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. 1 / 7
    2. 0 / 6
    3. 0 / 4
    4. the correct answer is not listed
    5. 0 / 7
    6. 1 / 4
    7. 1 / 5
    8. 1 / 6
    9. 0 / 5
  1. 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.
    1. the correct answer is not listed
    2. -1 0 1 1 -1 0 0 0 0 0
    3. 1 0 1 1 1 0 0 0 0 0
    4. -4 0 2 1 -1 0 0 0 0 0
    5. -9 -2 2 2 -1 0 0 0 0 0
  1. 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.
    1. 5 4 3 3 2 2 2 1 1 1
    2. 4 4 3 3 2 2 1 1 0 0
    3. 4 3 2 2 1 1 1 0 0 0
    4. 5 5 4 4 3 3 2 2 1 1
    5. the correct answer is not listed
  1. 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?
    1. the correct answer is not listed
    2. 2
    3. 4
    4. 0
    5. 1
    6. 3
    7. 5
  1. 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?
    1. 2
    2. the correct answer is not listed
    3. 8
    4. 9
    5. 7
    6. 1
    7. 3
    8. 6
    9. 5
  1. 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?
    1. 3 7 2 6
    2. 7 2 6
    3. the correct answer is not listed
    4. 7 6
    5. 3 7 2
  1. 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?
    1. 7
    2. 2 6
    3. 2
    4. 3 7
    5. 6
    6. 3
    7. the correct answer is not listed
  1. Choose an order of insertion for seven consecutive integers such that an AVL tree performs no rotations for any of the insertions.
  1. 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.
  1. 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.
  1. 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.
  1. 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

  1. Suppose a dynamic array was implemented so that growing the array increased the capacity by 1000 elements. What is the worst-case cost of the append operation?
    1. constant
    2. quadratic
    3. log linear
    4. linear
  1. Suppose a dynamic array was implemented so that growing the array increased the capacity by 2%. What is the amortized and worst-case costs of the append operation?
    1. log and linear
    2. constant and linear
    3. quadratic and quadratic
    4. linear and linear
  1. Suppose a dynamic array was implemented so that growing the array increased the capacity by 100 elements. What is the amortized and worst-case costs of the append operation?
    1. log and linear
    2. quadratic and quadratic
    3. constant and linear
    4. linear and linear
  1. 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.
    1. 3 n - 2
    2. 3 n - 1
    3. 2 n - 2
    4. 2 n - 1
    5. 2 n - 3
    6. 3 n - 3
  1. Consider a dynamic fillable array which grows from size n to size 2 n + 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 .
    1. 3 n - 3
    2. 3 n - 6
    3. 3 n - log n - 2
    4. 2 n
    5. 3 n - 1
    6. 2 n - 1
  1. 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?
    1. E + 2 C
    2. 2 S - C
    3. S - E
    4. S + 2 E
    5. 2 S - E
    6. S + E
  1. 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 worst-case times for enqueue and dequeue are:
    1. Θ ( 1 ) and Θ ( n )
    2. Θ ( n ) and Θ ( 1 )
    3. Θ ( n ) and Θ ( n )
    4. Θ ( 1 ) and Θ ( 1 )
  1. 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 Θ ( 1 ) for operations on this kind of queue?
    1. Φ = V s
    2. Φ = 2 V s
    3. Φ = V s + W s
    4. Φ = V s + 2 W s
  1. Suppose a data structure has operation A with a real cost of 1 and operation B with a real cost of 2 n + 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 Θ(1) for operations A and B on this data structure?
    1. P h i = n .
    2. Φ = 3 n
    3. P h i = 2 n .
  1. Suppose a data structure has operation A with a real cost of 3 n + 1 and operation B with a real cost of 3 2 n + 1. After an A operation, n decreases to 1 4 n while after a B operation, n decreases to 5 8 n.

    Which of the following potential functions can be used to show an amortized bound of Θ(1) for operations A and B on this data structure?
    1. Φ = 3 2 n
    2. Φ = 4 n
    3. Φ = 3 n
  1. 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 Θ(1) for A operations and Θ ( k ) for B operations?
    1. Φ = n
    2. Φ = 3 n
    3. Φ = 2 n

Concept: Graphs

  1. What is the primary characteristic of a directed graph?
    1. the vertices are all reachable
    2. at least one vertex is unreachable
    3. the edges are bi-directional
    4. the edges are uni-directional
  1. What is the primary characteristic of a weighted graph?
    1. the edge count exceeds vertex count
    2. the vertex count exceeds some threshold
    3. each vertex has an associated weight
    4. each edge has an associated weight
  1. What is the primary characteristic of an undirected, simple graph?
    1. there is at most one edge between any two vertices
    2. the edge count exceeds or equals the vertex count
    3. the edge count is less than the vertex count
    4. the termini of an edge may be the same vertex
  1. What is the degree of a vertex in an undirected, simple graph?
    1. the total number of paths emanating from the vertex
    2. the total number of edges emanating from the vertex
    3. the count of vertices reachable from that vertex
    4. the count of vertices not reachable from that vertex
  1. What is the primary characteristic of a undirected, simple, connected graph?
    1. each vertex has a edge that connects to itself
    2. a path exists between every pair of vertices
    3. there is at least one edge
    4. an edge exists between every pair of vertices
  1. What is the primary characteristic of an undirected, simple, regular graph?
    1. all vertices have the same weight
    2. all edges have the same weight
    3. all edges terminate at the same vertex
    4. all vertices have the same degree
  1. What is the primary characteristic of an undirected, simple, complete graph? Choose the most general answer.
    1. all vertices have a degree greater than some threshold
    2. there exists an edge between every pair of vertices
    3. each vertex has two edges or no edges
    4. there exists a path between every pair of vertices
  1. What is the primary characteristic of an undirected, simple, connected, acyclic graph? Choose the most general answer.
    1. the vertex count is one greater than the edge count
    2. no edge has a single vertex as its termini
    3. there are at least two unique paths between any two vertices
    4. the vertex count is equal to the edge count
  1. What is the primary characteristic of a planar graph?
    1. the maximum degree of a vertex is 4
    2. it can be drawn in a plane with no crossed edges
    3. when drawn in a plane, it must have crossed edges
    4. the maximum degree of a vertex is 3

Graph traversals

  1. What is a walk? Choose the most general answer.
    1. a sequence of edges such that e i and e i + 1 have no common vertex
    2. a sequence of vertices with an edge between v i and v i + 1
    3. a set of edges that have one vertex in common
    4. a sequence of vertices with no edge between v i and v i + 1
  1. What is a trail? Choose the most general answer.
    1. a walk with no edge appearing more than once
    2. a walk with at least one edge appearing twice (or more)
    3. a walk with at least one vertex appearing twice (or more)
    4. a walk with no vertex appearing more than once
  1. What is the primary characteristic of a path?
    1. a trail with all edges appearing at least once
    2. a trail with no vertex appearing more than twice
    3. a trail with all vertices appearing at least once
    4. a trail with no vertex appearing more than once
  1. What is an Euler trail? Choose the most general answer.
    1. the longest trail in a graph
    2. a trail which invovles every vertex, except one, exactly once
    3. a trail which invovles every vertex exactly once
    4. a trail which invovles every edge exactly once
  1. What is a Hamiltonian path? Choose the most general answer.
    1. the longest path in a graph
    2. the shortest path in a graph
    3. a path which involves every edge
    4. a path which involves every vertex
  1. T or F: An Euler trail is always the longest trail in an undirected graph.
  1. T or F: A Hamiltonian path, if it exists, is always the longest path in an undirected graph.
  1. The longest path in an undirected graph is bounded by:
    1. the maximum degree of a graph
    2. the number of edges
    3. the number of vertices
    4. the minimum degree of a graph
  1. T or F: All connected, undirected graphs have a spanning tree.
  1. Refering to graphs, Kruskal's algorithm is used to find:
    1. the shortest path between two vertices
    2. all-pairs shortest paths
    3. a minimum spanning tree
    4. the longest path with the least weight
  1. Refering to graphs, Dijkstra's algorithm is used to find:
    1. all-pairs shortest paths
    2. the longest path with the least weight
    3. a minimum spanning tree
    4. the shortest path between a source vertex and the other vertices
  1. Refering to graphs, Prim's algorithm is used to find:
    1. all-pairs shortest paths
    2. the longest path with the least weight
    3. the shortest path between two vertices
    4. a minimum spanning tree
  1. Refering to graphs, the Floyd-Warshall algorithm is used to find:
    1. the longest path with the least weight
    2. a minimum spanning tree
    3. all-pairs shortest paths
    4. the shortest path
  1. Suppose E = ω ( V ) . What is the asymptotic running time of Kruskal's Algorithm? Choose the simplest answer.
    1. Θ ( E log E + V log E )
    2. Θ ( E log E + V log V )
    3. Θ ( E + V log V )
    4. Θ ( E )
    5. Θ ( E log E )
    6. Θ ( E + V )
  1. Suppose E = Θ ( V ) . What is the asymptotic running time of Prim's Algorithm? Choose the simplest answer.
    1. Θ ( E log E + V log V )
    2. Θ ( E + V log V )
    3. Θ ( E + V )
    4. Θ ( E )
    5. Θ ( E log E + V log E )
    6. Θ ( E log E )
  1. T or F: Suppose you kept track of the level number for each vertex w in a breadth-first 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.
  1. T or F: For a simple, undirected graph, Θ ( E log E ) = Θ ( E log V )
  1. 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?
    1. n ( n + 1 ) 2
    2. n ( n + 1 ) 2 - 1
    3. n ( n - 1 ) 2
    4. n
    5. n ( n - 1 ) 2 - 1
    6. n-1
  1. 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?
    1. Θ ( V 3 E )
    2. the correct answer is not listed
    3. Θ ( V E 2 )
    4. Θ ( V 3 log V )
    5. Θ ( V 2 log V )
    6. Θ ( V 2 E )

Concept: The classes 𝒫 and N P

  1. A problem can be in 𝒫 and not in N P .
    1. True
    2. Not known
    3. False
  1. A problem can be in N P and not in 𝒫.
    1. True
    2. Not known
    3. False
  1. All problems are in 𝒫.
    1. False
    2. True
    3. Not known
  1. All problems are in N P .
    1. Not known
    2. False
    3. True
  1. N P stands for:
    1. Non-deterministic Polynomial.
    2. Non-intractable Program.
    3. Non-exponential Program.
    4. Non-Polynomial.
  1. T or F: A constant time algorithm is in 𝒫.
  1. T or F: A linear time algorithm is in 𝒫.
  1. T or F: A constant time algorithm is in N P .
  1. T or F: A linear time algorithm is in N P .
  1. Someone shows you a correct algorithm for problem A whose solution can be verified in polynomial time. You can conclude:
    1. problem A is in N P
    2. nothing about whether problem A is in N P or not.
    3. problem A is not in N P
  1. Someone proves that for a correct algorithm for problem A, solutions must be verified in at least exponential time. You can conclude:
    1. problem A is in N P
    2. nothing about whether problem A is in N P or not.
    3. problem A is not in N P
  1. Someone shows you a correct polynomial time algorithm for problem A. You can conclude:
    1. nothing about whether problem A is in 𝒫 or not.
    2. problem A is in 𝒫
    3. problem A is not in 𝒫
  1. Someone shows you a correct exponential time algorithm for problem A whose solution can be verified in polynomial time. You can conclude:
    1. nothing about whether problem A is in 𝒫 or not.
    2. problem A is not in 𝒫
    3. problem A is in 𝒫
  1. Someone shows you a correct polynomial time algorithm for problem A. You can conclude:
    1. nothing about whether problem A is in N P or not.
    2. problem A is in N P
    3. problem A is not in N P
  1. Which one of the following is not a valid way to prove a problem is in N P :
    1. show that a solution can be verified in polynomial time on a non-deterministic computer.
    2. show that a solution can be found in polynomial time on a non-deterministic computer.
    3. show that a solution can be verified in polynomial time on a deterministic computer.
    4. show that a solution can be found in polynomial time on a deterministic computer.

Concept: N P -completeness

  1. To show that a problem A is N P -complete, one task is to:
    1. show A is not in N P .
    2. show A is not in 𝒫.
    3. show A is in 𝒫.
    4. show A is in N P .
  1. Suppose B is an N P -complete problem. To show that a problem A is N P -complete, one could:
    1. show a polynomial time/space reduction from A to B.
    2. show a exponential time/space reduction from B to A.
    3. show an exponential time/space reduction from A to B.
    4. show a polynomial time/space reduction from B to A.
  1. Another way of stating “a reduction from A to B” is:
    1. convert an algorithm for B to an algorithm for A
    2. solve A-type problems with an algorithm for B
    3. solve B-type problems with an algorithm for A
    4. convert an algorithm for A to an algorithm for B

Concept: If 𝒫 = N P ?

  1. If 𝒫 = N P , then all problems in 𝒫 are in N P .
    1. Not known
    2. True
    3. False
  1. If 𝒫 = N P , then all problems in N P are in 𝒫.
    1. True
    2. Not known
    3. False
  1. If 𝒫 != N P , then there exist problems in 𝒫 that are not in N P .
    1. True
    2. Not known
    3. False
  1. If 𝒫 != N P , then there exist problems in N P that are not in 𝒫.
    1. True
    2. False
    3. Not known

Concept: Proving 𝒫 = N P .

  1. Factoring is in N P . 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 𝒫 = N P ?
    1. 𝒫 != N P
    2. 𝒫 = N P
    3. the question is still unanswered
  1. Factoring is in N P . 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 𝒫 = N P ?
    1. 𝒫 = N P
    2. the question is still unanswered
    3. 𝒫 != N P
  1. Factoring is in N P 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 𝒫 = N P ?
    1. 𝒫 = N P ? is still unanswered.
    2. 𝒫 != N P , but just for quantum computers
    3. 𝒫 != N P for all types of computers.
    4. 𝒫 = N P for all types of computers.
    5. 𝒫 = N P , but just for quantum computers
  1. Subset Sum is N P -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 𝒫 = N P ?
    1. 𝒫 = N P
    2. the question is still unanswered
    3. 𝒫 != N P
  1. Subset Sum is N P -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 𝒫 = N P ?
    1. 𝒫 != N P
    2. 𝒫 = N P
    3. the question is still unanswered
  1. In the past, it was shown how to solve Hamiltonian Path (an N P -complete problem) in linear time, using a DNA-based computer. However, the algorithm takes a factorial number of DNA strands, which need to be created each time. This means:
    1. 𝒫 = N P for all types of computers.
    2. 𝒫 != N P , but just for DNA-based computers
    3. 𝒫 != N P for all types of computers.
    4. 𝒫 = N P ? is still unanswered.
    5. 𝒫 = N P , but just for DNA-based computers
  1. T or F: 𝒫 = N P is just another way of saying, for problems in N P , finding a solution is no harder than verifying a solution.