\documentclass[exam, problems]{../../latex-common/cse311-common}
    \title{Final Exam}
	\topic{ }
\newcommand{\otpt}{\operatorname{output}}
\newcommand{\inpt}{\operatorname{input}}

%\usepackage{emoji} %Someday...

\begin{document}
\maketitle

\section*{Instructions}

\begin{itemize}
    \item This is a take home exam. It is due at \textbf{NOON} on Thursday December 17.
    \item Remember to follow the collaboration policy:
    	\begin{itemize}
    		\item You are permitted to work with at most $3$ other students in the class; you may discuss the exam only with those students and the course staff.
    		\item As always, you must write up your work independently. 
    	\end{itemize}
    \item This exam is open-book/open-note. You may use any resource the staff has provided, as well as external resources. 
    \item But you may not search for the particular problems in the exam. 
    \item Submit your responses to gradescope. You may handwrite or typeset solutions (as long as they are legible). We do not recommend trying to write on this document; we have not left enough room. 
    \item If you have a question, please check the pinned post on Ed where we've posted common clarifications. If you still have a question, please ask a \textbf{private} question on ed. 
    
\end{itemize}

\section*{Advice}
	\begin{itemize}
		\item Remember to properly format English proofs (e.g. introduce all your variables).
		\item All proofs for this exam will be English proofs.
		\item We give partial credit for the beginning and end of a proof. Even if you don't know how the middle goes, you can write the start of the proof and put the ``target'' and conclusion at the bottom.
		\item Remember to take deep breaths. 
	\end{itemize}

\vspace{3em}


\begin{center}
    \large
    \begin{tabular}{lrr}
        \toprule
        \textbf{Question} & \textbf{Max points} \\
        \midrule
        Quantify Your Understanding & 16 \\
        Set Proofs  & 20 \\
        Bug & 6 \\
        Scorigami & 26 \\
		Structural Induction & 15  \\
		Some Strings Attached & 18\\
		Wait, That's Illegal & 15 \\
		The Hard One at the End & 7  \\
		End Matter & 2\\
        \midrule
        \textbf{Total} & \textbf{125} & \\
        \bottomrule
    \end{tabular}
\end{center}

\newpage
{\Huge{First Half Fundamentals}}
\section{Quantify your understanding [16 points]}
	Translate each of the following sentences into predicate logic. Let your domain of discourse be strings and languages.
	You may use the following notation: 
	\begin{itemize}
		\item $\pred{regular}(x)$ returns true if and only if $x$ is a regular language. (Returns false on non-regular languages and on strings).
		\item $\pred{string}(x)$ (returns true iff $x$ is a string) and $\pred{language}(x)$ (returns true iff $x$ is a language) to do domain restriction
		\item Common set notation: $\subseteq, \in, \cup, =, \{, \}$, etc. 
	\end{itemize}
	
\begin{enumeratequestions}
	\item The union of two regular languages is regular. [4 points]
	\item Every non-regular language has a regular subset. [4 points]
	\item If $L$ is regular, then for every string $x$, $L\cup \{x\}$ is regular. [4 points]
\end{enumeratequestions}

\subsection*{Contrary to popular belief, contrapositives are fun!}
\begin{enumeratequestions}
	\item[(d)] State the contrapositive of part (c) in English. [4 points]
\end{enumeratequestions}
 
\vspace{0.5in}

\section{Set Proofs [20 points]}
Let $R$ be a relation on the integers (i.e. $R\subseteq \mathbb{Z}\times \mathbb{Z}$). We will use $xRy$ to mean $(x,y) \in R$. 

For a set $A$, define $\inpt(R, A) = \{x : \exists y(y\in A \wedge xRy)\}$. While it might look different on the surface, $\inpt(R,A)$ is closely related to $\otpt(f,A)$ from the midterm. 

For a few examples: $\inpt(|, \{3\}) = \{-3,-1,1,3\}$ where $|$ is the divides relation.\\
$\inpt(|, \{3,6\}) = \{-6,-3,-2,-1,1,2,3,6\}$. \\
$\inpt(S, \{1,4,9\}) = \{-3,-2,-1,1,2,3\}$, where $S = \{(x,y) : x^2=y \}$. 
\begin{enumeratequestions}
	\item Calcluate $\inpt(T, \{0,5\})$ where $T=\{(x,y) : |x|=y\}$. (Hint, there are three elements) [3 points] 
	
	{\color{blue} Take a deep breath. There's more notation to come. If you didn't find a) to be quick, you might want to do a few more examples of $\inpt$ before moving on.}

	\item Call a relation $R$ ``functional'' if $\forall x \exists y( xRy   \wedge \forall z [xRz \wedge xRy \rightarrow y=z])$,
	that is, every $x$ has exactly one element it relates to. Show that the relation $\leq$ (the normal less-than-or-equal-to on $\mathbb{Z}$) is not functional. [3 points]

	\item Show that if $R$ is functional, then $\inpt(R,A) \cap \inpt(R,B) \subseteq \inpt(R, A\cap B)$ [10 points] {\color{blue} Before starting this proof, you might want to see that it holds on a particular example. We recommend you compute each of the sets for $R=\{(x,y) : x^2=y\}$, $A=\{16,25\}, B=\{25,36\}$.}
	
	\item Show that the functional requirement is necessary.\\ I.e. disprove that $\forall R \forall A \forall B [\inpt(R,A) \cap \inpt(R,B) \subseteq \inpt(R, A\cap B)]$. [4 points]
