Exam 1 - Divide and Conquer Flashcards
Is pseudocode allowed in the D&C written questions?
No
In the D&C written questions, each recurrence should be a ____ problem than before
Smaller
In the D&C written questions, each solution must be more efficient than ____
The brute force solution
In the D&C written questions, what are the three sections expected?
Algorithm Description
Correctness Justification
Runtime Analysis
In the D&C written questions, what is expected in the Algorithm Description section?
How to solve the problem
In the D&C written questions, what is expected in the Justification of Correctness section?
Why the algorithm solves the problem
In the D&C written questions, what is expected in the Runtime Analysis section?
The big-O runtime of the algorithm, including the big-O runtimes for all nontrivial steps of the algorithm
In the D&C written questions, can the master theorem be used for the runtime analysis?
Yes
What is the input for FastMultiply?
Two n-bit integers x and y, where n is some power of two
What is the output of FastMultiply?
x times y
FastMultiply starts by splitting x and y into what components?
X_l, Y_l, X_r, Y_r
They are the left and right n/2 bits of x and y
After FastMultiply splits X and Y into left and right halves, how does it calculate the three subproblems?
A is FastMultiply(X_l,Y_l)
B is FastMultiply(X_r,Y_r)
C is FastMultiply(X_l+X_r,Y_l+Y_r)
After FastMultiply calculates A, B, and C, how does it use those values to calculate the output value?
2^n * A +
2^(n/2) * (C - A - B)
+ B
What’s the input formula for the master theorem?
What are the input constraints of the master theorem?
a > 0, b > 1, d >= 0
What is the result of the master theorem if d > log (b, a)
O(n^d)
What is the result of the master theorem if d = log (b, a)
O(n^d log n)
What is the result of the master theorem if d < log (b, a)
O(n^(log(b,a)))
What is the recurrence for the runtime of fastmultiply?
T(n) = 3T(n/2) + O(n)
What does the master theorem tell us the big-O of fastmultiply is, given that its recurrence is T(n) = 3T(n/2) + O(n)
O(n^(log(2,3)))
What is the input of mergesort?
An array of numbers a[1…n]
What does mergesort return if the input array has size 1?
The input array, unmodified
What does mergesort return if the input array has size > 1
In mergesort, what does the merge subroutine do if either if the inputs is empty?
It returns the other input
In mergesort, the merge subroutine is given two arrays, x[1…k] and y[1…l]. What does it do if x[1] is <= y[1]?
In mergesort, the merge subroutine is given two arrays, x[1…k] and y[1…l]. What does it do if x[1] is NOT <= y[1]?
What is the recurrence of the runtime for mergesort?
T(n) = 2T(n/2) + O(n)
What is the runtime for mergesort, given that the recurrence is T(n) = 2T(n/2) + O(n) ?
O(n log n)
What is FastSelect for?
Finding the kth smallest element in an unsorted list of numbers
What are the inputs to FastSelect?
A, an unsorted list of numbers of size n
k, an integer 1 <= k <= n
What is the first step of FastSelect?
Break A into n/5 groups, G1, G2, … G(n/5)
After splitting A into the n/5 G groups, what does FastSelect do next?
For i from 1 to n/5, sort Gi and let m_i be the median of Gi
After calculating the Gi medians, what does FastSelect do?
Creates set S which includes all of the medians of the G groups
S = {m_1, m_2, …, m_(n/5)}
After creating set S, what does FastSelect do?
It finds the pivot value p by recursing on S
p = FastSelect(S, n/10)
After calculating the pivot value p, what does FastSelect do?
It partitions A into A<p, A=p, A>p
After partitioning A based on pivot p, what does FastSelect do if k <= |A<p|?
It recurses on the A<p set
return FastSelect(A<p, k)
After partitioning A based on pivot p, what does FastSelect do if k > |A<p| + |A=p|?
It recurses on the A>p set
return FastSelect(A>p, k-|A<p|-|A=p|)
After partitioning A based on pivot p, what does FastSelect do if k is not <= |A<p| and not > |A<p| + |A=p|?
it returns p
What is the runtime of the step of FastSelect where it breaks A into n/5 groups of 5 elements each?
O(n)
What is the runtime of the step of FastSelect where it sorts the G groups, calculates their medians, and creates set S?
O(1) per group, which results in O(n)
What is the recurrence of the step of FastSelect where it calculates pivot p based on the set of medians S?
T(n/5)
What is the recurrence of the step of FastSelect where it recurses on one of the partitioned sections of A?
T((3/4)n)
Why do we know that FastSelect finds a good pivot p value?
