\documentclass[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}

\setlength{\topmargin}{-0.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.8in}

\usepackage{amsthm} %needed for \theoremstyle below
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}[section]
\setcounter{section}{3}

% 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{\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)}

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

% classname
\newcommand\examNumber{gStrongInduction --- Induction and Strong Induction}
\newcommand\semester{Fall 2023}
\newcommand\className{Foundations of Computer Science}
\newcommand\classNumber{CIS~300}
\newcommand\classFullName{\classNumber~\className}
\renewcommand{\dateseparator}{-}
\yyyymmdddate

% /classname

\title{\examNumber}


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

\begin{document}
\maketitle{}
\section*{Introduction}
This group assignment includes work on proof by induction and proof by
strong induction.

\section*{Assignment Goals}
\paragraph{Learning Outcomes} After completing this group assignment,
each student is expected to be able to
\begin{itemize}
\item Do some \emph{strong} induction proofs.
\item Do some induction proofs
\end{itemize}

\section*{Procedure}

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

\begin{quote}
\begin{description}
\item[Manager] Move discussion forward.
\item[Recorder] Writes the report that will be turned in.
\item[Reflector] Monitor that everyone gets heard and is caught
  up. (This is a \textbf{group} obligation, really.)
\item[Speaker] (Combine w/ \textbf{Reflector} if there are not four
  group members.) Asks the facilitator questions and communicates what
  the team has done.
\end{description}
\end{quote}
\noindent
\textbf{Answer these questions.}

\begin{questions}
\question{} Consider the \emph{recurrence relation}\\
  $u_{k} = u_{k-1} + (2k + 1)$\\
  $u_0 = 1$

  \begin{parts}
    \part{} Write out $u_i$ for $i \in \{1,\ldots,6\}$
    \part{} Write out a \emph{telescoping sum} by subtracting the
      lower-order term from the right-hand side for the six terms you
      calculated above.\\

      $u_{1} = u_{0} + 2(1) + 1$\\
      $u_{1} - u_{0} = 2(1) + 1$

    \part{} Using the cancelling telescope, find a sum for
      $u_{n}$ in terms of $u_{0}$.
    \part{} Prove that $u_{n} = n^2$.
  \end{parts}

\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{} \textbf{Prove} that $\forall k \in \mathbb{Z}^{\ge 0}\; square(k) \limplies \neg
  square(k+2)$.
  \begin{solution}[0.0in]
    TBP:  $\forall k \in \mathbb{Z}^{\ge 0}\; square(k) \limplies \neg
    square(k+2)$

    Proof will have two cases: $k = 0$ and $k > 0$.

    \textbf{Case 1:} $k = 0$\\
    $square(0)$ is true. $\neg square(2)$ is also true.\\
    $\therefore square(0) \limplies \neg square(0 + 2)$.

    \textbf{Case 2:} $k > 0$

    $square(k)$ ::= $\exists r \in \mathbb{Z}^{\ge 0} : r^2 = k$

    Since $k > 0$, $r > 0$. This means $2r + 1 > 2$

    $k = r^2$; $k < k + 2$; $r^2 < r^2 + 2 < r^2 + 2r + 1$

    Last set of inequalities shows: $r^2 < k + 2 < (r + 1)^2$\\
    If $k = r^2$, $k + 2$ is between $r^2$ and $(r+1)^2$, two
    sequential squares, and cannot,
    itself, be a perfect square.

    $\therefore$ for $k > 0$ $square(k) \limplies \neg
    square(k+2)$

    $\therefore$ $\forall k \in \mathbb{Z}^{\ge 0}\; square(k) \limplies \neg
    square(k+2)$
  \end{solution}

\question{} Cantor's Diagonalization for Computer Scientists:

  $|\{$Deciders$\}| < |\P{\{0, 1\}^*}|$

  Please explain, in English, what it means if the stated inequality
  holds? What has been \emph{proved} when the whole diagonalization
  proof is done?
  \begin{solution}[0.0in]
  \end{solution}

\question{} While proving the above inequality, a bijection,
  $f: \Z^+ \rightarrow \P{\{0,1\}^*}$, is represented by a table:

  \begin{parts}
  \part{} \textbf{Explain} why we assume such a bijection exists.
    \begin{solution}[0.0in]
    \end{solution}
  \part{} What label is give to each \emph{row} in the table? How are
    the labels \emph{ordered}?
    \begin{solution}[0.0in]
    \end{solution}
  \part{} What label is give to each \emph{column} in the table? How
    are the labels \emph{ordered}?
    \begin{solution}[0.0in]
    \end{solution}
  \part{} What is the \emph{type} of each entry in the table?
    What do the possible \emph{values} of any given \textbf{entry} in the
    table \textbf{mean}?
    \begin{solution}[0.0in]
    \end{solution}

  \part{} For any $j, k \in \mathbb{Z}^+$, what does it mean if
    $f(j)_{k} = 0$?
    \begin{solution}[0.0in]
    \end{solution}
  \part{} For any $j, k \in \mathbb{Z}^+$, what does it mean if
    $f(j)_{k} = 1$?
    \begin{solution}[0.0in]
    \end{solution}
  \part{} What is the \emph{type} of $f(j)$? What does it mean?
    \begin{solution}[0.0in]
    \end{solution}
  \part{} What is the \emph{type} of $\overline{f(j)}$? What would it
    mean?
    \begin{solution}[0.0in]
    \end{solution}
  \end{parts}

\end{questions}
\end{document}

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