\end{enumeratequestions}

\newpage
{\huge{Induction: Because it's always safe to assume I'm right.}}
\section{Insect Puns Bug Me [6 points]}

For this problem, define a ``tree'' as a directed graph such that:
\begin{itemize}
	\item It has exactly one vertex  (``the root'') with no incoming edges. 
	\item It has zero or more other vertices, each with exactly one incoming edge.
	\item There is a path from the root to every vertex.
\end{itemize}
Call the ``degree'' of a vertex the number of edges that touch it (whether they are coming in or leaving).
You friend has written the following induction proof. It is not correct.

Let $P(n)$ be ``every tree with $n$ vertices has a vertex of degree one.''\\
We show $P(n)$ for all $n\geq 2$ by induction on $n$.

Base Case: $n=2$, There is only one tree with two vertices -- one where the root connects directly to the other vertex (any other graph would be disconnected or have two many edges entering one of the vertices). 
In that graph, the one non-root vertex has degree one. 

Inductive Hypothesis: Suppose $P(2)\wedge \cdots \wedge P(k)$ for an arbitrary $k\geq 2$. 

Inductive Step: \\
Consider an arbitrary tree with $k$ vertices. By Inductive Hypothesis, the tree has a vertex of degree one, call it $v$. Add a new vertex $u$. We consider the ways to connect $u$.\\
Case 1: There is an edge from $v$ to $u$. Since $u$ can have only one incoming edge, $u$ cannot have any other edges, so it has degree one.

Case 2: There is an edge from $u$ to $v$. In this graph, $v$ would have two incoming edges, so it is not a tree and $P()$ vacuously holds.

In either case, $P()$ holds, so we have $P(k+1)$.

By the principle of induction, we have $P(n)$ for all $n\geq 2$. 
\begin{enumeratequestions}
	\item Give an example of a tree which does not fall into the base case, nor would be covered by any of the cases of the inductive step. [3 points]
	\item What would be the first sentence of a correct inductive step (i.e. the correct starting point)? You do not need to write the full step. Hint: what kind of claim is $P()$? [3 points]
	
\end{enumeratequestions}

