Lesson 1

Basic Problems.

1. (10 points) Design an algorithm that, for given \(n, k \in \mathbb{Z}_{\ge 1}\), outputs, in time \(O(k \cdot n^{k})\), all \(k\)-sequences over \([n]\) such that any two consecutive sequences differ in one position and the values in that position differ by exactly one.

   For example, for \(n=3, k=2\), the following is such an order: \[11 \quad 12 \quad 13 \quad 23 \quad 22 \quad 21 \quad 31 \quad 32 \quad 33.\] This way, such sequences generalize Gray codes for larger alphabets, though in this case we don't require anything for the last and the first elements of the sequence.

   Hint:

   Consider a recursive approach. How might one construct the required sequence for length \(k\) by utilizing the sequence generated for length \(k-1\)?
2. (10 points) For a given integer partition \(\lambda = (\lambda_{1}, \lambda_{2}, …, \lambda_{k})\) of \(n\) (with \(\lambda_{1} \geq \lambda_{2} \geq … \geq \lambda_{k} > 0\)), the corresponding Young diagram is a collection of \(n\) cells arranged in \(k\) left-justified rows, where row \(i\) has \(\lambda_{i}\) cells. A Standard Young Tableau (SYT) is a filling of the cells of this diagram with the integers \([n]\) such that the values increase along each row and down each column.

   Given an integer \(n\) and a partition \(\lambda\) of \(n\), describe an algorithm which generates all Standard Young Tableaux of shape \(\lambda\).

   For \(\lambda = (3,2,1)\), the SYT is shown below. \[\vcenter{\hbox{\begin{tabular} {c c c}1 & 3 & 6 \\ 2 & 5 & \\ 4 & & \end{tabular}}}\]

3. (15 points) Design a linear time algorithm that takes a sequence of brackets and outputs the longest valid bracket substring.
4. (15 points) Design a linear time algorithm that, given a permutation of \([n]\), outputs the lexicographically next permutation.
5. (15 points) By \(k\)-bit Gray code we mean the Gray code for binary strings of length \(k\). Consider the \(2\)-bit Gray code \(00\to 01\to11\to10\), then each digit changes twice (note that we're always assuming the final item loops back to the first).

   A Gray code is called balanced if each digit changes the same number of times in a full cycle. The 2-bit Gray code above is balanced. Do there exist \(3\)- and \(4\)-bit balanced Gray codes?

6. (15 points) Given an algorithm that counts the number of Hamiltonian paths in directed graphs in time \(T(n)\), construct an algorithm that finds some Hamiltonian path in time \(n^{O(1)}\cdot T(n)\).
   Hint:

   Consider a specific vertex \(s\) and a neighbor \(v\). Can you use the counter to determine whether there exists at least one Hamiltonian path that starts with the edge \((s, v)\)?
7. (15 points) In the Subset Sum problem, one is given a set of \(n\) integers and seeks to determine whether there exists a (nonempty) subset whose elements sum to zero. Design an algorithm for this problem with a running time of \(n^{O(1)}\cdot 2^{n / 2}\).