\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage[plain,linesnumbered]{algorithm2e} %algo2e for compatibility

\title{Recitation 12}
\author{Taylor Spangler}

\begin{document}
\maketitle
\begin{itemize}
\item (3 min max) Questions about last week's quiz?
\item Questions about lecture / homework so far?
\item MAPLE!!!!
\item Induction:Let's try a strong induction proof.\\
\begin{center}
Show that if $n\in \mathbb{N}$ then $12\mid (n^4 - n^2)$.
\end{center}
\begin{enumerate}
\item \textbf{Base Case:}
\begin{enumerate}
\item $n$ = 1: $1^4-1^2 = 0 = 12*0$ so $P(1)$ is true.
\item $n = 2: 2^4 - 2^2 = 16 - 4 = 12 = 12*1$ so $P(2)$ is true.
\item $n = 3: 3^4 - 3^2 = 81 - 9 = 72 = 12*6$ so $P(3)$ is true.
\item $n = 4: 4^4 - 4^2 = 256 - 16 = 240 = 12*20$ so $P(4)$ is true.
\item $n = 5: 5^4 - 5^2 = 625 - 25 = 600 = 12*50$ so $P(5)$ is true.
\item $n = 6: 6^4 - 6 ^2 = 1296 - 36 = 1260 = 12 * 105$ so $P(6)$ is true
\end{enumerate}
\item \textbf{Strong Inductive Hypothesis} Let $k \geq 6 \in \mathbb{N}$ and assume that $12\mid (m^4 - m^2)$ for $1\leq m \leq k$ where $m\in \mathbb{N}$.
\item Let $i = k-5$, then we can assume $P(i)$ holds. Clearly $i+6 = k+1$.
\item $(i+6)^4 - (i+6)^2 = (i^4 + 24i^3+180i^2 + 864i + 1296) - (i^2 +12i + 36) = (i^4-i^2) + 24i^3+180i^2 + 852i+1260$
\item Clearly $i^4-i^2 = 12*t$.
\item We can also see that the remaining portion can be rewritten as $12(2i^3 + 15i^2+71i+105)$.
\item Then we have that $(k+1)^4-(k+1)^2 = 12t + 12(2i^3 + 15i^2+71i+105) = 12*(t+2i^3 + 15i^2+71i+105)$
\item Then we have that $12\mid (k+1)^4-(k+1)^2$.
\end{enumerate}

\item Algorithms - Greedy algorithm for optimal change making:
\begin{itemize}
\item Start with the largest value coin, then as the value remaining decreases below that of the largest value coin, begin using smaller values:
\begin{itemize}
\item Example make change for 84 cents
\item Pick 25 we still have 59 cents
\item Pick 25, we still have 34 cents
\item Pick 25, we still have 9 cents
\item Can't pick 10, pick 5 we still have 4 cents
\item ...eventually picking 4 pennies.
\item Total of 8 coins
\end{itemize}
\item Is this algorithm correct (sound)? No, suppose we had a 21 cent value coin...this algorithm would give 8 coins (as above), but the optimal would be 4-21 cent coins. (it is sound if we do limit ourselves to the standard US coins though)
\item Is this algorithm complete? It will always give an answer, even if it has to use pennies
\item Is this algorithm finite? Yes, it will never take an infinite amount of steps.

\end{itemize}
\item Algorithm 2e...let's write this algorithm using algorithm 2e
\begin{algorithm}

\caption{makeChange(n)}
$C\leftarrow \{100,25,10,5,1\}$\\
$S\leftarrow \emptyset$  //cointains solution\\
$t\leftarrow 0$; //contains the sum of elts in $S$\\

\While{ $t\neq n$ }{
	$x\leftarrow$ largest elt in $C$ such that $x+t \leq n$
	\if{no such elt}{
		return \begin{quote} no solution \end{quote}
	}\fi
	$S\leftarrow S\cup \{$coin of value $x\}$
	$t\leftarrow t+x$

}
Return $S$

\end{algorithm}
\item Is this algorithm efficient in terms of the running time?
\begin{itemize}
\item Running time:
\item So this requires at most $n$ iterations through the loop. So one might think that this is linear.
\item However, the input to the function is $n$, which is of size $\log(n)$.
\item So since $n = 2^{\log(n)}$ then we get exponential time with respect to the input.
\end{itemize}
\end{itemize}

\end{document}