Mini #3, 15451 Fall 2013 ======================== This mini is due using *autolab* by 11:59pm Tuesday October 1. NEW RULE: TEXT OR PDF FILES ONLY. (DOES YOUR FILE NOT HAVE EXTENSION .TXT or .PDF? PLEASE DO NOT SUBMIT IT.) One attempt only. If you goof up please check Piazza, and/or contact your TA. ------------------------------------------------------------------ 1. a. Run DFS on the graph below, outputting the pre and post numbers for each vertex. For concreteness, assume the outer "DFS-Graph" while-loop examines nodes in alphabetical order, and similarly that the inner DFS(v) for-loop examines neighbors in alphabetical order. A------->B-------->C------->D | ^ | ^ | | | | | | | | | | | | v | v | H------->G-------->F------->E b. What topological ordering of the vertices is output by the algorithm? 2. Run DFS on the graph below, using the same tie-breaking rules as above. Use Kosaraju's algorithm to output the resulting strongly connected components of G. A------->B--->L<---C------->D | ^ | ^ ^ v | v | | J------->K M--->N------->O | | ^ | v v | v H<-------G-------->F<-------E 3. The LONGEST-INCREASING-SUBSEQUENCE problem is: given an array A of n integers like [7 2 5 3 4 6 9], find the longest subsequence that's in increasing order (in this case, it would be "2 3 4 6 9"). Give a dynamic-programming algorithm that runs in time O(n^2) to solve this problem. To keep things simple, let's say you just need to output the *length* of the longest-increasing subsequence. E.g., in the above case, the length was 5. Hint: suppose that for each i' < i you have computed the length of the LIS of A[0]...A[i'] that ends with A[i']. How would you use this to solve the corresponding problem for i?