%\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 2019} }
\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 13}{\bf {March 20, 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 Please turn in your solutions via
Gradescope, by noon on the due date.}
Good luck!
\medskip
\begin{enumerate}
\item Consider the following 2-person game. The game is played on
an $n \times n$ ``board'' with integers in each of the
$n^2$ cells. 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 zero, then player 1 wins; otherwise
player 2 wins.
Given a game board (a square matrix $M$ of integers)
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 those $M$ 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 Lecture 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 one 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 3-coloring} in which the graph
is a forest (i.e., contains no cycles). The language in question is
the set of all forests $G$ for
which $G$ is 3-colorable.
\item The language {\sc min trisection} consisting of pairs $(G,k)$ where $G =
(V,E)$ is a multigraph, $k$ is an integer, and
for which there exists a equipartition $V = A \cup B \cup C$
(i.e., $|A| = |B| = |C|$) so that
the number of edges between different parts of this partition is at
most $k$.
\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}