Exam 1 Flashcards
Studying
What is the approach for designing a dynamic programming problem?
- Define the subproblem in words and try the same problem on a prefix of the input
- Define e recursive relation which expresses k(i) - the solution to the ith subproblem - in terms of smaller subproblems ex) k(1) … k(i-1)
What are some example algorithms for the divide and conquering technique?
merge sort and solving recurrences
Euclids GCD algorithm
Multiplying n-bit integers
FFT
Median
What is Gause’s idea?
It’s based on the idea that:
- multiplication is expensive
- adding and subtracting is cheap
- the product of 2 complex numbers results in 4 terms where each is multiplied with itself
- thus we need 4 real number multiplications to solve
- We can reduce these term multiplications from 4 to 3
original) Ac - bd - (bc + ad)
new) ac, bd, (a +b)(c+d)
both give us the result (a +bi)(c + di)
How does the D&C approach work for the multiplying 2 numbers for the naive approach?
input = x, y where both are n-bit integers
output = z where z = xy?
Runtime is based on the number of bits in x and y
Idea is the break each of the inputs into 2 halves
- Break the input into 2 halves and solve the problems on the 2 halves recursively
ex) x = 182 to binary 10110110
X_l = 1011 = 11
X_R = 0110 = 6
182 = 11 * 2^4 + 6
General:
x = XL * 2^(n / 2) + XR
How does the D&C approach work for the multiplying 2 numbers for the recursive approach of easy multiply? What is the runtime?
input = x, y where both are n-bit integers
output = z where z = xy?
partition x: XL * 2^(n / 2) + XR
partition y: = YL * 2^(n / 2) + YR
So xy = (XL * 2^(n / 2) + XR) (YL * 2^(n / 2) + YR)
Simplify it to be:
(2^n * XL * YL) + (2^(n/2))(XLYR + XRYL) + XRYR
- This results in 3 terms (multiplied with each other) and then added together to give us xy
This is the pseudocode for easymultiply(x,y)
EasyMultiply PseudoCode:
A = easymultiply(xL,yL)
B = easymultiply(xR,yR)
C = easymultiply(xL,yR)
D = easymultiply(xR,yL)
z = (2^n) * A + (2^n/2)(C + D) + B
Runtime = 4 T(n/2) + O(n) = O(n^2)
What is the equation for the improved approach or fast multiply? What change was made?
We simply from 4 to 3 multiplications
(2^n * XL * YL) + (2^(n/2))(XLYR + XRYL) + XRYR
We convert the above to the following:
xy = (2^n)A + (2^n/2)(C- A - B) + B
which is now 3 terms
The run time is now:
O(n ^ log2 3)
This is from:
T(n) = 3T(n/2) + O(n)
evaluates to O(n ^ log2 3)
What are the general forms of recurrence?
For:
T(n) = aT(n / b ) + O(n)
O(n ^ log b a). if a > b
O(n log n). if a = b
O(n) if a < b
What is the name of the shortest path algorithm that finds the single source shortest path from S to any vertex? What is the input, output, and runtime? How does this algorithm work (general steps)? What is it’s limitation?
Dijkstra’s
Input: graph, S E V
Output: distance of Z for all vertices in the graph (Z E V)
The way works:
- Explores the graph in BFS approach
- Take O (n + m) for the BFS exploration (linear time)
- Also takes O (log n) for the min heap or priority queue for the weights
Take total time: O (n + m) * log (n)
Requires positive weights in the graph
What are negative weight cycles in the shortest path problem and how do they affect the result?
They disrupt the finding of the shortest path because a walk through the cycle ends up with negative distances / weights and potentially negative infinity for these values when walking
What is the dynamic programming idea when it comes to finding the shortest path for a single source to the vertices? What is the base and recurrence cases?
- We use a prefix of the result path and condition on the number of edges in the path
- The DP idea => introduce variable i ranging from 0 to n - 1 which is the number of edges that we allow on the paths
For 0 <= i <= n - 1 Z E V
Let D(i, z) = length of the shortest path from S to Z using i <= edges
Base cases:
D(0,S) = 0 the distance of S to itself
For all Z E S, D (0, Z) = infinity if no edge to Z
Recurrence case:
For i >= 1 (when i is at least 1):
If using at most i - 1 edges then
Min { D(i-1, z) , miny { D(i-1, y) + w(y,z) } }
D(i-1, z) if solution uses i - 1 edges
Try all choices for penultimate vertex y and take shortest path from s to y using i-1 edgers + the length of the last edge ( miny { D(i-1, y) + w(y,z) } )
What is the name of the algorithm that is similar to Dijkstra’s but handles negative weight edges and negative cycles? What is the overall time complexity? What are the steps and what does it ultimately return?
Bellman-Ford
Time complexity: O(nm)
Steps:
Init base cases where i = 0
D(0, S) = 0
D(0, Z) = infinity for all Z E V
Then for i = 1 to n - 1
For all Z E V
Set D(i, z) = D(i - 1, z)
For y -> z E edges:
Update to D(i, z) = D(i - 1, y) + w(y,z) if it’s smaller than D(i - 1, z)
Return D(n-1, . )
How are negative cycles detected in Bellman Ford?
When there’s a negative length cycle, there’s going to be shorter distance for the same vertex in the next i value which keeping shrinking over time
When there’s a negative cycle, i = n is going to smaller than i = n - 1. This shouldn’t normally happen
So how do we determine if there’s a negative weight cycle:
We compare the 2 rows n and n - 1 to see if there different - specifically if n is smaller than n - 1
What are 2 algorithm approaches to finding all pairs shortest path for a graph with edges?
A. All-pairs shortest path Bellman-Ford variant
how it works:
- input a graph with vertices/edges/weights for edges
For all edge pairs in the graph y -> z, we find the shortest path by running Bellman-Ford for all S E V
Run time is O(n^2 m)
B. Floyd Warshall
Run time: O(n^3)
How it works:
For every S from 1 to n
Check every t 1 to n
If there’s an edge between s and t then base case = w(s,t) the weight s and t
Else it’s an infinity
For 1 <= i <= n
For 1 <= s <= n
For 1 <= t <= n
D(i,s,t) = min { D(i-1, s, t), D(i - 1, s, i) + D(i - 1, i, t) }
Return D(n, . , . )
We return the case where i = n (return matrix D(n . .) for all possible pair paths
What is the difference between the 2 different all shortest paths algorithms in how they handle negative cycles?
All paths Belman-Ford:
Single source shortest path
Won’t always find the negative cycle because cycles may not be reachable from the start vertex
Floyd-Warshall:
All pairs shortest path
Will find the negative cycles
What is the base case and recurse case for the Fibonacci recursive problem? What is the run time? Is this the best solution? Why or why not?
The recursive formula for the fibonacci problem is
Fn = Fn-1 + Fn-2 (this is true for any nth Fib that is our input)
The base case for this problem is the first two fibonacci numbers which are 0 and 1
F(0) = 0
F(1) = 1
Runtime:
T(n) <= O(1) + T(n-1) + T(n-2)
O(1.618 ^ n ) or exponential run time
This is not the most optimal solution and therefore not the best solution
Why it’ s not optimal is because we calculate the same subproblems over and over again when recursing down the tree of subproblems. We need to store the previously solved subproblems
Describe the dynamic programming solution for the Fib numbers problem. What is the pseudocode for this problem?
A better solution would involve the following:
- Starting with smaller fibonacci numbers and saving the computed values for later calculation of larger values
- Using an array or hash table to store
Name the characteristics of a dynamic programming solution for this course:
- no recursion
- There is no recursion in dynamic programming
Memoization is another approach where a hash table is used to store the solutions
What is the pseudocode for the dynamic programming solution for the Fib problem?
Base case: input n is equal to 0 or 1
return 0 if n = 0
return 1 if n = 1
Otherwise set each in the solution array
for i = 2 -> n
F[i] = F[i-1] + F[-2]
Return F[n]
Runtime: O(n) based on the input n
What is a difference between a substring and a subsequence?
Substring = set of consecutive elements
Subsequence = set of elements in order (where skips can happen)
What is the subproblem and the recursive relation in the LIS problem?
Subproblem:
L(i) = LIS in a1 … ai which includes ai
Recursive relation:
L(i) = 1 + max { L(j) where 1 <= j <= i - 1 and aj < ai }
What is the pseudocode for the LIS problem? What is the run time?
for 1 -> n:
L(i) = 1
for j -> i - 1:
if aj < ai and L(i) < L(j) + 1:
L(i) = L(j) + 1
max = 1
for 2 -> n:
if L(i) > max:
max = i
return L(max)
Runtime: O(n ^ 2)
What is the psuedocode for the LCS problem? What is the subproblem? What is the runtime?
Subproblem:
The subproblem is the LCS of a prefix of the input of s1..si where i < n
We need two terms i, j
Base case:
for i = 0 -> n:
L(i, 0) = 0
for j = 0 -> n:
L(0, j) = 0
for i -> n:
for j -> n:
if xi = yj:
L(i, j) = 1 + L(i - 1, j - 1)
else:
L(i, j) = max { L(i, j - 1), L(i - 1, j)
return L(n,n)
(return the last value)
runtime: O(n ^ 2)
What is the median problem and what is the easy solution? What is the run time and name of algorithm involved?
Given a unsorted list A [A1…An], find the median or the n/2 smallest
other version is find the k smallest
Easy algorithm: sort A and an then output the kth element or n/2 element
merge sort can be used O (n log n)
What is an improved solution to the find median problem? What is its pseudocode?
BFPRT algorithm
It’s similar to the quicksort algorithm where a pivot p is chosen
then partition A into 3 groups:
A < p
A = p
A > p
We want the median or something close to it when choosing a pivot
The difference is that we don’t have to recursively consider both sublists. We only have to search in one of these 2 lists
Quick Select Pseudocode:
- choose a pivot p close to the median
- then partition A into 3 groups:
A < p
A = p
A > p - if k <= A <p then quickselect(A < p, k)
if k > |A < p | + |A = p | then quickselect(A > p, k - 1 - |A < p| - |A=p| )
if | A < p| < k <= | A < p| + |A = p | then return p
A good pivot is chosen by:
- we approximate a median because we don’t have the original median
- we can find a pivot that satisfies or falls in the range of n/4 to 3n/4
- the worst case in the above range is
T(3n/4) + O(n) which is O(n) runtime
In fact, this is the case if our band is from n/100 to 99/100 we still can achieve O(n)
There’s exactly n/2 good pivots with a P(1/2) of choosing a good pivot. We can choose again until we have a good pivot
It takes O(n) expected time to find a good pivot and then once you find one a good pivot leads to O(n) run time for an overall O(n)
What is the process of choosing a good pivot for the median problem?
A good pivot is chosen by:
- we approximate a median because we don’t have the original median
- we can find a pivot that satisfies or falls in the range of n/4 to 3n/4
- the worst case in the above range is
T(3n/4) + O(n) which is O(n) runtime
In fact, this is the case if our band is from n/100 to 99/100 we still can achieve O(n)
There’s exactly n/2 good pivots with a P(1/2) of choosing a good pivot. We can choose again until we have a good pivot
It takes O(n) expected time to find a good pivot and then once you find one a good pivot leads to O(n) run time for an overall O(n)
Steps: for finding good pivot
- Break A in n/5 groups of 5 elements each
- For each group, we sort it (takes order of 1 time)
- Choose 1 representative of each group
- Choose in a way that at least 2 of the elements are at most <= x and two of the elements are at least >= x
Example group G
G = x1, x2, x3, x4, x5
What is the pseudocode for fast select where a good pivot is chosen? What is the run time?
Steps:
Find good pivot - break A into n/5 groups -> G, G2, G3.. Gn/5
For i = 1 -> n / 5 (for loop over the n/5 groups)
For the ith group we want to find the median by first sorting this group and then we take the median of these five elements where mi becomes the group median of Gi
We want to look at n/5 medians we found in step 2. Let S denote this set of n over 5 medians
We next find the median of this set S. This will be a pivot P by recursive calling the FastSelect(S, n/10) -> median of the set of S = store as P
We then use P as pivot and partition into 3 groups -> less than P, equal to P, and greater than P
Recurse on the A<p or A>p or output p
Runtime:
Breaking A into 5 groups => O(n)
Sorting a group of 5 => O(1) / group => O(n)
Run FastSelect on subset S to get partition => T(n/5)
Partition A into 3 subgroups => O(n)
Recurse over 3 subproblems => because P is a good partition, then T(3/4n)
T(n) = T(3/4n) + T(n/5) + O(n) = O(n)
What is the knapsack problem? What the two types of Knapsack problems?
Problem:
Inputs: integers weights and values (weights and values are corresponding), total capacity (of the sack)
Output: the subset where we maximize the values V while keeping the weights less than or equal to the total capacity
Two versions of the knapsack problem:
A. One copy of each object - without repetition (1 copy)
B. Unlimited supply of each object - with repetition (unlimited supply
What is the subproblem in words and the recurrence of the knapsack problem?
Subproblem:
K(i, b) = The max value achievable in subset S where 0 <= i <= i and 0 <= b <= B
The recurrence:
for 0 <= i <= n and 0 <= b <= B
k(i, b) = max value achievable using subset from 1 up to i and and under total weight <= b
What is the base case , recurrence case, and pseudocode for the knapsack problem no repeat?
What is the runtime? Is it efficient?
Base cases:
k(0,b) = 0
k(i, 0) = 0
Recurrence cases:
for 0 to b
K(0, b) = 0
for 1 to n:
K(i, 0 ) = 0
for 1 <= i <= n
for 1 <= b <= B
if wi <= b:
k(i,b) = max {
vi + k(i-1, b - wi), k(i - 1, b)
}
else:
k(i,b) = k(i - 1, b)
return K(n, b)
(last value in the 2D table or bottom right)
Runtime: O(nb)
No, it’s not polynomial because it’s not a polynomial in the input size. B is just a number where the space required for it is O(log B). Thus, the input size is n and log B size. it’s an NP complete problem
What is the knapsack with repetition pseudocode, base case, recurrence, and run time?
This time we only need the term b where we focus on the weight
base case:
K(b) = 0
recurrence:
K(b) = max achievable using weight b <= B
try all possibilities of the last object to add
pseudocode:
for b = 0 to B:
K(b) = 0
for i = 1 to n:
if wi <= b and
k(b) < vi + k(b -
wi) then k(b) = vi
\+ k(b - wi)
return K(b)
we return the last entry of our table
We make a separate array S
Init to S[b] = 0 to start
And then when we settle into the if-then statement, we update S[b] to be i
We can then use the S set to backtrack to produce a multiset which obtains the maximum value
Runtime: O(n B); same runtime as the other knapsack problem but just smaller space complexity
What is the goal of the chain matrix multiply problem?
We have 4 matrices A, B, C, D
Think of these matrices as having integer values for the entries
Goal is to compute the product of these matrices most efficiently
General problem:
given matrices A1, A2, ..An
where Ai is mi-1 * mi
What is the min cost for multiplying these matrices
input: m0, m1, … mn
output: find min cost for multiplying these matrices
All we need to determine the costs for computing is the size of these matrices
What is the subproblem in words and the recurrence for matrix multiply?
Subproblem:
Defining the subproblem in words:
C(i) = min cost for computing A1…Ai (first i matrices in the input)
There are 2 params i and j where i is the start of the substring and j is the end of the substring
Recurrence for C(i, j) Base Case
Base case is when i = j and thus just computing Ai
C(i, i) = 0
These are the diagonal entries C(i, i) see above
Recurrence general case:
The recurrence (general) case is the following:
- Corresponds to computing the matrices defined by the substring from i to j
- Root of the tree is from Ai…Aj
- We are trying to find the split L
- Left subtree -> Ai … AL
- Right subtree -> AL+1 … Aj
- We try all possibilities for the index L for the split and then we look up in our table the minimum cost for computing the left subtree (corresponding to a smaller substring) - we do the same for the right subtree
-We combine these together
- Left matrix mi-1 * mL
- Right matrix mL * mj
Total cost of the split of the split at index L is the following:
( Mi-1 * ML * Mj ) + C(i, L) + C(L+1, j)
root -> ( Mi-1 * ML * Mj )
left subtree -> C(i, L)
right subtree -> C(L+1, j)
Ps
What is the pseudocode for matrix multiply?
for i -> n
C(i,i) = 0
for 1 <= s <= n - 1
for 1 <= i <= n - s
j = i + s
c(i, j) = infinity
for l = i -> j - 1
current = mi-1mlmj + C(i, l) + C(l+ 1, j)
if C(i,j) > curent:
C(i,j) = curent
return C(L,n)
Total run time is O(n ^ 3) given the 3 nested for loops
You and a friend are going on a road trip to your new school across the country along a set route. Since you have hardly seen the world, you also want to make the most of this trip. Along your route you have a series of possible sites to visit, recorded in array D in order as di = distance the ith site is from home along the route, and the Coolness factor array C where ci = coolness of the ith site. However, because you are in a rush to get there before the start of school, you’ve agreed to only stop at a site once every 300 miles or more.
Design a DP solution to maximize the Coolness of your trip.
Input: Distance array D [d1, d2, … , dn], and Coolness array C [c1, c2, … , cn], both of positive integers.
Output: Maximum Coolness possible from the trip
Question: Define the entries of your table in words, E.g. T(i) or T(i,j) is..
Let T(i) = maximum coolness of a trip up to and including the ith site.
