%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\midterm}[2]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{0}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
\hfill Winter 2018} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Final \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Out: #1 \hfill Due: #2} }
\vspace{2mm}}
}
\end{center}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\newcommand{\set}[1]{\left \{{#1} \right \}}
\begin{document}
\midterm{March 7}{\bf {March 14, noon}}
{\bf This is the final exam.} You may consult only the course
notes and text (Sipser). You may not collaborate. There are 5 problems on two pages. Please attempt
all problems. {\bf To facilitate grading, please turn in each
problem on a separate sheet of paper and put your name on each
sheet. Do not staple the separate sheets.} Good luck!
\medskip
{\bf Instructions for turning in the exam:} Please turn in your
exams to Diane Goodfellow in Annenberg 246 before noon on Wednesday
March 14.
\begin{enumerate}
\item Consider the following 2-person game. The game is played on
an $n \times n$ ``board'' with nonnegative integers in each of the
$n^2$ cells. There is a specified ``target'' value $B$ which is
also a nonnegative integer. The players take turns selecting
integers from successive rows: player one selects an integer in
row 1, then player two selects an integer in row 2, then player
one selects an integer in row 3, etc... After an integer has been
selected from the last row, the game ends. If the sum of all of
the selected integers equals $B$, then player 1 wins; otherwise
player 2 wins.
Given a game board (a square matrix $M$ of nonnegative integers)
and a nonnegative integer $B$, we can ask whether there is a win
for player one (i.e., player one can win no matter what player two
does). Prove that the language $L$ consisting of pairs $\langle M,
B \rangle$ for which there is a win for player one is
PSPACE-complete. In other words prove:
\begin{enumerate}
\item $L$ is in PSPACE, and
\item $L$ is PSPACE-hard. Here it may be useful to recall the
two-player game interpretation of QSAT from Lectures 23-24.
\end{enumerate}
\item Let $L$ be the language over the alphabet $\Sigma = \set{a,b,c}$ consisting of exactly those strings with an {\em unequal} number of $a$'s and $b$'s (and any number of $c$'s). Is $L$ (i) regular, (ii) context-free but not regular, or (iii) not context free? Prove that your classification is correct.
\item For a language $L \subseteq \Sigma^*$ and a string $y \in
\Sigma^*$, the language
\[L_{-y} = \set{xz : x \in \Sigma^* \mbox{ and } z \in \Sigma^* \mbox{ and } xyz \in L}\]
consists of all strings in $L$ with the string $y$ deleted from
them.
\begin{enumerate}
\item Prove that if $L$ is regular, then $L_{-y}$
is regular. Hint: make $|y|+1$ copies of a DFA recognizing $L$.
\item Prove that if $L$ is R.E., then $L_{-y}$ is R.E.
\end{enumerate}
\item Is the following statement true or false? Give a complete proof of your assertion.
``If for some fixed $k$, an NP-complete language has an
$O(n^k)$-time algorithm, then every language in NP has an
$O(n^k)$-time algorithm.''
\item Each of the following languages is either
in P, or it is NP-complete. {\bf Choose 4 out of the 5 problems, and for each one, prove that it is NP-complete, or prove that it is in P. Please indicate clearly which 4 you are choosing, and provide solutions for only those 4.}
For two of the problems below, you will need to recall that in a graph, the {\em degree} of a vertex $v$, denoted $d(v)$, is the number of edges that touch that vertex; the {\em maximum degree} of a graph is the maximum, over vertices $v$, of $d(v)$.
\begin{enumerate}
\item This problem is a variant of {\sc independent set} in
bounded-degree graphs. The language in question is the set of all pairs $(G, k)$ for which $G$ is a graph with maximum degree at most 4 containing an independent set of size at least $k$.
\item This problem is a variant of {\sc undirected hamilton path} in bounded-degree
graphs. The language in question is the set of all triples $(G, s, t)$
for which $G$ is an undirected graph with maximum degree at most 2 containing a Hamilton path from node $s$ to node $t$.
\item Given a universe $U$ and a collection of subsets ${\cal C} =
\{S_1, S_2, S_3, \ldots, S_n\}$, with each $S_i \subseteq U$, we
say that a subset $H \subseteq U$ is a {\em hitting set} if each
$S_i$ contains at least one element of $H$. In this problem we are
interested in the case in which each $S_i$ has size at most $2$.
The language in question is
\begin{eqnarray*} \mbox{{\sc hitting
set-2}} = \{({\cal C}, k) & : & \mbox{for all $S_i \in {\cal C}$,
$|S_i| \le 2$, and}\\
& & \mbox{there is a hitting set $H \subseteq U$ with $|H| \le
k$}\}.
\end{eqnarray*}
\item The language consisting of 2-CNF formulas $\phi$ for which there exists an assignment that satisfies at least $3/4$ of the first $1000$ clauses, and all of the other clauses.
\item The language consisting of 2-CNF formulas $\phi$ for which there exists an assignment that satisfies all of the first $1000$ clauses, and at least $3/4$ of the other clauses.
\end{enumerate}
\end{enumerate}
\end{document}