\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fullpage}
\usepackage{hyperref}

\title{Week 13 Recitation}
\author{Robert Woodward}

\begin{document}
\maketitle

\begin{itemize}
\item Questions about lecture / homework so far?

\item
How to use Algorithm2e package for writing algorithms.  See algo\_example.tex for what was done in class, or visit \url{http://www.ctan.org/tex-archive/macros/latex/contrib/algorithm2e/} to see the package documentation.

\begin{enumerate}
\item
Start with an empty document

\item
Write the algorithm for finding the maximum element in a finite sequence (Slide~14 in Class Slides).  [Only \textbackslash usepackage\{algorithm2e\}]
\begin{itemize}
\item Always state the input (using \textbackslash KwIn) and output (using \textbackslash KwOut)
\item How to use \textbackslash For, \textbackslash If
\item Always end with a ``return'' (using \textbackslash Return) even when not returning any values
\item Always use \textbackslash gets for assignments (Note: Always declare and initialize your local variables)
\item End each line with \textbackslash ;
\item Adding a \textbackslash caption to describe the algorithm, and using \textbackslash sc to denote the algorithm name
\item Adding \textbackslash DontPrintSemicolon (Or \textbackslash dontprintsemicolon depending on the algorithm2e version installed) will remove
the semicolons from the end of the lines
\end{itemize}

\item
Change the package to: \textbackslash usepackage[linesnumbered]\{algorithm2e\} -- Now line numbers appear.  You should always number your lines for quick referral.

\item Change the package to: \textbackslash usepackage[linesnumbered,ruled]\{algorithm2e\} -- The caption moves to the top, and it adds horizontal lines
to separate the algorithm

\item Change the package to: \textbackslash usepackage[linesnumbered,ruled,vlined]\{algorithm2e\} -- The ``Ends'' for the if statement and for
loop do away (Helps save on space).

\item
Write the algorithm for the greedy change-making (Slide~19 in Class Slides).
\end{enumerate}

Also note, that you should use common functions and operands such as {\sc Union}, {\sc PowerSet}, etc. as often as needed, unless you are asked to define them.

TUG (\TeX\/ Users' Group) is a great resource on learning \LaTeX.
For information on algorithm2e from TUG, visit \url{http://www.tug.org/texlive/Contents/live/texmf-dist/doc/latex/algorithm2e/}.

\item
Rosen 3.3.7 (Similar to Homework problem 3.3.8)

\begin{enumerate}
\item[a)] Evaluate $3x^2 + x + 1$ at $x = 2$ using the algorithm
{\sc Polynomial}, given in the problem description on page 199,
by working through each step of the algorithm showing the values
assigned at each assignment step.

We want to run {\sc polynomial}$(2, 1, 1, 3)$, therefore to show the steps used in the algorithm,
you show the changes in assignments incrementally.

In this problem, we start with the first line:
\begin{itemize}
\item
$power = 1, y = 1$
\end{itemize}

Then, you incrementally show each iteration of $i$ in the for loop, and the changes of $power$ and $y$:
\begin{itemize}
\item
$i = 1, power = 2, y = 3$

\item
$i = 2, power = 4, y = 15$
\end{itemize}

\item[b)] Exactly how many multiplications and additions are used to evaluate
a polynomial of degree $n$ at $x = c$?

Look before the for loop, how many multiplications and additions are there:
\begin{itemize}
\item
Multiplications: 0

\item
Additions: 0
\end{itemize}

Inside of the for loop, how many multiplications and additions are there:
\begin{itemize}
\item
Multiplications: 2

\item
Additions: 1
\end{itemize}


How many times does the for loop iterate: $n$

How many total multiplications and additions are there:
\begin{itemize}
\item
Multiplications: $0 + n \times 2 = 2n$

\item
Additions: $0 + n \times 1 = n$
\end{itemize}

\end{enumerate}

\item
Rosen 3.1.1) List all the steps used by Algorithm 1, on page 169, to find the maximum of the list $\{1,8,12,9,11,2,14,5,10,4\}$.

To show the steps used in an algorithm, you show the changes in assignments
incrementally.

In this problem, we start with line~1 of the {\sc Max} method as defined in algo\_example:
\begin{itemize}
\item
$max = 1$
\end{itemize}
Then, you incrementally show each iteration of $i$ in the for loop of line~2, and the results if $max$ changes:
\begin{itemize}
\item
$i = 2, max = 8$
\item
$i = 3, max = 12$
\item
$i = 4$
\item
$i = 5$
\item
$i = 6$
\item
$i = 7, max = 14$
\item
$i = 8$
\item
$i = 9$
\item
$i = 10$
\end{itemize}

Putting all of this together, the answer would be:\\
$max = 1\\
i = 2, max = 8, \\
i = 3, max = 12, \\
i = 4,\\
i = 5,\\
i = 6,\\
i = 7, max = 14, \\
i = 8,\\
i = 9,\\
i = 10$

\item
Rosen 3.1.31 -- Solution in algo\_example.tex file

Note that there is a difference between:
\begin{itemize}
\item
\textbackslash If with \textbackslash Else: There is an ``End'' after the If, which we do not want!

\item
\textbackslash uIf with \textbackslash Else: There is not an ``End'' after the If, then the Else directly follows.

\item
\textbackslash lIf with \textbackslash lElse: They do not expand the ``If'' and ``Else'' to a second line (Helps save on space).
\end{itemize}

\item
Rosen 3.1.53b) Use the greedy algorithm (Algorithm~6 on page 175) to make change using quarters, dimes, nickels, and pennies for 69 cents

$c_1 = 25$, $c_2 = 10$, $c_3 = 5$, $c_4 = 1$.

$n = 69$

$C = \emptyset, \\
i = 1, C = \{25\}, n = 44 \\
i = 1, C = \{25,25\}, n = 19 \\
i = 2, C = \{25,25,10\}, n = 9 \\
i = 3, C = \{25,25,10,5\}, n = 4 \\
i = 4, C = \{25,25,10,5,1\}, n = 3 \\
i = 4, C = \{25,25,10,5,1,1\}, n = 2 \\
i = 4, C = \{25,25,10,5,1,1,1\}, n = 1 \\
i = 4, C = \{25,25,10,5,1,1,1,1\}, n = 0$

\item
Rosen 3.1.55b) Use the greedy algorithm (Algorithm~6 on page 175) to make change using quarters, dimes, and pennies for 69 cents

$c_1 = 25$, $c_2 = 10$, $c_3 = 1$.

$n = 69$

$C = \emptyset, \\
i = 1, C = \{25\}, n = 44 \\
i = 1, C = \{25,25\}, n = 19 \\
i = 2, C = \{25,25,10\}, n = 9 \\
i = 3, C = \{25,25,10,1\}, n = 8 \\
i = 3, C = \{25,25,10,1,1\}, n = 7 \\
i = 3, C = \{25,25,10,1,1,1\}, n = 6 \\
i = 3, C = \{25,25,10,1,1,1,1\}, n = 5 \\
i = 3, C = \{25,25,10,1,1,1,1,1\}, n = 4 \\
i = 3, C = \{25,25,10,1,1,1,1,1,1\}, n = 3 \\
i = 3, C = \{25,25,10,1,1,1,1,1,1,1\}, n = 2 \\
i = 3, C = \{25,25,10,1,1,1,1,1,1,1,1\}, n = 1 \\
i = 3, C = \{25,25,10,1,1,1,1,1,1,1,1,1\}, n = 0$

\item
(Last 10 minutes) Quiz

\end{itemize}

\end{document}