Exam 1 Flashcards
Master Theorem (Book)
if d>log_b(a): O(n^d)
if d=log_b(a): O(n^d log(n))
if d < logb(a): O(n^log_b(a))
T(n) = aT(⌈n/b⌉) + O(n^d)
Binary Search
requires a list be sorted.
BinarySearch(sortedArray):
mid = (high - low) / 2
if(mid = goal):
return mid
if(midgoal):
BinarySearch(low,mid-1)
return -1
1 + 2 + 3 + 4 + … + (n-1) = ?
( (n-1) * n ) / 2
Longest Increasing Subsequence (LIS) Recurrence
T(i) =1
If a[j] < a[i]:
T(i) = max{ T(i), T(j) + 1) }for 1<=i<=n and 1<=j
Longest Common Subsequence (LCS) Recurrence
T(i,0) = 0 for 0\<=i\<=n T(0,j) = 0 for 0\<=j\<=m
If (x[i] != y[i]):
T(i,j) = max{ T(i-1,j), T(j,i-1) }
else:
T(i-1,j-1) + 1
Edit Distance Recurrence
T(i,0) = 0 for 0\<=i\<=n T(0,j) = 0 for 0\<=j\<=n
T(i,j) = min{ 1+T(i,j-1), 1+T(i-1,j), diff(i,j) + T(i-1,j-1)}
Knapsack (no repeats) Recurrence
T(b,0) = 0 for 0\<=b\<=B T(0,i) = 0 for 0\<=i\<=n
if(w[i] <=b):
T(b,i) = max{ T(b,i-1), T(b-w[i],i-1) + v[i] }
else:
T(b,i) = T(b,i-1)
Knapsack (with repeats) Recurrence
T(b,0) = 0 for 0\<=b\<=B T(0,i) = 0 for 0\<=i\<=n
if(w[i] <=b):
T(b,i) = max{ T(b,i-1), T(b-w[i],i) + v[i] }
else:
T(b,i) = T(b,i-1)
Fast Matrix Multiplication Runtime
O(n^3)
Difference between Bellman-ford and Floyd-Warshall algorithms.
- Bellman-ford: single-source shortest path. If the negative weight cycle is not reachable from the start vertex, it won’t find them. It finds negative weight cycles reachable from a single source. Runs in O(nm) where n=vertices and m=edges.
- Floyd-Warshall: all-vertices shortest path. Finds negative weight cycles anywhere in the graph. Runs in O(n^3)
Runtime of Dijkstra’s algorithm
O((n+m) log(n)) where n is vertices and m is edges
Does Dikjstra’s algorithm work if negative weights are allowed
No. It requires all edge weights are positive. It’s not guaranteed to produce the right output when the edge weights can be positive.
Fibonacci’s Numbers Recurrence
T(0) = 0 T(1) = 1 T(n) = T(n-1) + T(n-2)
Dictionary Lookup (Sequence of words?) Recurrence
T(0) = True T(i) = False T(i) = T(i) or ( T(j-1) and dict(j...i) ) for 1\<=i\<=n and 1\<=j\<=i
Longest Common String Recurrence
T(i,0) = 0 for 0\<=i\<=n T(0,j) = 0 for 0\<=j\<=m
If x[i] = y[j]:
T(i,j) = T(i-1,j-1) + 1
else:
T(i,j) = 0
Inputs to FFT and IFFT
FFT: (A,w_n^1) where A = n-sized matrix of polynomial coefficients.
IFFT: (A’,w_n^-1) * 1/n where A’ = n-sized matrix of values representing polynomial A.
What is the sum of the nth roots of unity for even n?
0
What is the product of the nth roots of unity when n is odd and when n is even?
Even = -1 Odd = 1
How do you determine what n-roots of unity to use in FFT when using it for polynomial multiplication: A * B?
a = degree of polynomial A
b = degree of polynomial B
n = 2^{ ceil(log_2(a+b)) }
This the power of 2 closest to a + b.
What nth root of unity should you use in FFT for a polynomial of power n
The power of 2 closest to the (n+1)th root of unity.
What is the geometric series 1 + w_n + w_n^2 + … + w_n^{n-1} equal to?
1 * (1-w_n^n) / (1-w_n)
Note: w_n^n = 1 so this equals 0.
What is the recurrence for Floyd-Warshall?
min { D(i-1,s,t), D(i-1,s,i)+D(i-1,i,t) }
What is the runtime of fast-multiply?
O(n^{log_2(3)})
Describe Recursion for FastMultiply
A = FastMultiply(xl,yl)
B = FastMultiply(xr,yr)
C = FastMultiply(xl+xr,yl+yr)
z = 2^n*A + 2^{n/2}(C-A-B) + B
Return(z)
