Exam 1

Question 1

Properties of Logs: LogB(xy) is equal to:

Answer 1

LogB(x) + LogB(y)

Question 2

Properties of Logs: LogB(x/y) is equal to:

Answer 2

LogB(x) - LogB(y)

Question 3

Properties of Logs: Convert LogB(x) To LogA:

Answer 3

LogA(x)/LogA(b)

Question 4

Properties of Logs: LogB(x^n) is equal to:

Answer 4

nLogB(x)

Question 5

Properties of Logs: x^(LogB(Y)) is equal to:

Answer 5

Y^(LogB(x))

Question 6

Master Theorem: What is the formula for master theorem in terms of a, b, and d:

Answer 6

T(n) = aT([n/b]) + O(n^d)

Question 7

Master Theorem: According to master theorem, what is the time: if d > logB(a)

Answer 7

O(n^d)

Question 8

Master Theorem: According to master theorem, what is the time: if d = logB(a)

Answer 8

O(n^d log n)

Question 9

Master Theorem: According to master theorem, what is the time: if d < logB(a)

Answer 9

O(n^(logB(A))

Question 10

Roots of Unity: Multiply: (r1, theta1) (r2, theta2)

Answer 10

([r1 * r2],[Theta1 + Theta2])

Question 11

Roots of Unity: Given the following equation for Z, what would -Z be. Z = (r, theta)

Answer 11

-Z = (t, theta + pi)

Question 12

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)

Answer 12

Z^n = (1, n*theta)

Question 13

Complex Roots of Unity Reference Card

Answer 13

Question 14

What are 5 steps in the FFT algorithm

(in order, high level)

Answer 14

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]

Question 15

What is the process called that takes values from FFT and converts them back into Coefficients?

How is it done?

Answer 15

Interpolation

Rerun the FFT using the values and the inverse of the roots of unity.

Coefficients = 1/n FFT(, w^-1)

Question 16

What is the Big O time for the FFT Algorithm?

Answer 16

n log n

Question 17

FFT Algorithm Reference Card

Answer 17

Question 18

Algorithm Times:

What is time for finding the median via divide and conquer using Big O notation

Answer 18

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)

Question 19

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)

Answer 19

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.

Question 20

Median in linear time

What is the definition of a good pivot (in terms of partition size)?

Answer 20

A good pivot is if our pivot point divides the list between

25% and 75% of the list size.

Question 21

Describe the high level steps to perform a FastSelect

Set = A

Number Element to find = k

6 steps

Answer 21

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

Question 22

Median in linear time

What is the recurrence equation for finding the median in O(n) time including the slack time.

Answer 22

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.

Question 23

Median Reference Card

Answer 23

Question 24

Proof that P is a good pivot?

Reference

Answer 24

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.

Question 25

What is the sum of the nth roots of unity when both even and odd roots are kept in?

Answer 25

0

Question 26

What is the product of all the even roots of unity?

Answer 26

-1

Question 27

What is the product of all the odd roots of unity?

Answer 27

1

Question 28

What is the big-O time for FastMultiplication

What is the big-o time for normal multiplication

Answer 28

O(n^log₂3)

O(n²)

Question 29

What is big-O time for Merge Sort

Answer 29

O(n log(n))

Question 30

What is a common equivilant equation for the following:

-(W_n^k)

Answer 30

-(W_n^k+n/2)

Question 31

What is another equivilant formula for

(INVERSE)

(w_n^k)^-1

Answer 31

(w_n^n-k)

or

(w_n^-k)

Question 32

What is the equivilant of the following:

(Square)

(w_n^k)²

Answer 32

(w_n/2^k)

Squaring is the same as reducing the number of elements. (This is important for FFT)

Question 33

For an n-1 degree polynomial with size n, what will be the root of unity that we will use.

Answer 33

we use the nth root of unity.

Question 34

What does the following formula equal:

(w_n^k)^-1 * (w_n^k) =

Answer 34

1

Question 35

What is the recurrence for a single source shortest path?

Answer 35

Question 36

The number of candidates for an optimal solution to a single source shortest path is equal to?

Answer 36

The number (1 + the number of verticies going into the end point.)

Question 37

What is the big-O time for the single source shortest path algorithm?

Answer 37

O(n³)

1. Loop one (1 to n) for the sub problem size. How many hops?
2. Inner loops 2, for each vertex in the verticies
3. third inner loop is the recurrence to find the min, goes through all edge weights going into a node.

Question 38

Single Shortest Path Base Case?

Answer 38

A[0,S] = 0

A[.,.] = +Inf

Question 39

When does the single shortest path algorith stop?

Answer 39

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.

Question 40

What is Eculid’s extended formula for GCD

Answer 40

gcd(a,b) = d

d = ax + by

gcd(b, a mod b) = bx + (a mod b)y