UMDAssignmentTemplates

% LaTeX Assignment Template
% Developed by Jason Filippou (jasonfil@cs.umd.edu)
% Maintained at https://github.com/JasonFil/UMDAssignmentTemplates

% Document class will always be article for the purposes of UMD assignments
\documentclass[letterpaper,12pt]{article}

% Tweak the following based on what you think the current document needs:
\usepackage[inner=1.5cm,outer=1.5cm,top=2cm,bottom=1.5cm]{geometry}
\usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue]{hyperref}
\setlength{\parindent}{2em}
\setlength{\itemindent}{.5in}
%\DeclareMathSizes{12pt}{14pt}{10pt}{8pt}

% Title of the current document
\title{CMSC250, Spring '18: Final Exam}


%%%%%%%%%%%%%  IMPORT MACRO FILES AS NEEDED %%%%%%%%%%%
\input{packageimports}
\input{mymath}
% \input{code} % This is useful for assignments in CMSC420, 132, etc
\input{formatting}
\input{emphasis}
\input{cool}
\input{examdata} % Edit this file for variable problem numbers in grading box
 \input{cards}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}


% Box at the top of every first page.
\examdata{CMSC250, Spring 2018}{all}{Final Exam}{Tuesday, 05-15-2018}{04:05pm-06:00pm}

\vspace{-.3in}

