Exam 1 Flashcards
Properties of Logs: LogB(xy) is equal to:
LogB(x) + LogB(y)
Properties of Logs: LogB(x/y) is equal to:
LogB(x) - LogB(y)
Properties of Logs: Convert LogB(x) To LogA:
LogA(x)/LogA(b)
Properties of Logs: LogB(x^n) is equal to:
nLogB(x)
Properties of Logs: x^(LogB(Y)) is equal to:
Y^(LogB(x))
Master Theorem: What is the formula for master theorem in terms of a, b, and d:
T(n) = aT([n/b]) + O(n^d)
Master Theorem: According to master theorem, what is the time: if d > logB(a)
O(n^d)
Master Theorem: According to master theorem, what is the time: if d = logB(a)
O(n^d log n)
Master Theorem: According to master theorem, what is the time: if d < logB(a)
O(n^(logB(A))
Roots of Unity: Multiply: (r1, theta1) (r2, theta2)
([r1 * r2],[Theta1 + Theta2])
Roots of Unity: Given the following equation for Z, what would -Z be. Z = (r, theta)
-Z = (t, theta + pi)
Roots of Unity: Roots of unity can be solved using the formula Z = (r, theta) What is the nth root of unity: E.g. Z^n = ???? (Assume a unit circle)
Z^n = (1, n*theta)
Complex Roots of Unity Reference Card
What are 5 steps in the FFT algorithm
(in order, high level)
FFT(A, w)
1) if w = 1: Return A(1)
2) Express A(w) in the forms Ae + xAo
3) r1 = Call FFT(Ae, w^2) - evaluate Ae at even power roots of unity.
4) r2= Call FFT(Ao, w^2) - evaluate Ao at even power roots of unity.
k = n/2
5) Loop j = 1 to k - 1:
r[j] = r1[j] + w^j * r2[j]
r[j+k] = r1[j] - w^j * r2[j]
Return = r[0…n]
What is the process called that takes values from FFT and converts them back into Coefficients?
How is it done?
Interpolation
Rerun the FFT using the values and the inverse of the roots of unity.
Coefficients = 1/n FFT(, w^-1)
What is the Big O time for the FFT Algorithm?
n log n
FFT Algorithm Reference Card
Algorithm Times:
What is time for finding the median via divide and conquer using Big O notation
If we had to sort it, it would require O(nlog(n)) however
using the divide and conquer method we can make it linear at O(n)
Median in linear time.
When selecting an algorithm to find a good pivot, what does the coefficient a for the master theorem be for the recurrence equation T(an) + O(n) = O(n)
The recurrence equation T(n) = T(an) + O(n)
The a must be < 1 to converge to O(n)
We need a pivot that guarantees we eliminate a constant fraction of elements each iteration.
Median in linear time
What is the definition of a good pivot (in terms of partition size)?
A good pivot is if our pivot point divides the list between
25% and 75% of the list size.
Describe the high level steps to perform a FastSelect
Set = A
Number Element to find = k
6 steps
1) Break the elements A into n/5 groups of 5 elements.
2) Sort each subgroup (with only 5 elements it’s O(1) & select the median from each sub group
4) Combine the medians from all n/5 groups into a new set A
5) Call Fast Select with the new group, and k/5, this returns a partition value p.
6) Partition A into A
p
6) If K <= A
if K > A
p, k-len(|A
Else return P
Median in linear time
What is the recurrence equation for finding the median in O(n) time including the slack time.
T(n) = T(3n/4) + T(n/5) + O(n)
The selection of a good pivot is T(3n/4) remember that by selecting a pivot in the mid 50% (between n/4 and 3n/4, our worst partition would have 3n/4 elements.
The T(n/5) is slack time. Remember that for the above equation to equal O(n) the T numbers must add up to be less than 1. So 3n/4 leaves us slack (1/4) and if we can find a good pivot in that T(n/5) + O(n) time, we will still have an O(n) algorithm.
Median Reference Card
Proof that P is a good pivot?
Reference
Graphically, groups are broken down into elements of 5
Those groups are sorted so everything above the middle element is less than it, everything below greater.
If we sort those grouped elements, the very middle median is our result. That is at position 1/2 * n/5 or n/10
Looking at that, everything to the left and above it has to be less than or equal to that pivot point. In groups of 5, that means we have 3 elements above the line. giving us 3n/10 in the worst case.
3/10 = 30%, best case is the inverse 7/10 = 70%. We wanted our selection between 25% and 75% to be a good pivot, so this algorithm always gives us a value in the range we need.
What is the sum of the nth roots of unity when both even and odd roots are kept in?
0
What is the product of all the even roots of unity?
-1
What is the product of all the odd roots of unity?
1
What is the big-O time for FastMultiplication
What is the big-o time for normal multiplication
O(nlog23)
O(n2)
What is big-O time for Merge Sort
O(n log(n))
What is a common equivilant equation for the following:
-(Wnk)
-(Wnk+n/2)
What is another equivilant formula for
(INVERSE)
(wnk)-1
(wnn-k)
or
(wn-k)
What is the equivilant of the following:
(Square)
(wnk)2
(wn/2k)
Squaring is the same as reducing the number of elements. (This is important for FFT)
For an n-1 degree polynomial with size n, what will be the root of unity that we will use.
we use the nth root of unity.
What does the following formula equal:
(wnk)-1 * (wnk) =
1
What is the recurrence for a single source shortest path?
The number of candidates for an optimal solution to a single source shortest path is equal to?
The number (1 + the number of verticies going into the end point.)
What is the big-O time for the single source shortest path algorithm?
O(n3)
- Loop one (1 to n) for the sub problem size. How many hops?
- Inner loops 2, for each vertex in the verticies
- third inner loop is the recurrence to find the min, goes through all edge weights going into a node.
Single Shortest Path Base Case?
A[0,S] = 0
A[.,.] = +Inf
When does the single shortest path algorith stop?
When the edge budget n has been exhausted
Or
When the responses stabilize and no more changes are made to the costs in an iteration.
What is Eculid’s extended formula for GCD
gcd(a,b) = d
d = ax + by
gcd(b, a mod b) = bx + (a mod b)y
