Exam 1 Prep Flashcards
How do you identify a (LIS) Longest Increasing Subsequence problem?
- The problem only has one array
- The problem is comparing to itself (the array I guess?)
- The problem only looks back one item at a time (no window, no knapsack)
At a high level, how do you solve a LIS (Longest Increasing Subsequence) problem?
- Normally only requires a 1D table
Two variations:
O(n) lookback:
- You need to check all previous elements, or all previous element < or > some requirement
- Results in O(n^2) overall
O(1) lookback:
- You need to check only one element back
- Or some fixed number of items back
- Your restriction moves forward with i (?)
- You need to carry a max, sum, count, etc. forward (only have to compare against last element)
- Results in O(n) overall
How do you identify an LCS problem? (Longest Common Substring OR Subsequence?)
- The problem requires comparison between two arrays
- Problem is looking for something in common
Substring: Matches need to be consecutive
Subsequence: Matches don’t need to be consecutive
How do you solve an LCS (Longest Common SUBSTRING) problem?
- Normally requires a 2D table
- Add 1 or whatever if the comparison succeeds
- Reset to zero when comparison fails
- 1 + T(i-1, j-1)
- Solution is max of T
- Runtime is O(n*m) (or O(n^2) if arrays are the same length)
How do you solve an LCS (Longest Common SUBSEQUENCE) problem?
- Add 1 or whatever if the comparison succeeds
- Take max of either side if comparison fails, i.e., max{T(i, j-1), T(i-1, j)}
- Solution is the result in the bottom right of table, T(n, m)
- Runtime is O(n*m) (or O(n^2) if arrays are the same length)
How do you identify an Edit Distance problem?
(Very similar to LCS)
- The problem compares two arrays
- Requires you to minimize the difference
- Penalizes differences, rewards matches
- Requires aligning the arrays
How do you solve an Edit Distance problem?
- Usually a 2D table
- Declare a function like diff(i,j) to compute the penalty/reward of aligning i and j
- i and j have three possible alignments, i=j, i=j-1, or j=i-1
- Two loops over i and j, T(i, j) = min or max of
{T(i-1, j-1) + diff(i, j); T(i-1, j) + diff(i, -); T(i, j-1) + diff(-, j} - i.e., you want the min or max over diagonal to the left, up, or left. Plus whatever diff() does.
- Runtime is O(n*m)
How do you identify a Knapsack problem?
- Problem needs to check if something can fit, or can add up to X
- Problem wants to maximize value given a specific budget
- Problem wants the minimum budget to achieve a given value
How do you solve a knapsack problem? (limited items)
- Usually a 2D table
- Iterate over b = 1 -> budget B
- Iterate over the items
- In that double for loop check if item can fit (w[i] < b)
- if it fits: check if you get more with budget b but excluding item i or reducing budget b by the weight of i, making room for it, then adding item i
- i.e., T(b, i) = max{T(b, i-1), T(b-w[i], i-1) + v[i]}
- if it doesn’t fit: just carry the last value forward for budget b and move on
- i.e., T(b, i) = T(b, i-1)
- Runtime is O(Bn)
How do you solve a knapsack problem? (unlimited items)
- Usually a 1D table where we just iterate over budgets, but can be expressed in 2D with when we also iterate over the items, though it’s unnecessary
- Iterate over b = 1-> budget B
- Set T[b] = 0
- if item can fit, i.e., w[i] <= b
- then T[b] = max{T[b], v[i] + T[b-w[i]]}
- if item can’t fit, i.e., w[i] > b
- do nothing!
- Run time is O(nB)
How do you identify a windowing-only problem?
- It requires that you optimize something by considering different subarrays or subsequences
How do you identify a “windowing and break at midpoint” problem?
- It asks you to find the optimal way to split an array and optimize some criteria based on the split
Ex: Chain Matrix Multiply. Basically asks how do you parenthesize the matrix multiplication to minimize the number of element multiplications.
How do you solve a windowing-only problem?
- Usually a 2D table
- Iterate over window sizes s = 1->n
- iterate i = 1->n-s
- Set j = i + s
- Compute T[i, j] using smaller windows between i and j
- This is possible because window size grows, so you already have the small windows computed
- Runtime is O(n^2)
How do you solve a “windowing and break at midpoint” problem?
- Usually a 2D table
- Iterate over window sizes s = 1 -> n
- Iterate over i = 1 -> n
- Set j = i + s
- Iterate over possible breaks k = i+1 -> j-1
- Set choose T[i, j] to the best value given all possible choice of k. You will be building on smaller windows for this.
- Runtime is O(n^3)
What are the properties of Bellman-Ford? i.e.,
- What can it solve?
- What are the requirements?
- What can it not solve?
- What are the runtimes?
What can it solve?
- Single source shortest paths, i.e., for some source node it finds the distance from the source to every other node. Output is an array
- Can tell if there is a negative weight cycle on that ONE path
What are the requirements?
- A directed graph and weight edges (undirected graph can be converted to directed with antiparallel edges)
- No negative weight cycles (we can detect one, but after that we can’t solve for a shortest path)
What can it not solve?
- all-paths
- Can’t find all negative weight cycles, only those reachable from source node
What is the runtime?
- O(n*m) where n = |V| and m = |E|