\section*{Exam guidelines / rules}
\label{sec:guidelines}
\begin{itemize}
	
	\item \textbf{TURN OFF ALL ELECTRONIC DEVICES} (e.g phones, tablets, laptops, {\bf calculators}). Setting a device on ``silent" or ``sleep" mode does \textbf{not} constitute it being turned \textbf{off}: Your device is turned off if and only if it requires \textbf{pushing a power button to begin the execution of a bootloader}. \textbf{Proctors reserve the right to confiscate an electronic device if it is not turned off according to the definition above.}
		\item The exam is {\bf CLOSED BOOK AND NOTES}.
		\item {\bf DO NOT RIP PAGES FROM THE EXAM}. You can ask us for \textbf{extra scrap paper} if you need it.
	\item {\bf WRITE NEATLY}. If we can't read your response, you will receive \textbf{no credit} for it. 
	\item There are {\bf 7 (seven)} problems in this exam, with a total grade value that adds to $\mathbf{100}$ \textbf{(one hundred)}.
	\item The exam has been printed \textbf{two-sided}, \textbf{stapled on the top-left corner} and spans {\bf 24 (twenty-four)} pages across {\bf 12 (twelve)} sheets. 
	\item The total time allocated for this exam is \textbf{115 (one hundred and fifteen)} minutes.
	\item You may \textbf{not} leave the classroom (e.g to go to the bathroom, or because you're done) during the \textbf{last 5 (five) minutes} of the exam.
\end{itemize}
 \vspace{-.2in}
\section*{Provided materials \& assumed facts}
 \vspace{-.1in}
\subsection*{Logic}
\label{subsec:logic}

Table \ref{tbl:propLogicAxioms} contains a number of logical equivalences that we have discussed in class. Recall that, in Logic, the symbol $\equiv$ means ``logically equivalent to". 

\begin{table}[H]
	\centering
	\renewcommand*{\arraystretch}{1.2}
	\begin{tabular}{|>{\centering\arraybackslash}p{1.5in} | c | c |} \hline
		\textbf{Commutativity of binary operators} & $p \land q \equiv q \land p$ & $p \lor q \equiv q \lor p$ \\ \hline
	\textbf{Associativity of binary operators} & $(p \land q) \land r \equiv p \land (q \land r)$ &  $(p \lor q) \lor r \equiv p \lor (q \lor r)$ \\ \hline
	\textbf{Distributivity of binary operators} & $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ & $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ \\ \hline
	\textbf{Identity laws} & $p \land T \equiv p$ & $p \lor F \equiv p$ \\ \hline
	\textbf{Negation laws} & $p \lor (\neg p) \equiv T$ & $p \land (\neg p) \equiv F$ \\ \hline
	\textbf{Double negation} & \multicolumn{2}{c|}{$\neg (\neg p) \equiv p$}  \\ \hline 
	\textbf{Idempotence} & $p \land p \equiv p$ & $p \lor p \equiv p$ \\ \hline
	\textbf{De Morgan's axioms} & $\neg (p \land q) \equiv (\neg p )\lor (\neg q)$ & $\neg (p \lor q) \equiv (\neg p) \land (\neg q)$\\ \hline
	\textbf{Universal bound laws} & $p \lor T \equiv T$ & $p \land F \equiv F$ \\ \hline
	\textbf{Absorption laws} & $p \lor (p \land q) \equiv p$ & $p \land (p \lor q) \equiv p$ \\ \hline
	\textbf{Negations of contradictions / tautologies} & $\neg F \equiv T$ & $\neg T \equiv F$ \\ \hline
	\textbf{Equivalence between biconditional and implication} & \multicolumn{2}{c|}{$a \Leftrightarrow b \equiv (a \Rightarrow b) \land (b \Rightarrow a)$} \\ \hline
	\textbf{Equivalence between implication and disjunction} & \multicolumn{2}{c|}{$a \Rightarrow b \equiv \neg a \lor b$} \\ \hline
	\end{tabular} \vspace{.1in}
	\caption{A number of propositional logic axioms you can refer to.}
	\label{tbl:propLogicAxioms}
\end{table}
 
\pagebreak

\subsection*{Set Theory}
\label{subsec:setTheory}

The following are Set Theoretic notation and definitions.

\begin{table}[H]
	\centering
	\renewcommand*{\arraystretch}{1.4}
	\begin{tabular}{| c | c | c | } \hline 
		{\large \bf Operation} & 		{\large \bf Symbol} &  {\large \bf Definition } \\  \hline 
		\textbf{Membership} & $x \in A$ & $x$ is a member of set $A$ \\ \hline
		\textbf{Non-membership} & $x \notin A$ & $ \neg (x \in A)$ \\ \hline
		\textbf{Union} & $A \cup B$ & $\{ (x \in A) \lor (x \in B)$\}   \\ \hline
		\textbf{Intersection} & $A \cap B$ & $\{ (x \in A) \land (x \in B)$\}   \\ \hline
		\textbf{Relative complement of} $\mathbf B$ \textbf{given} $\mathbf A$ & $A - B$ & $\{ (x \in A) \land (x \notin B)$\}   \\ \hline 
		\textbf{Universal (Absolute) complement} & $\overline{A}$ & $\{x \notin A\}$\\ \hline
		\textbf{Cartesian Product} & $A \times B$ & $\{(a, b) \mid   (a \in A) \land (b \in B)  \}$ \\ \hline
		\textbf{Subset} & $A \subseteq B$ & $(\forall x \in A)[x \in B] $\\ \hline
		\textbf{Superset} & $A \supseteq B$ & $ B \subseteq A$\\ \hline
		\textbf{Set equality} & $A = B$ & $(A \subseteq B) \land (B \subseteq A) $ \\ \hline
		\textbf{Set non-equality} & $A \neq  B$ & $\neg (A =B) $ \\ \hline
		\textbf{Proper subset} & $A \subset B$ & $ \{ (A \subseteq B) \land (A \neq B) \} $ \\ \hline
		\textbf{Proper superset} & $A \supset B$ & $ \{ (A \supseteq B) \land (A \neq B) \} $ \\ \hline
		\textbf{Powerset} & $\Pset{A} $ & $ \{ X \mid X \subseteq A \} $ \\ \hline
	\end{tabular}
	\vspace{.1in}
	\caption{Definitions of Set Theory}
	\label{tbl:setTheory}
\end{table}

\subsection*{Number Theory}

\begin{itemize}
	\item The set of naturals $\N$ is \textbf{closed} under \textbf{addition} and \textbf{multiplication}.
	\item The set of integers $\Z$ is \textbf{closed} under \textbf{addition}, \textbf{subtraction} and \textbf{multiplication}.
	\item $0 \in \N$.
\end{itemize}
 

\pagebreak

\problem{Various}{10}

{\large For every one of the following statements, fill in the circle corresponding to the appropriate choice (\True{} or \False{}).  For example, if any given statement is \True, you should fill in the {\bf first} circle, such that \whitecircle{5pt} becomes \tikz\draw[black,fill=black] (0,0) circle (.85ex); . \textbf{PLEASE DO \underline{NOT} USE CHECKMARKS (\Checkmark),  CROSSES ({\large $\mathlarger \displaystyle \times$}), ETC: FILL-IN THE CIRCLES AS INDICATED ABOVE.} You do {\bf not} need to justify your answers. You may refer to Table \ref{tbl:setTheory} for a list of all axioms of Set Theory that we have learned in the class. }

\begin{table}[H]
	\renewcommand{\arraystretch}{1.6}
	\centering
	{\large 
	\begin{tabular}{|c|c|c|c|} \hline 
		& {\bf Statement } & {\bf True} & {\bf False} \\ \hline 
		(a)& $ \{ 2 \} \in \{2, \{ \{ 2 \} \} \} $ & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(b)& $\Q^{\leq 0}$ is {\bf countable}. & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(c)& $f: \R^{\geq 0} \rightarrow \R^{\geq 0}, f(x) = x^{16}$ is a {\bf bijection}.  & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(d)& $f: \R^{> 0} \rightarrow \R^{> 0}, f(x) = \frac{1}{\vert x \vert }$ is a {\bf bijection}. & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(e)& $(\exists A)[ \emptyset \in (A - A) ]$ & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(f)& $(\forall A)[\vert \Pset{A} \vert = \vert A \vert ]$ & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(g)& $(\forall A)[\vert \Pset{ \{ A \} } \vert ] = 2$ & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(h)& $ \vert \Pset{\Pset{\{ 1, 2, 3 \} }} \vert = 8 $ & \whitecircle{5pt} & \whitecircle{5pt} \\ \hline
		(i)& If $a, b \in \Q^{>0}$, then $a^b \in \Q$ & \whitecircle{5pt} & \whitecircle{5pt} \\  \hline
		(j)& If $a, b \not\in \Q$, then $\frac{a}{b} \notin \Q$ & \whitecircle{5pt} & \whitecircle{5pt} \\  \hline
	\end{tabular}
	}
	\caption*{}
\end{table} \vspace{-.4in}
\freespace 
\pagebreak

\notespage

\problem{Logic}{10}


\question{Truth Tables}{5}

{\large Complete the  following \textbf{truth table} for the logical expression }

{\Large $$(p \land q) \lor (\neg (z \land q) )$$ } 

{\large To start you off, we are giving you the first three columns. Write {\bf neatly}; if we can't make out the difference between a \T{} and an \F{}, we will be forced to take off points! Also, you should write \T{} and \F{}, {\bf not} \textbf{1} or \textbf{0}. You can use the scrap space available if you want to first fill in the table with \textbf{0}s and \textbf{1}s. } 

\begin{center}
	\begin{table}[H] 
		\Large 
		\setlength{\tabcolsep}{16pt}
%		\renewcommand{\arraystretch}{1.2}
		\begin{tabular}{|c|c|c|c|c|c|c| p{5.25in}|} \hline 
			$p$ & $q$ & $z$ & $p \land q$ & $z \land q$ & $ \neg (z \land q)$ & $(p \land q ) \lor (\neg (z \land q)) $\\ \hline
			\F & \F & \F & & & &   \\ \hline 		
			\F & \F & \T & & & & \\ \hline 		
			\F & \T & \F & & & &  \\ \hline 		
			\F & \T & \T & & & &\\ \hline
			\T & \F & \F & & & &\\ \hline 		
			\T & \F & \T & & & &\\ \hline
			\T & \T & \F & & & &\\ \hline 		
			\T & \T & \T & & & &\\ \hline												
		\end{tabular}
	\end{table}
\end{center} \vspace{-.7in}

\freespace

\pagebreak

\question{Logical equivalence}{5}


{\large Prove that the following compound logical expression: }

{\Large $$ \big (   ( z \lor q  ) \lor   ( z \land \neg q   )  \big ) \land  \big ( z \lor   ( \neg    ( \neg p \land \neg z   )   )  \big )$$ }
\vspace{-.1in}

{\large is logically equivalent to the expression: } 

{\Large $$z \lor (q \land p) $$ }

{\large For every derivation you make, write the \textbf{name} of the propositional logic axiom that you are using \textbf{on the right of the derivation.} Refer to Table \ref{tbl:propLogicAxioms} for a list of all propositional logic axioms we have learned in the class. }
\answerspacefullpage

\problem{Relations}{10}


\newcommand{\emptybox}[1]{\framebox(#1,#1){} }
 
{\large For every one of the following relations, fill in the square corresponding to the choices you believe are appropriate for the given relation $A$. For example, if you believe that $A$ \textbf{is} reflexive but \textbf{neither} symmetric {\bf nor} transitive, you should turn the first square from \emptybox{8} into \ $\blacksquare$ \ with your pen or pencil, yet leave the other two ones empty, like so: \emptybox{8}.\ If you believe that the relation doesn't have {\bf any} of the three properties, you should fill  in {\bf the last} box. If you believe that the relation has {\bf all} properties, you should fill in {\bf the first three} boxes. \textbf{PLEASE DO \underline{NOT} USE CHECKMARKS (\Checkmark), CROSSES, ({\large $\mathlarger\times$}), ETC: FILL IN THE SQUARES AS INDICATED ABOVE.} Note that for every relation, you are {\bf given} the sets for which the relation is defined; \textbf{those change from relation to relation}. You do {\bf not} need to justify your answers.  }

\begin{table}[H]
	\centering
	\setlength\extrarowheight{15pt}

		\hskip-.5cm
		\begin{tabular}{|c|c|c|c|c|c|} \hline 
			& {\bf Relation } & {\bf Reflexive} & {\bf Symmetric } & {\bf Transitive } & {\bf None}\\ \hline 
			(a) & $A \subseteq \R \times \R$ ,  $A = \{ (x, y) \mid x \geq y \}$ & \emptybox{8} & \emptybox{8} & \emptybox{8}  &  \emptybox{8} \\ \hline
			(b) & $A \subseteq \N^{\geq 1} \times \N^{\geq 1}$ ,  $A= \{ (x, y) \mid x \leq y^2 \}$ & \emptybox{8} & \emptybox{8} & \emptybox{8}  &  \emptybox{8} \\ \hline
			(c) & $A \subseteq \R \times \R$ ,  $A= \{ (x, y) \mid \vert x - y \vert \geq 1 \}$ & \emptybox{8} & \emptybox{8} & \emptybox{8}  &  \emptybox{8} \\ \hline
			(d) & $A \subseteq \N^{\geq 2} \times \N^{\geq 2}$,  $A= \{ (x, y) \mid y \equiv 0 \pmod{x} \}$ & \emptybox{8} & \emptybox{8} & \emptybox{8} &  \emptybox{8} \\ \hline
			(e) & $A \subseteq \R \times \R, A= \{ (x, y) \mid x \geq \floor{y}  \} $ & \emptybox{8} & \emptybox{8} & \emptybox{8} &  \emptybox{8} \\ \hline
		\end{tabular}
	\caption*{}
\end{table} \vspace{-.3in}
\freespace
 
\notespage

\problem{Number Theory}{20} 

\question{Direct Proof}{5}

{\large Prove {\bf directly} that, if $q \in \Q$, $q-1 \in \Q$. }

\answerspacefullpage

\question{Indirect Proof I}{5}

{\large Suppose that $a \in \Z$. Using an {\em indirect} proof methodology, prove that, if $a^3 \equiv 0 \pmod{5}$, then $a \equiv 0 \pmod{5}$. }  

\answerspacefullpage

\question{Indirect Proof II}{10}

{\large Using an {\em indirect} proof methodology as well as the theorem of question (b), prove that $\sqrt[3]{5} \notin \Q$. You should take the theorem of question (b) {\bf as a given, whether you were able to prove it or not.} }

\answerspacefullpage

\notespage

\problem{Induction}{20}

\question{Strong}{5}

{\large Let $a_n$ be a sequence recursively defined as follows: }


{\Large $$a_n = \begin{cases}6, & n = 0 \\ 8, & n = 1 \\ -2n + a_{\tiny n-1} + a_{\tiny n-2}, & n \geq 2 \end{cases}$$ }

{\large Using {\bf strong induction}, show that }

{\Large $$(\forall n\ge 0)[a_n = 2n+6]$$ }

\vspace{-.2in}
\standardinductionspace

\pagebreak

\question{Structural on binary trees}{7}

{\large We recursively define a {\bf perfect binary tree} of height $h$, as follows:

\begin{itemize}
	\item A single node called the tree's \textbf{root}, if $h=0$, or 
	\item A root node pointing to \textbf{two} \textbf{perfect} binary trees of height $h-1$, if $h>0$.
\end{itemize}


Let $V$ be the number of nodes and $E$ the number of edges in a perfect binary tree.  Use structural induction to prove that $E=V - 1$.  \textit{Hint: Induct on the height of the tree.}

} 
\standardinductionspace

\question{Structural on $k$-ary trees}{8}

{\large A {\bf perfect tree} (not perfect {\bf binary} tree!) of height $h$ is either

\begin{itemize}
	\item A single node called the tree's \textbf{root}, if $h=0$, or 
	\item A root node that points to the roots of \textbf{one} or \textbf{more} perfect trees, each of height $h - 1$, if $h>0$.
\end{itemize}

Let $V$ be the number of nodes and $E$ the number of edges in a perfect tree.  Use structural induction to prove that $E=V - 1$.  \textit{Hint: Induct on the height of the tree.}
}
\standardinductionspace

\problem{Combinatorics / Probability}{20}

{\large Answer the following questions on the line available to you after each and 
every one of them. Your answer should be in terms of {\bf factorials}, {\bf permutation / combination symbols} or {\bf ratios} of the aforementioned quantities. Do {\bf not} simplify any ratios: for example, if you end up with a result of form $\nicefrac{4!}{2!}$, leave it {\bf exactly as is}; do {\bf not} simplify the ratio to $6$.
}
\begin{enumerate}[label=(\alph*)]
\doublespacing
	\item The {\bf Greek alphabet} has \textbf{24 (twenty-four)} characters, of which \textbf{7 (seven)} \\ are vowels, and \textbf{17 (seventeen) } are consonants. How many strings of length \\ 
$\mathbf{13}$ \textbf{ (thirteen)} can we construct from this alphabet...
		\begin{enumerate}[label=(\roman*)]
			\lineitem {If we {\bf CAN reuse} the same characters (WITH replacement)?}
			\lineitem {If we {\bf CANNOT reuse} the same characters (WITHOUT replacement)?}
			\lineitem {If we want {\bf exactly} three vowels, and we \textbf{CAN} re-use characters? }
			\lineitem {If we want {\bf exactly} three vowels, and we \textbf{CANNOT} re-use characters? }
		\end{enumerate}

		\item The {\bf octal} numbering system uses the digits $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$ to build  \\ ``octal strings". How many octal strings of length $10$ (ten) contain:
	\begin{enumerate}[label=(\roman*)] 
		\setlength\itemsep{0.6em}
	  	\lineitem{ \textbf{Exactly}  three \textbf{6}s?    }
 		\lineitem{ \textbf{At most}  three \textbf{6}s?    }
		\lineitem{ \textbf{Exactly}  three \textbf{6}s and {\bf exactly} four \textbf{5}s?    }
	\end{enumerate} 
	\item A standard deck of cards has $\mathbf{52}$ \textbf{(fifty-two)} cards, which are divided into \\ \textbf{4 (four)} \textbf{suits}:\textbf{ clubs, diamonds, spades and hearts}. Every suit is \\  subdivided into \textbf{13 (thirteen)} \textbf{ranks}: Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, \\  Queen, King. The Jack, Queen and King of {\bf all four suits} are also called \\ {\em face} cards. A ``hand" is just a set of $n\geq 1$ cards. Order {\bf never matters} \\ in hands. For example, A\spd{} 7\spd{}  4\clb{} and 7\spd{} A\spd{} 4\clb{} are the \textbf{same 3} \\ \textbf{ (three) - card hand}.
	\begin{enumerate}[label=(\roman*)]
		\lineitem{How many \textbf{6 (SIX)} - card hands are there?}
		\lineitem{How many \textbf{6 (SIX)} - card hands of {\bf only face cards} are there?}
		\lineitem{How many \textbf{6 (SIX)} - card hands contain {\bf all 4 (four) Aces}?}
		\lineitem{How many \textbf{4 (FOUR)} - card hands contain {\bf all 4 (four) Aces}?}
		\lineitem{How many \textbf{6 (SIX)} - card hands {\bf do not} contain {\bf any} face \\ cards? }
	\end{enumerate}
	\item Suppose that we have a group of people from \textbf{4 (four)} different countries: \\ \textbf{8 (eight)} from the USA, \textbf{2 (two)} from Egypt, \textbf{4 (four)} from Greece \\ and \textbf{6 (six)} from Israel. We are interesting in creating committees from \\ all of these people. In committees, order of the people in the committee \\ does {\bf NOT} matter.
	\begin{enumerate}[label=(\roman*)]
		\lineitem {How many \textbf{4 (four)}-person committees can we make from this group of \\ people? }
		\lineitem {How many \textbf{4 (four)}-person committees can we make from this group \\ of people if we want every person to be \textbf{from a different country?} }
		\lineitem {What is  the \textbf{probability} that a \textbf{4 (four)}-person committee, chosen at \\ random from this group of people consists of people from {\bf 4 (four)} \\ different countries?} 
	 \end{enumerate}	
\end{enumerate}
 
 
\freespace

\problem{Show me what you got}{10}

{\large Suppose that $\mathlarger{T_n}$ is a sequence recursively defined as follows: }

{\Large $$T_n = \begin{cases}0, & n = 0 \\ 5, & n = 1 \\ T_{\floor{\nicefrac{n}{6}}} + T_{\floor{\nicefrac{2n}{3}}} + 3n, & n \geq 2 \end{cases}$$ }

{\large Using {\bf Constructive STRONG induction}, find the {\bf smallest possible} constant $\mathlarger{c \in \R^{>0}}$ such that:  }

{\Large $$(\forall n \in \N)[T_n \leq c  n]$$ }
 
\standardinductionspace

\notespage


\end{document}