\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{gCounting}
\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 Expand some recurrence relations
\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 {} Given a class for linked-list nodes as followws

\begin{lstlisting}[language=java]
class Node {
  public int data;
  public Node next;
}
\end{lstlisting}

  Write a \emph{recursive} function that takes a \lstinline|Node| as
  its parameter and returns the sum of the values in the list.
  \begin{solution}[0.0in]
  \end{solution}


\question{} Consider the \emph{recurrence relation}\\
  $u_{k} = u_{k-1} + 2k$\\
  $u_0 = 0$

  \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_{k} - u_{k-1} = 2\times (k)$\\
      $u_{k-1} - u_{k-2} = 2\times (k-1)$\\
      $u_{k-2} - u_{k-3} = 2\times (k-2)$\\
      \ldots

    \part{} Using the cancelling telescope, find a sum for
      $u_{k}$ in terms of $u_{0}$.
    \part{} Prove that $u_{k} = k(k+1)$.
  \end{parts}
\question{} Consider a pile of 4\textcentoldstyle{} and
  11\textcentoldstyle{} stamps.
  \begin{parts}
  \part{} What values of postage can be made, exactly, with just these stamps?
  \part{} Prove, using \emph{strong} induction, that your answer above
    is correct.
  \part{} Prove using \emph{weak} induction, that your answer to (a)
    above is correct. Pay close attention to the \textbf{inductive
      hypotheses} and how they are different in both proofs.
  \end{parts}

\question{} There is a bin with 10 each of lemon, cinnamon, and
  rose flavored chocolates. How many chocolates must be drawn to
  assure that:
  \begin{parts}
  \part At least two different flavors are picked?
    \begin{solution}[0.0in]
    \end{solution}

  \part At least three of \emph{one} flavor are picked?
    \begin{solution}[0.0in]
    \end{solution}

  \part No flavor is missing from the chocolates picked?
    \begin{solution}[0.0in]
    \end{solution}
  \end{parts}

\question{} Use strong induction to show that every positive integer $n$
  can be written as a sum of distinct powers of two, that is, as a sum
  of a subset of the integers $2^0 = 1$, $2^2 = 2$, $2^2 = 4$, and so
  on. [Hint: For the inductive step, separately consider the case
  where $k + 1$ is even and where it is odd.  When it is even, note that
  $\frac{k + 1}{2}$ is an integer.]

\end{questions}
\end{document}

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