6. (15 points) Suppose that you are given a directed graph G = (V, E) along with weights on the edges (you can assume that they are all positive). You are also given a vertex s and a tree T connecting the graph G that is claimed to be the tree of shortest paths from s that you would get using Dijkstra's algorithm. Can you check that T is correct in linear time? 7. (0 points, optional)? This exercise is based on the 2SAT problem. The input to 2SAT is a logical expression of a specific form: it is the conjunction (AND) of a set of clauses, where each clause is the disjunction (OR) of two literals. (A literal is either a Boolean variable or the negation of a Boolean variable.) For example, the following expression is an instance of 2SAT: (11 V 12) (II V 13) ^ (11 V 22) ^ (14 V 13) ^ (14 V TI). A solution to an instance of a 2SAT formula is an assignment of the variables to the values T (true) and F (false) so that all the clauses are satisfied, that is, there is at least one true literal in each clause. For example, the assingment 11 = T, 12 = F, 13 = F, 14 = T satisfies the 2SAT formula above. Derive an algorithm that either finds a solution to a 2SAT formula, or returns that no solution exists. Carefully give a complete description of the entire algorithm and the running time. (Hint: Reduce to an appropriate problem. It may help to consider the following directed graph, given a formula I in 2SAT: the nodes of the graph are all the variables appearing in I, and their negations. For each clause (a v B) in 1, we add a directed edge from a to B and a second directed edge from B to a. How can this be interpreted?) 8. (0 points, optional)? Give a complete proof that log(n!) is (n log n). Hint: you should look for ways to bound (n!). Fairly loose bounds will suffice