\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2010}{17 November 2010}{15}           

\begin{center}
\Large{\bf POW 8--10}
\end{center}

{\bf 8. Using up all Scrabble letters}

You have a set of $n$ letter tiles, each tile having exactly one
letter of the English alphabet.  (Each letter may appear multiple
times; thus you may have 5 of As, 2 of Bs, 7 of Cs, etc.)  You also
have a limited vocabulary of $m$ English words.  You want to determine
whether you can make a collection of English words that use up all of
the letter tiles, with each tile appearing exactly once in this
collection, and each word coming from your vocabulary of $m$ words.
(A word may appear multiple times in your collection.)

Show that this problem is NP-complete.

{\bf 9. Efficiently solvable 3-SAT instances}

Consider the class of 3-SAT instances in which each of the $n$
variables occurs in exactly 3 clauses (counting both positive and
negated occurrences).  Show that such 3-SAT instances are always
satisfiable and a satisfying assignment can be solved in polynomial
time.

{\bf 10. Random walk on a directed graph}

Consider the directed graph $G$ over the vertex set $V =
\{0,1,\ldots,n\}$ and edge set given by
\[
\{(i,i+1) : i < n\} \cup \{(i,0): i \le n\} \cup \{(n,n)\}.
\]
Compute the Markov chain corresponding to the standard random walk and
calculate its stationary distribution.  Compare with the stationary
distribution one would get on the graph obtained by making all of the
above edges undirected.
\end{document}