\newcommand{\ig}[1]{}

\documentclass[12pt,letterpaper]{article}

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

\usepackage[linesnumbered,ruled]{algorithm2e}

\usepackage{hyperref}

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

\begin{document}
\maketitle

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

\item
Rosen 3.1.9, page 177.  A palindrome is a string that reads the same
forward and backwards.  Describe an algorithm for determining whether a string of $n$ characters is a palindrome.

\begin{algorithm}
\KwIn{$a_1a_2a_3\ldots a_n$, a string of length $n$}
\KwOut{If the string is a palindrome}
$answer \gets true$\;
\For{$i \gets 1$ \textbf{to} $\lfloor n/2 \rfloor$}{
  \If{$a_i \not= a_{n+1-i}$}{
    $answer \gets false$\;
  }
}
\Return{$answer$}\;
\caption{{\sc Palindrome}: Checks if a string is a palindrome}
\end{algorithm}

Use the Mathematical Analysis of Algorithms to analyze {\sc Palindrome}'s performance.

Recall the general strategy for the Mathematical Analysis of Algorithms:
\begin{enumerate}
\item
Decide on a parameter(s) for the input, $n$
\item
Identify the basic operation
\item
Evaluate if the elementary operation depends only on $n$
\item
Set up a summation corresponding to the number of elementary operations
\item
Simplify the equation to get as simple of a function $f(n)$ as possible.
\end{enumerate}

For {\sc Palindrome}:
\begin{enumerate}
\item
The input parameter is $n$, the size of the string

\item
The basic operation is the comparison of $a_i$ and $a_{n+1-i}$

\item
The elementary operation depends only on $n$

\item
The summation for the number of elementary operations is: $\sum_{i=1}^{\lfloor n/2 \rfloor} 1$

\item
First, recall that:
$\sum_{i=m}^n 1 = n - m + 1$

Therefore, $\sum_{i=1}^{\lfloor n/2 \rfloor} 1 = \lfloor n/2 \rfloor - 1 + 1 = \lfloor n/2 \rfloor$
\end{enumerate}

\item
Reminder. To prove that $f(n) \in \Delta (g(n))$, we saw three main
techniques:
\begin{enumerate}
\item
Applying the definition:  Specify $n_0$ and $c$ (or $c_1$ and $c_2$).

\item
The limit method: $lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = \begin{cases}
0 & f(n) \in \mathcal{O}(g(n)) \\
c > 0 & f(n) \in \Theta(g(n)) \\
\infty & f(n) \in \Omega(g(n)) \\
\end{cases}$

\item
Applying the rule of L'H\^{o}pital in the limit method:
$lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = lim_{n\rightarrow\infty} \frac{f'(n)}{g'(n)}$.
\end{enumerate}

\item Let $f(n) = 3n^4 + 1$ and $g(n) = n^5 - 100$.  Find a tight bound of the form $f(n) \in \Delta(g(n))$ and prove this
bound formally.

Intuitively we think that $f(n) \in \mathcal{O}(g(n))$ because the highest degree of $f(n)$ is lower than the highest degree of $g(n)$.
Therefore, we want to show $f(n) \in \mathcal{O}(g(n))$.

We need to find:
\begin{itemize}
\item $c \in \mathbb{R}^+$

\item $n_0 \in \mathbb{N}$
\end{itemize}
Such that for every positive integer $n \geq n_0$ we have $f(n) \leq c g(n)$

(Note that for $n \geq 4$, $g(n) \geq 0$ because $4^5 - 100 = 1024 - 100 = 924$.)

$\forall n \geq n_0 = 4$ we have:
$$3n^4 \leq 3n^5 \leq 3n^5 + n^5 - 400 = 4n^5 - 400 = 4(n^5 - 100)$$
Also,
$$1 \leq n^5 - 100$$

Adding up the above two expressions, we get
$$f(n) = 3n^4 + 1 \leq 4(n^5 - 100) + (n^5 - 100) = 5(n^5 - 100) = 5g(n)$$

Therefore, $f(n) \leq 5 g(n)$ $\forall n \geq n_0 = 4$ and $c = 5$.
Consequently, $f(n) \in \mathcal{O}(g(n))$.

\item (Similar to Rosen 3.2, problem 11)
Let $f(n) = 3n^4 + 1$ and $g(n) = \frac{n^4}{2}$. Find a
tight bound of the form $f(n) \in \Delta(g(n))$ and prove this bound
formally.

