Exam 1

Question 1

Master Theorem (Book)

Answer 1

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)

Question 2

Binary Search

Answer 2

requires a list be sorted.

BinarySearch(sortedArray):

mid = (high - low) / 2
if(mid = goal):
return mid
if(midgoal):
BinarySearch(low,mid-1)

return -1

Question 3

1 + 2 + 3 + 4 + … + (n-1) = ?

Answer 3

( (n-1) * n ) / 2

Question 4

Longest Increasing Subsequence (LIS) Recurrence

Answer 4

T(i) =1
If a[j] < a[i]:
T(i) = max{ T(i), T(j) + 1) }for 1<=i<=n and 1<=j

Question 5

Longest Common Subsequence (LCS) Recurrence

Answer 5

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

Question 6

Edit Distance Recurrence

Answer 6

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)}

Question 7

Knapsack (no repeats) Recurrence

Answer 7

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)

Question 8

Knapsack (with repeats) Recurrence

Answer 8

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)

Question 9

Fast Matrix Multiplication Runtime

Answer 9

O(n^3)

Question 10

Difference between Bellman-ford and Floyd-Warshall algorithms.

Answer 10

• 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)

Question 11

Runtime of Dijkstra’s algorithm

Answer 11

O((n+m) log(n)) where n is vertices and m is edges

Question 12

Does Dikjstra’s algorithm work if negative weights are allowed

Answer 12

No. It requires all edge weights are positive. It’s not guaranteed to produce the right output when the edge weights can be positive.

Question 13

Fibonacci’s Numbers Recurrence

Answer 13

T(0) = 0 
T(1) = 1 
T(n) = T(n-1) + T(n-2)

Question 14

Dictionary Lookup (Sequence of words?) Recurrence

Answer 14

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

Question 15

Longest Common String Recurrence

Answer 15

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

Question 16

Inputs to FFT and IFFT

Answer 16

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.

Question 17

What is the sum of the nth roots of unity for even n?

Answer 17

0

Question 18

What is the product of the nth roots of unity when n is odd and when n is even?

Answer 18

Even = -1
Odd = 1

Question 19

How do you determine what n-roots of unity to use in FFT when using it for polynomial multiplication: A * B?

Answer 19

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.

Question 20

What nth root of unity should you use in FFT for a polynomial of power n

Answer 20

The power of 2 closest to the (n+1)th root of unity.

Question 21

What is the geometric series 1 + w_n + w_n^2 + … + w_n^{n-1} equal to?

Answer 21

1 * (1-w_n^n) / (1-w_n)
Note: w_n^n = 1 so this equals 0.

Question 22

What is the recurrence for Floyd-Warshall?

Answer 22

min { D(i-1,s,t), D(i-1,s,i)+D(i-1,i,t) }

Question 23

What is the runtime of fast-multiply?

Answer 23

O(n^{log_2(3)})

Question 24

Describe Recursion for FastMultiply

Answer 24

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)

Question 25

What runtime can you find the median using DP?

Answer 25

Linear: O(n)

Question 26

Bellman-Ford Recurrence

Answer 26

for i=1->n-1:
for all z in V:
for all yz in E:
D(i,z) = D(i-1,z)
if D(i,z) > D(i-1,z) + w(y,z):
D(i,z) = D(i-1,z) + w(y,z)
return D(n,:) (whole row)

Question 27

Maximum sum recurrence

Answer 27

T(i) =ai+ max (0,T(i−1)) for 1<=i<=n