\newpage
\section{Scorigami [26 points]}
Scorigami\footnote{As defined by Jon Bois in this \href{https://www.youtube.com/watch?v=9l5C8cGMueY&t=281s}{video}; if you enjoy football, you may enjoy this video. If you don't, you won't miss anything by not watching it.} is the art of tracking the possible final scores in your favorite game. 
In this problem, we'll play scorigami for a game Robbie just made up. 

Robbie's game is played over rounds between two players. At the start of the game, each player has $0$ points. In each round, exactly one of the following things occurs:
\begin{enumerate}
	\item[1.] One player gets $3$ points, and the other gets $1$ point.
	\item[2.] One player gets $4$ points, and the other gets $0$ points
	\item[3.] One player gets $6$ points, and the other gets $3$ points. 
\end{enumerate}
A game may end after any number of rounds, as long as the players have a different number of total points. When the game is over, the player that has more points is the winner.

\begin{enumeratequestions}
	\item Prove by induction that the losing player could end the game with any natural number of points. [8 points] 
	\item Prove by induction that the winning player could end the game with $n$ points for every $n \geq 3$ (prove by induction on $n$ -- be careful, make sure the player is the winner!) [16 points]
	\item Can you combine the two claims to get: for every $n\geq 3$ and every $m \geq 0$, if $n>m$ then a game can end with the winning player having $n$ points, and the losing player having $m$ points? \\
	If yes, describe in 1-3 sentences how you could prove it (e.g. how you would modify or combine your proofs above); if not, give 1-3 sentences explaining why the statement is false.\\ 
	You do not need to give a formal proof in either case. [2 points]
\end{enumeratequestions}

\problemvspace{1in}

\section{Structural Induction [15 points]}
Consider the following context-free-grammar, which generates the language $L$:
\begin{align*}
	S &\rightarrow 00S1 | S010010 | 010S | \varepsilon
\end{align*}

We could rewrite this CFG using the following recursive definition:

\textbf{Basis:} $\varepsilon \in L$\\
\textbf{Recursive:} if $x \in L$ then $00x1 \in L$, $x010010 \in L$ and $010x \in L$. 

Prove that $\forall x \in L$, the number of 0s in $x$ is twice the number of 1's in $x$.

You must use structural induction for this problem.

\newpage
{\Huge{The Last Few Weeks}}
\section{Some strings attached [18 points]}
\begin{enumeratequestions}
	
	\item Write a regular expression for the language $\{xy : x~\text{starts with 1 and ends with 0}, y~\text{starts with 0 and ends with 1}\}$
	\item Write a context free grammar for the language $\{0^m1^n : m\not\equiv n \pmod{3}\}$\\
	 If your grammar has more than one symbol: tell us which non-terminal is the start symobl and for every other non-terminal tell us what strings it generates.
	\item Draw an NFA for the language $\{x : \left[\operatorname{len}(x) \equiv 0 \pmod{2} \wedge x~\text{starts with a 1} \wedge x~\text{ contains 11}\right] \vee \left[x~\text{contains 000}\right]\}$.\\
	Please name your states, and briefly explain how your machine works (2-3 sentences total).
\end{enumeratequestions}
For drawing the NFA, you may want to use an interface like \href{http://madebyevan.com/fsm/}{http://madebyevan.com/fsm/}
\problemvspace{1in}

\section{Wait, That's Illegal [15 points]}
Choose \textbf{one} of the two problems to do. Do not submit attempts at both. 

\subsection{This is Highly Irregular}
Use the method from class (i.e. the one in lecture 27) to prove that $\{w\#w | w\in \{0,1,2\}^* \}$ is not regular. ($\#$ is just a character here, i.e. for this problem $\Sigma=\{0,1,2,\#\}$)

\subsection{1,2,3,...$\infty$}
A ``Turing Machine'' is a common abstraction for normal computers. The memory of a Turing Maching is an infinite ``tape.'' The tape is divided into cells (think: bits) that are either $0$ $1$ or $\sqcup$ ($\sqcup$ corresponds to ``not initialized yet'').
The tape is infinite in the following sense: for every integer $i$, there is a cell $i$ of the tape (i.e., the nubmer of cells is countable).

Show that the number of possible tapes is uncountable by adapting Cantor's Diagonalization argument.

\newpage
\section{The really hard one at the end [7 points]}
This is (in Robbie's opinion) the hardest problem on the exam. We've intentionally made it worth a small amount of points so that you do not feel bad about giving up if you get stuck.

A \textbf{Tourist Machine} is a finite automaton: it has a finite set of states, a start state, and transitions between states labeled with an $x \in \Sigma$. For every state $q$ and every character $x$, there is at least one transition labeled with $x$ leaving $q$  (so computation can't ``die'').\\
A Tourist Machine processes a string much like an NFA does -- it can read a character from the string and follow a transition (of its choice if more than one) labeled with that character.
But a Tourist Machine does not have any final states. Instead, a Tourist machine accepts input $x$ if and only if the machine can vist all of its states while processing $x$.

The language of a Tourist Machine is the set of all strings that it accepts. 

In this problem you'll show Tourist Machines are less powerful than DFAs.

\begin{enumeratequestions}
	\item Suppose $L$ is the language of a Tourist Machine. Give a construction that shows $L$ must be regular (i.e. tell us how to make an NFA/DFA/regex). Include all the details we would need to build your regular expression, NFA, or DFA for any particular Tourist Machine. You do not have to formally prove your construction is correct, but you should write 2-3 sentences briefly explaining why it works. [4 points]
	\item Prove that there is a regular language $L$ that is not the language of a Tourist Machine.\\
	 Hint: think about languages where our DFAs definitely wouldn't visit every state in an accepting computation.\\
	 It is not enough to just state a language here. You must give a regular language, \textbf{and} prove that no Tourist Machine can accept that language. [3 points]
\end{enumeratequestions}

\newpage

\section*{Feedback [1 point]}
So we can help 311 instructors teaching remotely this year:
\begin{enumeratequestions}
	\item How long did you spend studying for the final \textbf{before} working on the final (estimate to the nearest hour)
	\item How long did you work on the final overall (estimate to nearest hour)
	\item Of the time in (b), how long was ``studying'' (e.g. looking up old lectures or old problems)
	\item Of the time in (b), how long was making the pretty final submission (typing or writing/uploading/finding the best wording/checking your answers)
\end{enumeratequestions}

\section*{For grading morale [1 point]}
Produce a piece of art to reflect how you will relax over Winter break, now that you won't have 311 homework.
Suggested media include drawing, poetry, or short story.\\
The TAs will use these for morale boosts during grading breaks.

Any non-empty submission will receive full credit. 


\problemvspace{3in}

Gumball is proud of you. He says you deserve a nap.
\begin{center}
	\includegraphics[width=.4\textwidth]{Gumball_done.jpeg}
\end{center}
\end{document}