Problem 0: Review Homeworks #4 through #6 and relevant exercises from the textbook, especially solved exercises.

Problem : Devise an $O(2^n \cdot n^2)$ dynamic programming algorithm for the Travelling Salesperson problem.

Problem : Ch. 5, Exercise 1

Problem : Write a recurrence for the running time of the following algorithm and find a tight asymptotic (Θ) bound on the solution assuming that

• a) tinker runs in Θ(n) time and
• b) tinker runs in Θ(n²) time.

int twiddle(List L)
  if (L.size() <= 2)
    return foo(L); // assume this runs in O(1) time
  else
    L1 = twiddle(L.subList(1, L.size() / 2)
    L2 = twiddle(L.subList(L.size()/4, 3*L.size()/4)
    L3 = twiddle(L.subList(L.size()/2, L.size())
  return tinker(L1, L2, L3) // returns a list of size n

Problem : You are distributing leftover kits from meal kit delivery companies to local residents with mobility problems. Each of the $n$ delivery companies specializes in a particular distinct type of food (vegetarian, vegan, pesceterian, kosher, halal, ...) and the residents can be grouped into $k$ classes determined by dietary restrictions. Each class may be compatible with multiple specialties (e.g. vegeterians can eat vegan). Devise an algorithm that runs in time polynomial in $n$ and $k$ that, given the number of meals supplied by each service $m_1, \ldots, m_n$ and the number of residents in each class of dietary restrictions $r_1, \ldots, r_k$, determines if you can deliver each resident a meal that is compatible with their dietary restrictions.

Problem : Consider the maximum flow problem without the restriction that at most one of $(u, v)$ and $(v, u)$ is present in the graph. A flow $f$ may then have non-zero flow on both $(u, v)$ and $(v, u)$. Show that $f'$ defined by $f'(u, v) = \max(0, f(u, v) - f(v, u))$ is also a flow and that $v(f') = v(f)$.

Problem :

• For each of CYCLIC (given $G$, does it contain a cycle), VERTEX-COVER, and QSAT, state whether it is known to have the following properties, known not to have them, or whether it is currently unknown whether they have them.
  • in $P$
  • in $NP$
  • in co-$NP$
  • $NP$-complete
  • in $PSPACE$
• Repeat under the assumption that $QSAT \in P$.

Problem : ALMOST-HP is the problem of, given an undirected, connected graph with $n$ vertices, determining if that graph has a simple path that visits at least $n-1$ vertices. Give a complete proof that ALMOST-HP is NP-complete. You may assume that UNDIRECTED-HAMILTONIAN-PATH is NP-complete.

Problem : Show that if the decision problem UNDIRECTED-HAMILTONIAN-PATH is solvable in polynomial time then so is FIND-UNDIRECTED-HAMILTONIAN-PATH (the problem of, given an undirected graph $G$, finding a Hamiltonian path in $G$ if one exists).

---