\documentclass[noanswers,addpoints,10pt]{exam}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[most]{tcolorbox}
\usepackage{datetime}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{xltxtra}
\usepackage{listings}

\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{makecell}
\usepackage{multicol}
\usepackage{multirow}

\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,decorations.pathmorphing,backgrounds,positioning,fit}
\usepackage{pgf-umlcd}

% compact itemized and then enumerated
\setlist{leftmargin=*,
  noitemsep,
  topsep=5pt,
  parsep=0pt,
  partopsep=0pt,
}

\setlist[enumerate]{leftmargin=*,
  itemsep=2pt,
  topsep=0pt,
  parsep=0pt,
  partopsep=0pt,
}


\usepackage{fontspec}
\setmainfont{Gentium Basic}
\setmonofont{Comic Code}[
Scale          = 0.80,
UprightFont    = *-Regular,
ItalicFont     = *-Italic,
BoldFont       = *-Bold,
BoldItalicFont = *-Bold Italic
]

\lstset{
  basicstyle=\ttfamily,
}

\DeclareMathOperator{\limplies}{\Rightarrow}
\DeclareMathOperator{\lbiconditional}{\Leftrightarrow}
\DeclareMathOperator{\liff}{\iff}
\DeclareMathOperator{\lxor}{\oplus}
\DeclareMathOperator{\qeq}{\overset{?}{=}}
\DeclareMathOperator{\modulus}{\mathbf{mod}}
\DeclareMathOperator{\even}{even}
\DeclareMathOperator{\odd}{odd}
\DeclareMathOperator{\ddiv}{|}
\DeclareMathOperator{\ndiv}{\not|}
\DeclareMathOperator{\contra}{\Rightarrow\mskip-\thinmuskip\Leftarrow}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\P}[1]{\mathbb{P}(#1)}
\newcommand{\mathcheckmark}{\text{ \ding{51}}}

\DeclareMathOperator{\vowel}{vowel}
\DeclareMathOperator{\consonant}{consonant}
\DeclareMathOperator{\isprime}{prime}
\DeclareMathOperator{\equals}{equals}
\DeclareMathOperator{\divides}{divides}

\newcommand\examNumber{gMoreProofs}
\newcommand\semester{Spring 2024}
\newcommand\className{Foundations of Computing}
\newcommand\classNumber{CIS~300}
\newcommand\classFullName{\classNumber~\className}
\renewcommand{\dateseparator}{-}
\yyyymmdddate

% /classname
\pagestyle{headandfoot}
\firstpageheader{~\\\classFullName}{\examNumber\\~}{~\\\semester}

\newenvironment{showExample}[1]{
  \begingroup
  \renewcommand{\solutiontitle}{\noindent\textbf{Example:}\enspace}
  \printanswers
  \begin{solution}[#1]
  }{
  \end{solution}
  \endgroup
}

\begin{document}

\section*{Introduction}
Students will work in groups using propositional logic, truth tables,
and logic operations.

\section*{Learning Outcomes}
When completing this assignment, students should be able to

\begin{itemize}
\item \textbf{Use} named rules of inference.
\item \textbf{Set-up} different types of proof.
\item \textbf{Prove} theorems with different methods of proof.
\end{itemize}

\textbf{Get out paper.}

\noindent
\textbf{Copy each question before the answer.}

n\noindent
\textbf{Assign Roles.} Students should take roles they
have not held recently (or, perhaps, ever).

\noindent
\textbf{Answer these questions.}

\emph{A proof of a proposition is a convincing argument that the
  proposition is true.}

\begin{questions}
\question{} Given $P_{1} \land P_{2} \land P_{3} \limplies Q$
  What is the contrapositive?
\question{} What is a \emph{binary language}?

\question{} \textbf{State} the Halting Problem: What is the
  \emph{decider} in question, what is the \emph{input} to the decider,
  and \emph{what} do you know about the decider in question?

\question{} Given the set $C = \{\spadesuit, \heartsuit, \clubsuit,
  \diamondsuit\}$, describe how you could \textbf{prove} $|C| = 4$.

\question{} How could you represent the \emph{subsets} of $C$ as bit
  strings? How many bits would you need per subset? How would you
  assign meaning to the \emph{order} of the bits because $C$ is
  unordered?

\question{} \textbf{Prove} $|\P{C}| = |\mathbb{Z}_{16}|$ using a \emph{T-table} to
  express the function.

\question{} \textbf{Explain}, in English, what it means to say that some piece
  of code, with input size $j$, is $O(j^2)$? Include what happens if
  the input size is \emph{doubled} or \emph{tripled}.
  \begin{solution}[0.0in]
  \end{solution}

\question{} Consider proving the following summation is equivalent
  to the given \emph{closed-form} for all $g \ge 0$:

  $\sum\limits_{i=0}^{g} i^3 = \frac{g^4 + 2g^3 + g^2}{4}$
  \begin{parts}
  \part{} Before working on proving the above, prove that the
    closed-form is always an integer by \textbf{proving} that

    $\forall g \in \mathbb{Z}^{\ge 0}\;\;\;4 \ddiv g^4 + 2g^3 +
      g^2$

    \textbf{Note:} this can be done by induction or by algebra, your
    choice.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} \textbf{Define} a \emph{predicate}, $R(g)$, such that the
    proof of the above equivalence is the same as the proof of

    $\forall g \in \mathbb{Z}^{\ge 0}$ $R(g)$.

  \part{} \textbf{Prove} that $R(k)$ is true for all $k \in \{0, 1,
    2\}$.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} State and \textbf{prove} the \emph{basis} of proving $R(g)$
    for all non-negative integers.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} \textbf{State} the \emph{inductive hypothesis} without
    using your predicate.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} State and \textbf{prove} the \emph{inductive hypothesis} for
    the original equivalence; you may use your predicate if you
    wish. Stop after the \emph{inductive hypothesis} is proved.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} Write the final \emph{therefore} for proving that the
    original equivalence holds for all non-negative numbers.
    \begin{solution}[0.0in]
    \end{solution}

  \part{} Explain, in English, your own words, what the final
    \emph{therefore} statement actually means.
  \begin{solution}[0.0in]
  \end{solution}
  \end{parts}

\question{} Dr. Ladd has written a piece of code that, for an
  input of size $g$, executes $\sum\limits_{i=0}^{g} i^3$
  instructions. The running time of the code is $O(f(g))$ for some
  function $f$. What is the smallest $f(g)$ you can give?
  \begin{solution}[0.0in]
  \end{solution}

\end{questions}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
