Lesson 2

Advanced Problems.

1. (20 points) Describe an algorithm that outputs all permutations on \(n\) items, such that any two consecutive permutations differ in exactly one swap of two adjacent elements. The running time should be \(n^{O(1)}\cdot n!\).
2. (20 points) Write an iterative function (without recursion) that generates all \(2^{n}\) subsets of \(\{0, \dotsc, n-1\}\) in Gray code order (i.e., each successive subset differs from the previous one by the addition or removal of exactly one element).
3. (20 points) A maximal clique in a graph \(G=(V, E)\) is a subset of vertices \(S \subseteq V\) such that the subgraph induced by \(S\), \(G[S]\), is a clique, and \(S\) is not a proper subset of any other clique.

   Prove that the number of maximal cliques in a graph with \(n\) vertices does not exceed \(3^{n/3}\).

   Hint:

   Try to construct a recursive procedure that finds all maximal cliques.
4. (25 points) Given a directed graph \(G = (V, E)\), construct an algorithm that checks whether there is a Hamiltonian path in \(G\) in time \(n^{O(1)}\cdot 2^{n}\) and space \(n^{O(1)}\).
   Hint:

   The core idea is to reduce the problem of determining whether a graph has a Hamiltonian path to the harder problem of counting the number of Hamiltonian paths.

   Recall that a walk in a graph is defined as any finite sequence of vertices \((v_{1}, v_{2}, …, v_{t})\) such that each pair \((v_{i}, v_{i+1})\) forms an edge in the graph. A walk of length \(t\) is called a \(t\)-walk. The key distinction between a walk and a path is that a walk may visit the same vertex multiple times, while a path may not. Try to express the number of Hamiltonian Paths in terms of \(n\)-walks.

5. (30 points) Gray code is a Hamiltonian path on the Boolean cube. Consider the following graph: let \(G_{n,k}\) be the graph whose vertices are the \(k\)-element subsets of the set \([n]\). Two vertices (subsets) \(A\) and \(B\) are connected by an edge if \(|A \cap B| = k-1\). This is equivalent to stating that \(B\) can be obtained from \(A\) by exchanging a single element \(x \in A \setminus B\) for a single element \(y \in B \setminus A\).

   Show that \(G_{n,k}\) has a Hamiltonian path between any pair of vertices (for all \(n \ge 1\) and \(0 \le k \leq n\)).