Intuitively we think that $f(n) \in \Theta(g(n))$ because both $f(n)$ and $g(n)$ have a $n^4$ term as their highest degree.
Therefore, we need to
show:
\begin{enumerate}
\item 
$f(n) \in \mathcal{O}(g(n))$ and
\item
$f(n) \in \Omega(g(n))$.
\end{enumerate}

\begin{enumerate}
\item{\em To show $f(n) \in \mathcal{O}(g(n))$}, we need to find:
\begin{itemize}
\item
$c_1 \in \mathbb{R}^+$

\item
$n_0 \in \mathbb{N}$
\end{itemize}
Such that for every positive integer $n \geq n_0$ we have $f(n) \leq
c_1 g(n)$.

$\forall n \geq n_0 = 1$ we have:
\begin{eqnarray*}
3n^4 = 6{n^4 \over 2}
\end{eqnarray*}
Also,
\begin{eqnarray*}
1 \leq n^4 = 2 {n^4 \over 2}
\end{eqnarray*}
Adding up the above two expressions, we get:
\begin{eqnarray*}
f(n) = 3n^4 + 1 \leq 6{n^4 \over 2} +  2 {n^4 \over 2} = 8 {n^4 \over 2} = 8g(n)
\end{eqnarray*}
Therefore, $f(n) \leq 8g(n)$ $ \forall n \geq
n_0=1 $ and $c_1 = 8$.  Consequently, $f(n) \in \mathcal{O}(g(n))$.

\item{\em To show $f(n) \in \Omega(g(n))$}, we need to find:
\begin{itemize}
\item
$c_2 \in \mathbb{R}^+$

\item
$n_0 \in \mathbb{N}$
\end{itemize}
such that for every integer $n \geq n_0$ we have $f(n) \geq c_2 g(n)$.

For $n_0 \geq 1$, we have:
\begin{eqnarray*}
3n^4 \geq n^4 \geq {n^4 \over 2}
\end{eqnarray*}
Obviously, we have:
\begin{eqnarray*}
1 \geq 0
\end{eqnarray*}

Adding up the above two expressions, we get:
$$f(n) = 3n^4 + 1 \geq {n^4 \over 2} + 0 = {n^4
\over 2} = g(n)$$
Therefore, $f(n) \geq 1g(n)$ $\forall n  \geq n_0=1$ and $c = 1$.  Consequently, $f(n) \in
\Omega(g(n))$ .
\end{enumerate}
Because $f(n) \in \mathcal{O}(g(n))$ and $f(n) \in \Omega(g(n))$, then
$f(n) \in \Theta(g(n))$.

\item
Similar to above, consider instead where $f(n) = 3n^4 - 1$ and $g(n) = \frac{n^4}{2}$. Find a
tight bound of the form $f(n) \in \Delta(g(n))$ and prove this bound
formally.

\begin{enumerate}
\item{\em To show $f(n) \in \mathcal{O}(g(n))$}, it will follow very similar to above.

\item{\em To show $f(n) \in \Omega(g(n))$}, we need to find:
\begin{itemize}
\item
$c_2 \in \mathbb{R}^+$

\item
$n_0 \in \mathbb{N}$
\end{itemize}
such that for every integer $n \geq n_0$ we have $f(n) \geq c_2 g(n)$.

For $n_0 \geq 1$, we have:
\begin{eqnarray*}
3n^4 - 1 = 6 {n^4 \over 2} - 1 = {n^4 \over 2} + 5{n^4 \over 2} - 1 \geq {n^4 \over 2}
\end{eqnarray*}
(Note that, $5 {n^4 \over 2} - 1 \geq 0$ because $n_0 \geq 1$.)

Therefore, we get:
$$f(n) = 3n^4 - 1 \geq {n^4 \over 2} = g(n)$$
Therefore, $f(n) \geq 1g(n)$ $\forall n  \geq n_0=1$ and $c = 1$.  Consequently, $f(n) \in
\Omega(g(n))$ .
\end{enumerate}
Because $f(n) \in \mathcal{O}(g(n))$ and $f(n) \in \Omega(g(n))$, then
$f(n) \in \Theta(g(n))$.

\item (Last 10 minutes) Quiz

\end{itemize}

\end{document}