CS 325 Final Review Questions and [UPDATED] Solutions The Final (1 hour 50 min) is comprehensive, with a focus on the portion after Midterm. Special focus on the connections among DP, priority queues, and graph problems (such as shortest/longest-path). There will be a short fill-in-the-blanks question (DP), similar to HW8, HW9, or HW10. 1. What's the practical relevance of k-best solutions in DP? A: k-best optimization is used in everyday life because you always want alternative choices! Think about Google Map, which (a long time ago) used to present a single path for directions, but now presents alternative paths (shortest vs. fastest, etc.). A user sometimes prefers to avoid freeway, ferry, etc., and often the user's objective function is multi-dimensional (time, distance, traffic, etc.) so s/he would benefit from multiple choices. 2. For a DAG, how to get k-shortest paths using Viterbi? (cf. hw10 RNA k-best) A: each vertex stores k-shortest paths from the source. the update operation becomes merging sorted lists, but only need top k out of them. time: O(E + V k log k). Note: this is not the fastest, but very easy to implement. 3. How to decide whether a graph has a *unique* topological order? Hint: a small change in the bottom-up (or top-down) code. [UPDATE] A: in each iteration, before choosing one node from the zero-in-degree list (either a stack or a queue), check if that list is a singleton. 4. Give a DAG where Dijkstra fails. A: Example (negative edge): V = {S, V_1, T}; E = { S -> V_1: 3 S -> T: 2 V_1 -> T: -2 } 5. Dijkstra's algorithm doesn't work if there are negative weight edges. One proposal for how to deal with this case, is to find the most negative edge, say with value -v, add v to the cost of every edge, so that each edge is non-negative, and solve the shortest path algorithm in the resulting graph. Does this work? If not, give a counterexample. [UPDATE] A: No. See the example from the previous question. 6. (from KT slides) Suppose that you change the length of every edge of G as follows. For which is every shortest path in G a shortest path in ?? A. Add 17. B. Multiply by 17. C. Either A or B. D. Neither A nor B. [UPDATE]: A: B only. 7. What's the time complexity of Dijkstra if you use the following implementations of priority queue? (a) heap (does not support decrease_key) (b) heapdict (supports decrease_key) (c) hash (d) unsorted array A: (a) (E+E) log E (b) (V+E) log V (c) V^2 + E (d) V^2 + EV Note: (c) is faster than (a-b) for dense graphs, but since big dense graphs are extremely rare in practice, the default implementation is either (a) or (b). (a) is (E+E)logE not (V+E)logE b/c in the worst case you pop E times and only V of them are unique pops. 8. (from CLRS) Dijkstra with integer weights: suppose all edge weights are in {1..W} where W is a positive integer but not a const. Modify priority queue data structure to achieve O(VW+E) time. (hint: no heap). A: Similar to bucket-sort, your priority queue is actually (V-1)W+1 buckets (0, 1, ..., (V-1)W). Vertex with key k is in the bucket k. Scan these buckets from left to right, and pop one vertex from the first non-empty bucket. 9. (from CLRS) Weird shortest path: find the path whose longest edge is the shortest. motivation: My car has a small tank, and gas stations are only found in cities. To be safe, I don't wanna travel long distance between two cities. O(V+E) (just modify Viterbi) O((V+E)logV) (modify Dijkstra => similar to Prim) -- not required for final. Follow-up: How about the path whose shortest edge is the longest? A: [UPDATED with details] O(V+E): from Viterbi solution for longest-path (hw8), change the two operators from (max, sum) to (min, max). (min, max): for each node u in the topological order: take the min among all incoming edges (v, u), but take the max when you extend d(v): d(u) = min_{v: (v,u) in E} max(d(v), c(v,u)) compare it with hw8 (viterbi for longest) d(u) = max_{v: (v, u) in E} (d(v) + c(v,u)) O((V+E)logV): in Dijkstra's priority queue, change the key of node v from "(shortest) distance from source to node v" to "(shortest) longest edge from source to node v". i.e., when you pop node u and use it to update node v along edge (u,v): d(v) min= max(d(u), c(u, v)) compare it with hw9 (dijkstra for shortest): d(v) min= d(u) + c(u, v) Recall that "min=" is like "+=", i.e., a min= b means a = min(a, b). For "whose shortest edge is the longest": Viterbi: change to (max, min) Dijkstra: change the edge weight e_ij to max_e - e_ij, then the question is same as "longest edge is the shortest". -- not required for final. 10. Which DP problems in this course can be solved by *both* Viterbi and Dijkstra? A: So far, only the coins problem. Another classical example would be edit-distance (found in numerous textbooks and resources, see below). follow-up: which algorithm is faster for coins? A: Dijkstra (actually coins doesn't even need Dijkstra -- a simple BFS will do). BFS can be viewed as simplified Dijkstra where the priority queue is just a normal queue. Dijkstra can be viewed as fancy BFS where the queue becomes priority queue. 11. Given a boolean expression, count the number of parenthesizations that return T. e.g., input: F + F * T output: 0. reason: impossible input: T + F * T output: 2. reason: (T+(F*T)) ((T+F)*T) O(n^3) or better. A: Use the gaps between two T/F as index, from 0 to n. true[i][i+1] = 1 if e[i] is T else 0 false[i][i+1] = 1 if e[i] is F else 0 true[i][j] = sum( true[i][k] * true[k][j], if o[k] is *; true[i][k] * true[k][j] + true[i][k] * false[k][j] + false[i][k] * true[k][j], if o[k] is +; ) for i (i-1,j) | \ | 1| \0 or 1 |1 | \ | v \ v (i, j-1) --1-> (i, j) final: opt[n, m] where n = |s| and m = |t| space: O(n*m) time: same graph or hypergraph: graph, find shortest-path from (0,0) to (n, m) Because it's a shortest-path problem with non-negative weights (0 or 1), and because the graph is a DAG, this problem can be solved by both Viterbi or Dijkstra and the latter could be faster if the final edit distance is small. Example: s = a-cdefh |-||+|* t = abcd-fg t= a b c d f g i/j| 0 1 2 3 4 5 6 ------------------------------- s 0 | 0 1 2 3 4 5 6 || | \ +1 a 1 | 1 0---1 2 3 4 5 | \ c 2 | 2 1 1 1 2 3 4 | \ d 3 | 3 2 2 2 1 2 3 | |+1 e 4 | 4 3 3 3 2 2 3 | \ f 5 | 5 4 4 4 3 2 3 | \+1 h 6 | 6 5 5 5 4 3 3 ------------------------------- When edit distance is small (mostly diagonal copying), then Dijkstra is faster: (I've implemented both: distance1() is Viterbi, and distance2() is Dijkstra) In [40]: %time distance1("aaaaaaadaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaa") CPU times: user 12.7 ms, sys: 17 us, total: 12.7 ms Wall time: 12 ms Out[40]: 5 In [41]: %time distance2("aaaaaaadaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaa") CPU times: user 6.59 ms, sys: 1.96 ms, total: 8.55 ms Wall time: 7.55 ms Out[41]: 5 Otherwise Viterbi is faster.