FINAL - short answer/equations Flashcards
Get an A+ on the final exam!!
Greedy choice property
The (a) greedy choice is contained in a globally optimal solution
Optimal substructure property
A globally optimal solution contains globally optimal solutions to its subproblems
Cardinality
The number of elements in a set
7 steps to solve a DP problem
- Define variables, 2. Express final numeric answer using variables, 3. Recurrence relation between the variables, 4. Dependency graph, 5. Figure out the order to solve the subproblems, 6. Pseudocode, 7. Reconstruct an actual optimal solution
What form does the recurrence have to take to use Master Theorem?
For Master Theorem, what is the level cost?
For Master Theorem, what is the # base cases?
For Master Theorem, what is the # levels?
For Master Theorem Case 1, what condition must be met?
Level cost is polynomially SMALLER than # base cases
What is the running time T(n) for Master Theorem Case 1 (level cost is poly SMALLER than # base cases)?
For Master Theorem Case 3, what condition must be met?
Level cost is polynomially LARGER than # base cases
For Master Theorem Case 3, what extra condition must be met?
What is the running time T(n) for Master Theorem Case 3 (Level cost is polynomially LARGER than # base cases)?
For Master Theorem Case 2, what condition must be met?
Level cost is in Big-Theta(# base cases)
For Master Theorem Case 2, what is the runtime T(n)?
What summation is this equation true for?
A BFS Tree is also…
The single source shortest path tree (where the weight of each edge is 1)
Tree edge (BFS)
An edge from a gray to a white node, where the white node is first being discovered (also called discovery edges)
BFS Applications
- Test if G is connected
- Compute a spanning tree of G
- Compute the connected components of G
- Compute the shortest path/distance between s and each vertex v in G
Parenthesis Lemma
- u is an ancestor of v iff [d[u], f[u]] SUPERSET OF [d[v], f[v]]
- u is a descendant of v iff [d[u], f[u]] SUBSET OF [d[v], f[v]]
- u and v are not related iff [d[u], f[u]] and [d[v], f[v]] are disjoint
What is a topological sort (of a DAG)?
A LINEAR ORDERING of all vertices in G such that vertex u comes before vertex v if (u, v) is in G. Topological sort creates a PARTIAL ordering (since multiple valid orders may exist)
For Prim’s algorithm, what is the key data structure?
A priority queue (min-heap) that is used to determine which node/edge to add to the tree next
For Dijkstra’s algorithm, what is the key difference from Prim and Kruskal?
Dijkstra’s algorithm uses a priority queue (like Prim) but uses the shortest distance to the root node as the key value for the PQ.
To compare (lg n)^100 vs. (lg n)^(lg n), what is a technique you can use?
Let m = lg n. Then you can easily compare m^100 vs m^m
ith order statistic of n elements is…
the ith smallest element
How do you reconstruct the LCS solution (qualitatively looking at the table)?
Take the letter listed on the side(s) when the arrow goes diagonally out of that letter’s box!
For US coinage problem, what approach do we use?
It can be solved with a greedy algorithm (unlike the general making change problem), and the greedy choice is to select the largest coin possible without exceeding the remaining amount
What problem does Huffman encoding solve?
If we know the frequencies of characters in our alphabet, Huffman encoding can generate the optimal binary prefix-free encoding (such that the most frequently used characters have the shortest encoding).
How does Huffman encoding work?
Sort all characters from lowest to highest frequency. Take the lowest two and combine them under a new node that contains the sum of their frequencies. Insert this composite node back into the list, resort, and repeat. You end up with a binary tree, and the encoding for any character can be found by assigning 0 to left branches and 1 to right branches as you traverse the path from the root node to that character.
For L, root, R, what is inorder?
L, root, R
For L, root, R, what is preorder?
root, L, R
For L, root, R, what is postorder?
L, R, root
How do you implement topological sort?
Run DFS on the graph. As each vertex is finished, insert it at the FRONT of a linked list. Return this list when done, which contains the topological sorted nodes
To find the maximum element of a strictly concave array (array strictly goes up then strictly goes down), what is the essence of the algorithm we discussed?
Compare the middle two (adjacent) elements. Since they are ADJACENT, you can properly determine if you are going up or down (since the strict ordering actually applies for adjacent elements!). Based on that, search either the left or right halves of the array
For the Max subarray problem (DP), what is the definition of the main variable/answer?
maxSumEndAt[i] is the maximum sum of a contiguous subarray ENDING at index i (it can start anywhere!). The answer is: max (from i=1 to n) { maxSumEndAt[i] }
For knapsack problem, what is the definition (not recurrence) of V[i, j]? What does it mean?
V[i, j] is the optimal solution considering only the first i items and capacity j knapsack
What is the current view of P, NP, and NPC? (venn diagram)
What is P?
The set of problems solvable in polynomial time
What is NP?
The set of problems verifiable in polynomial time
What is NPC?
The set of problems in NP and as hard as any other problem in NP
What is NPH?
Problems that are as hard as any other problem in NP (hasn’t necessarily been shown that these problems are in NP themselves)
How to prove that a problem Y is NPC?
Show that:
- It is in NP
- Another NPC problem Yn is no harder than Y (Yn <=p Y)
What kind of problems are NPC?
Decision problems (Y/N answers)
T(n) = 2T(n/2) + Theta(n)
T(n) = Theta(n lg n)
T(n) = T(n/3) + T(2n/3) + Theta(n)
T(n) = Theta(n lg n)
T(n) = 3T(n/2) + Theta(n)
T(n) = Theta(n^lg 3)
T(n) = T(n/5) + T(7n/10) + Theta(n)
T(n) = Theta(n)
If the recursion coeffecients sum to 1, we get…
Theta(n lg n)
If the recursion coefficients sum to > 1, we end up with…
something > n lg n
If our recursion coefficients sum to < 1, we end up with…
Theta(n)
What is the general approach for unbalanced recursion trees?
Find T(n) >= something based on shorter side, find T(n) <= something based on longer side, then make a bound from that
