CS 325 Final Review Questions and 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. 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. 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. 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(VlogV + E) (modify Dijkstra => similar to Prim) -- not required for final. Follow-up: How about the path whose shortest edge is the longest? A: O(V+E): change two operators (max, sum) to (min, max). O(VlogV+E): change the key of node v from "(shortest) distance from source to node v" to "(shortest) longest edge from source to node v". 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. 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