PS5-4. A Hamiltonian path in an undirected graph G is defined to be a path that includes every vertex of G. Given as input an adjacency list of an n-vertex graph G and two distinct vertices s, t = V(G), we'd like to determine whether G has an s-to-t Hamiltonian path. This is a famous example of a computationally hard problem (the formal term is "NP-hard"; see CS 39). Therefore, we don't expect to find a polynomial time algorithm for this problem. However, that doesn't preclude being clever, as you'll now see. In this problem, we'll use poly(n) to denote a function of n that grows at most polynomially. Formally, "f (n) = poly(n)" means no, kN Vnno: f(n) nk. a. Does there exist a constant a such that n! = O(a") poly(n)? Prove your answer. b. A brute-force algorithm to solve the given problem is to try out all permutations of V(G) - {s, t} and, for each such permutation, check whether it gives us the desired Hamiltonian path. Analyze the running time of this algorithm and express it in the form g(n) poly(n) for some function g(n). Hint: It's going to involve a factorial. c. Use divide-and-conquer to give a better algorithm for this problem that runs in time O((4.001)"). Hint: You may use without proof the fact that == m The natural big-O recurrence for your algorithm will have a form that the Master Theorem can't handle. However, it will be simple enough to iterate the recurrence and find a pattern, leading to a solution. [10 points]