Finals Flashcards
Dynamic Programming Longest Palindrome
What are the base and recursive cases?
Base Case:
- i == j
- return {i}
- i == j-1 && A[i] == A[j]
- return {i,j}
Recursive Cases:
- A[i] == A[j]
- recursively search S = A[i+1…j-l]
- return {i} U S {j}
- A[i] != A[j]
- recursively search s1 = A[i…j-l]
- recurisvely search s2 = A[j+1…j]
- returns max of s2, s1
Dynamic Programming Longest Palindrome
What does i and j refer to?
What does subProbSols[i][j] refer to?
What location returns the optimal solution?
i refers to the start of the section we are reviewing, j refers to the end
in our two dimensional table, the first index refers to i value, second index refers to j value
subprobSols[i][j] refers to optimal solution to subproblem A[i…j]
subprobSols[0][n-1] refers to the optimal sol for A[0…n-1]
Dynamic Programming Longest Palindrome
In the bottom up first what are the first cases filled out?
subprobSols[0][0] = {0}
all the way through to:
subprobSols[n-1][n-1] = {n-1}
then look
0-1
1-2
…
0-2
1-3
…
What is the run speed of longest palin buttom up
Theta of n2
Dynamic Programming Longest Palindrome
What is the overlappin subproblems property
Dynamic Programming 0-1 knapsack
What is the speed?
O(nk)
n = num of items
k = capacity
Fast, as long as k into too large
if k is O(n2) then nk is O of (n3)
Dynamic Programming 0-1 knapsack
What are the base and recursive cases?
Base Cases:
- n == 1
- If n fits, put it in
- if n doesn’t fit return 0
recursive cases:
- if I[n][0] is > K then the answer is recursive(I,k,n-1)
- otherwise
- bestWithoutItemN = recursive(I,k,n-1);
- bestWithItemN = I[n][1] + recursive(i,k-I[n][0],n-1);
- return the max
Dynamic Programming 0-1 knapsack
How is the table set up?
What does i keep track of of?
What does j keep track of?
first index i keeps track of which item we are considering (starting at n down to 1)
second index j keeps track of the remaining capacity (starts at k, down to 0)
Dynamic Programming 0-1 knapsack
How do we decide what value to put in table entry?
Where is the answer located?
w(i,j) is exactly the value that we want to store in entry [i][j] of the table
The answer is in w(n,k)
we use the same formula:
w(i,j):
- if i =1
- it either fits (vi) or it doesn’t, 0
- i > 1
- si>j so the answer must be in w(i-1,j)
- si<=j so the answer is
- the bigger of the two w(i-1,j) or vi+w(i-1,j-si)
Dynamic Programming 0-1 knapsack
What is the table filling order, what are the base cases to fill in?
Fill the table in order
sol[0][0] is item 0 with cap 0
sol[0][1] is item 0 with cap 1
sol[1][0] best of so far with cap 0, etc
Dynamic Programming 0-1 knapsack
What is the speed of bottom up
Theta of (nk)
Dynamic Programming 0-1 knapsack
How would the solutions table be implemented (code)
capacity = k
we need a decision table that represents if that item is in the opt sol (true, false)
We use that table to build the rest.
for(int i = n-1; i>=0; i–){
if(decision[i][capacity] == true){
solution[i] = true;
capacity = capacity - I[i][0];
}else{
solution[i] = false;
}
What is the definition of Expectation of T?
Expectation of T is the sum of each probabiltiy mult by it’s lines of code.
What is a randomiszed algo?
An algorithm whose execution is determined in part by a source of random bits
In general what is the Las Vegas algo
It outputs an answer that is always correct
It’s run time depends on a randomness, but they most often run fast
What is the Monte Carlo algo?
Is an algo that always runs fast (it’s speed isn’t dependant on a random variable)
But the answer may not be correct, or may be close to correct.
What is Freivalds random algo for verifying matrix multiplications
- repeate M times
- choose an n x 1 binary matrix r uniformly at random:
- Each entry ri is 0 with probability 1/2 and 1 with prob 1/2
- Comput A*B*r, compute C*r, then check if they are equal
- If not equal immediately output C != AB and stop
- After m’th iteration output “yes, C=AB”
- choose an n x 1 binary matrix r uniformly at random:
Verifying Matrix mults
what is the run speed?
Divide and Conquer
What is merge sort’s divide, conquer and combine?
What is it’s formula and run speed?
Divide:
Partition A into two subarrays: A[0…n/2] and A[n/2+1…n-1]
Conquer:
Recursively sort each subarray using MergeSort
Combine:
Merge the two sorted subarrays into one sorted array, by repeatedly comparing the smalles from each subarray
Graphs:
What is the cost to brute force?
How fast is Prim’s?
How fast is Kruskals?
Brute : nn-2
Prim and Kruskal = O(ElogV)
Matrix Multiplication
What is the divide, conquer and combine for naive and Stressen’s?
What is the speed of naive, divide and conquer and Strassens?
Divide: Part A&B in 4 n/2-by-n/2 matrices
Conquer: recursively computer 8 matrix mults of size n/2-by-n/2
Combine: Use 4 matrix additions to computer the n/2-by-n/2 matries c11, c12,c21,c22
Base case: when A and B are 1-by-1 matrices, return A11B11
Matrix Mult
How are they multiplied?
Half-Plane Intersection
Given a convex polygon P and a half-plane h, the intersection is either:
What is the cost of half-plane brute force?
What is the divide, conquer and combine of half-plane?
Divide: Partition the set H into two sets H1 and H2 with equal size n/2
Conquer: Recursively compute the intersection of each set H1 and H2. This will return two convex polygons P1 and P2
Combine: Computer the intersection of P1 and P2
Base:cse single-half-plane, just return it
Whats the general idea of the half-plan intersection algo?
Advance P or Q?
What is the speed and formula for Half-Plane?
What is proof for greedy choice property with the coins?
What is needed for Dynamic Programming to be a good candidate for a solution?
