1. Draw an instance of convex hull problem with 6 points, such that if Graham-Scan algorithm runs on this instance, the sequence of stack operations is (push, push, push, push, pop, pop, push, pop, push). 2. Let G = (V,E) be a directed graph, and (u,v) E E be an edge of G. During a run of DFS on G, the [pre, post] interval for u and v are [4,7] and [2,9), respectively. Is it possible that G is a DAG? Either give an example to show that this is possible, to prove that this is not possible. %3D 3. Below are the pre- and post-numbers of vertices a,b,c,d,e in a run of DFS on a directed graph (there are other vertices in the graph that are not shown). One of the vertices has incorrect pre-/post-numbers. Indicate which one is incorrect and explain why. vertex pre-number | post-number 21 a 10 b 18 25 17 30 d 12 15 11 16