%\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 2024} }
       \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 6}{\bf {March 13, 1pm}}

{\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 1pm on the due date.}

 Good luck!

\medskip

\begin{enumerate}
\item Consider the following 2-person game. The game is played on a
  directed acyclic graph whose nodes are labeled with integers. There
  is a specified start-node $s$.

  Starting from node $s$, the players take turns selecting an outgoing
  edge from the current node: player one selects an outgoing edge from
  nodes $s$, which takes them to a node  $v$, then player two selects
  an outgoing edge from node $v$, which takes them to a node $u$, then
  player one selects an outgoing edge from node $u$, and so on. We
  keep a running sum of the integers encountered as this
  path from $s$ in the graph is traversed. The game ends when a sink (a node with no outgoing edges)
  is reached. At that point player one wins if the running sum equals
  zero; otherwise player two wins. 


Given a game instance (a directed acyclic graph $G$ labeled with
integers, and a start node $s$) 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 game instances 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. Hint: in your
reduction, it is sufficient for the graph to be a {\em layered} graph,
with at most 3 nodes per layer. A layered directed graph is one in
which the nodes can be partitioned into subsets (``layers'') $V = L_1
\cup L_2 \cup L_3 \cup \cdots \cup L_k$ and the only directed edges
are edges between adjacent layers; i.e., from nodes in layer $L_i$ to
nodes in layer $L_{i+1}$.
\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 $w \in
\Sigma^*$, the language
\[L_{-w} = \set{xy : x \in \Sigma^* \mbox{ and } y \in \Sigma^* \mbox{ and } xwy \in L}\]
consists of all strings in $L$ with the string $w$ deleted from
them.
\begin{enumerate}
\item Prove that if $L$ is regular, then $L_{-w}$
is regular. Hint: make $|w|+1$ copies of a DFA recognizing $L$.
\item Prove that if $L$ is R.E., then $L_{-w}$ is R.E.
\end{enumerate}


\item  Suppose someone says they wish to prove the following
  reasonable-sounding statement:

``If some NP-complete language has an
$O(n^2)$-time algorithm, then every language in NP has an
$O(n^4)$-time algorithm.''

Show that such a proof is not possible. In other words, prove that
{\em even if} some NP-complete language had an $O(n^2)$-time
algorithm, the conclusion (that every language in NP has an
$O(n^4)$-time algorithm) is false.


\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 $100$ 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 $100$ clauses, and at least $3/4$ of the other clauses.

\end{enumerate}
\end{enumerate}

\end{document}
