Skip to content

Instantly share code, notes, and snippets.

@jdavis
Last active December 25, 2015 03:19
Show Gist options
  • Save jdavis/6909428 to your computer and use it in GitHub Desktop.
Save jdavis/6909428 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
\documentclass{article}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage[usenames,dvipsnames]{color}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{changepage}
\usepackage{lineno}
\usepackage{algpseudocode}
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in
\linespread{1.1}
\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass\ (\hmwkClassInstructor\ \hmwkClassTime): \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{}
\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}
\setlength\parindent{0pt}
\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}
\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
\stepcounter{#1}
\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}
\setcounter{secnumdepth}{0}
\newcounter{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\nobreak{}
\newenvironment{homeworkProblem}{
\section{Problem \arabic{homeworkProblemCounter}}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}
\newcommand{\hmwkTitle}{Homework\ \#2}
\newcommand{\hmwkDueDate}{September 23, 2013 at 4:30pm}
\newcommand{\hmwkClass}{CS311}
\newcommand{\hmwkClassTime}{Section 3}
\newcommand{\hmwkClassInstructor}{Professor Lathrop}
\newcommand{\hmwkAuthorName}{Josh Davis}
\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}
\vspace{3in}
}
\author{\textbf{\hmwkAuthorName}}
\date{}
\begin{document}
\maketitle
\pagebreak
\begin{homeworkProblem}
Using a loop invariant, prove that the following property holds for
\(MAX\):
\[
\forall{0 \leq i < n},\ list[i] \leq MAX(list)
\]
\textbf{Solution}
\begin{proof}
To prove the following property holds, we will use the following loop
invariant:
\\
\begin{adjustwidth}{2.5em}{0pt}
When looping, of all of the elements in the range \(list[0 \hdots
i]\), \(maxValue\) will contain the the value that is the largest
element in the range of elements.
\\
\end{adjustwidth}
By proving the loop invariant, it will prove the correctness of
the function \(MAX(list)\). Thus the property will hold.
\\
\textbf{Initialization}
At the beginning of the loop, \(i = 0\). Since \(maxValue = list[0]\),
there is only one value in the range of elements. It is trivially true
that the max value of a range with 1 element is always that element.
Thus the the loop invariant holds.
\\
\textbf{Maintenance}
During each iteration of the while loop on line 3, the value of
\(list[i]\) is compared to \(maxValue\). If \(list[i] > maxValue\),
then \(maxValue = list[i]\).
\\
Since this happens each loop of the iteration, everytime \(i\) is
incremented on line 7, the range of elements consists of \(list[0
\hdots i]\). Thus since \(i\) is being incremented by one, the range is
growing by one everytime. Since \(maxValue\) is the largest element in
the range \(list[0 \hdots i - 1]\), we just need to compare the value
at \(list[i]\) to see if we need to update \(maxValue\).
\\
This is exactly what the loop invariant says, thus it proves the
maintenance step of the loop invariant.
\\
\textbf{Termination}
When the loop terminates, it terminates when \(i < n\). Since \(i\) is incremented
every iteration in the while loop on line 7, when \(i = n\) the loop will stop.
\\
Since \(n\) is the length of the array, it is easy to tell that when
\(i = n\), all items in \(list\) have been iterated over and thus
\(maxValue\) will be set to the maximum value in the whole array from
lines 4--5.
\\
Since this corresponds to the termination step of the loop invariant,
it is easy to see that the loop invariant holds.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Prove that a tree with \(n\) vertices has precisely \(n - 1\) edges.
\begin{proof}
To prove that a tree with \(n\) vertices has precisely \(n - 1\) edges, we will use induction.
\\
\textbf{Base}
First consider the simplest possible tree, a tree with
\(n = 0\) vertices. Since the tree consists of just one vertex, there
are no edges to other vertices and a tree cannot have a cycle. The
number of edges is \(0\) or \(n - 1 = 0\). Thus it holds for the base
case.
\\
\textbf{Step}
We want to prove that for a tree with \(n + 1\) vertices, the tree will
also have \((n + 1) - 1\) edges.
\\
Consider a tree, \(T_0\) with \(n\) vertices. We can create a new tree,
\(T\) by taking \(T_0\) and adding one vertex to it. This would give \(n + 1\)
vertices. Because we'd need to connect the vertice to \(T_0\), the
number of edges would then be:
\[
\mbox{edges} = T + 1
\]
We know this because a tree must be connected and have no cycles. By
assuming the induction hypothesis:
\[
\begin{split}
\mbox{edges} &= T + 1
\\
&= (n - 1) + 1
\\
&= (n + 1) - 1
\end{split}
\]
Thus we have shown that a tree with \(n + 1\) vertices has exactly \((n
+ 1) - 1\) edges.
\end{proof}
\end{homeworkProblem}
\begin{homeworkProblem}
Prove that \(6n^4 + 2n^3 + n + 12 \in \Theta(n^4)\).
\begin{proof}
To prove that \(6n^4 + 2n^3 + n + 12 \in \Theta(n^4)\), we must show
the following:
\[
\exists c_1 \exists c_2 \forall n \geq n_0,\ {c_1 \cdot g(n) \leq
f(n) \leq c_2 \cdot g(n)}
\]
For the first inequality, it is easy to see that \(n^4 \leq c_1 \cdot
(6n^4 + 2n^3 + n + 12)\) even for \(c_1 = 1\) and \(n_0 = 1\).
\\
Now we must show the second part of the inequality:
\[
\begin{split}
6n^4 + 2n^3 + n + 12 &=
\\
&\leq 6n^4 + 2n^4 + n^4 + 12n^4
\\
&= 24n^4
\\
&\leq c_2 \cdot n^4
\end{split}
\]
when \(c_2 = 24\) and \(n_0 = 1\).
\\
Therefore, since we have found our two constants, \(c_1 = 1\) and \(c_2
= 24\), and constrained \(n_0 = 1\), we have proven the proposition.
Thus the proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Prove a polynomial of degree \(k\), \(a_kn^k + a_{k - 1}n^{k - 1} + \hdots
+ a_1n^1 + a_0n^0\) is a member of \(\Theta(n^k)\) where \(a_k \hdots a_0\)
are nonnegative constants.
\begin{proof}
To prove that \(a_kn^k + a_{k - 1}n^{k - 1} + \hdots + a_1n^1 +
a_0n^0\), we must show the following:
\[
\exists c_1 \exists c_2 \forall n \geq n_0,\ {c_1 \cdot g(n) \leq
f(n) \leq c_2 \cdot g(n)}
\]
For the first inequality, it is easy to see that it holds because no
matter what the constants are, \(n^k \leq a_kn^k + a_{k - 1}n^{k - 1} +
\hdots + a_1n^1 + a_0n^0\) even if \(c_1 = 1\) and \(n_0 = 1\). This
is because \(n^k \leq c_1 \cdot a_kn^k\) for any nonnegative constant,
\(c_1\) and \(a_k\).
\\
Taking the second inequality, we prove it in the following way.
By summation, \(\sum\limits_{i=0}^k a_i\) will give us a new constant,
\(A\). By taking this value of \(A\), we can then do the following:
\[
\begin{split}
a_kn^k + a_{k - 1}n^{k - 1} + \hdots + a_1n^1 + a_0n^0 &=
\\
&\leq (a_k + a_{k - 1} \hdots a_1 + a_0) \cdot n^k
\\
&= A \cdot n^k
\\
&\leq c_2 \cdot n^k
\end{split}
\]
where \(n_0 = 1\) and \(c_2 = A\). \(c_2\) is just a constant. Thus the
proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Give an appropriate positive constant \(c\) such that \(f(n) \leq c \cdot
g(n)\) for all \(n > 1\).
\begin{enumerate}
\item \(f(n) = n^2 + n + 1\), \(g(n) = 2n^3\)
\item \(f(n) = n\sqrt{n} + n^2\), \(g(n) = n^2\)
\item \(f(n) = n^2 - n + 1\), \(g(n) = n^2 / 2\)
\end{enumerate}
\textbf{Solution}
We solve each solution algebraically to determine a possible constant
\(c\).
\\
\textbf{Part One}
\[
\begin{split}
n^2 + n + 1 &=
\\
&\leq n^2 + n^2 + n^2
\\
&= 3n^2
\\
&\leq c \cdot 2n^3
\end{split}
\]
Thus a valid \(c\) could be when \(c = 2\).
\\
\textbf{Part Two}
\[
\begin{split}
n^2 + n\sqrt{n} &=
\\
&= n^2 + n^{3/2}
\\
&\leq n^2 + n^{4/2}
\\
&= n^2 + n^2
\\
&= 2n^2
\\
&\leq c \cdot n^2
\end{split}
\]
Thus a valid \(c\) is \(c = 2\).
\\
\textbf{Part Three}
\[
\begin{split}
n^2 - n + 1 &=
\\
&\leq n^2
\\
&\leq c \cdot n^2/2
\end{split}
\]
Thus a valid \(c\) is \(c = 2\).
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Find \(f(n)\) and \(g(n)\) that satisfy the following relationships. Write
"None" if neither exist.
\begin{enumerate}
\item \(f(n) = o(g(n))\) and \(f(n) \neq \Theta(g(n))\)
\item \(f(n) = \Theta(g(n))\) and \(f(n) = o(g(n))\)
\item \(f(n) = \Theta(g(n))\) and \(f(n) \neq O(g(n))\)
\item \(f(n) = \Omega(g(n))\) and \(f(n) \neq O(g(n))\)
\end{enumerate}
\textbf{Solutions}
\\
\textbf{Part One} \(f(n) = n\) and \(g(n) = n^2\). \(f(n)\) is dominated by
\(g(n)\) yet \(g(n)\) isn't a tight bound on \(f(n)\).
\\
\textbf{Part Two} None. Any function \(f(n)\) that is tightly bounded by
\(g(n)\) cannot be dominated by the same function.
\\
\textbf{Part Three} None. If \(f(n)\) is bounded tightly with \(g(n)\) (Big
Theta definition), then there is no way it isn't bounded asymptotically by
\(g(n)\) which is what Big Oh means. Big Theta is essentially a stronger
statement than Big Oh and thus a subset.
\\
\textbf{Part Four} \(f(n) = n^2\) and \(g(n) = n\). Big Theta is a lower
bound thus \(f(n)\) is asymptotically greater than \(g(n)\). However it
doesn't say anything about \(f(n)\)'s upper bound.
\end{homeworkProblem}
\begin{homeworkProblem}
Prove that if \(f_1(n) \in O(g_1(n))\) and \(f_2(n) \in O(g_2(n))\), then
\(f_1(n) + f_2(n) \in O(g_1(n) + g_2(n))\).
\begin{proof}
To prove the above proposition, we must show that there exists a \(c\)
and \(n_0\) such that:
\[
f_1(n) + f_2(n) \leq c \cdot (g_1(n) + g_2(n))
\]
Since \(f_1(n) \in O(g_1(n))\), there exists a \(c_1\) and \(n_1\).
Also, since \(f_2(n) \in O(g_2(n))\), there exists a \(c_2\) and
\(n_2\).
\\
\[
\begin{split}
f_1(n) + f_2(n) &\leq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)
\\
&\leq (c_1 + c_2) \cdot g_1(n) + (c_1 + c_2) \cdot g_2(n)
\\
&= (c_1 + c_2) \cdot (g_1(n) + g_2(n))
\\
&\leq c \cdot (g_1(n) + g_2(n))
\end{split}
\]
Since \(c = c_1 + c_2\), it is just a constant. By choosing \(n_0\) in
a similar fashion, it is easy to see that the propsition holds and thus
the proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Suppose \(f_1 \in \Theta(g_1)\) and \(f_2 \in \Theta(g_2)\). Prove that
\(f_1/f_2 \in \Theta(g_1/g_2)\).
\begin{proof}
To prove the above proposition, we must show that there exists a
\(c_0\), \(c_1\) and \(n_0\) such that:
\[
c_0 \cdot \dfrac{g_1(n)}{g_2(n)} \leq \dfrac{f_1(n)}{f_2(n)} \leq c_1 \cdot \dfrac{g_1(n)}{g_2(n)}
\]
Since \(f_1(n) \in \Theta(g_1(n))\), there exists a \(c_2\),
\(c_3\) and \(n_{1}\). Also, since \(f_2(n) \in \Theta(g_2(n))\),
there exists a \(c_4\), \(c_5\) and \(n_2\).
\\
For the first part of the inequality:
\[
\begin{split}
\dfrac{c_2 \cdot g_1(n)}{c_4 \cdot g_2(n)} &= \left(\dfrac{c_2}{c_4}\right) \cdot \dfrac{g_1(n)}{g_2(n)}
\\
&= c_0 \cdot \dfrac{g_1(n)}{g_2(n)}
\\
&\leq \dfrac{f_1(n)}{f_2(n)}
\end{split}
\]
For the second part of the inequality:
\[
\begin{split}
\dfrac{f_1(n)}{f_2(n)} &\leq \dfrac{c_3 \cdot g_1(n)}{c_5 \cdot g_2(n)}
\\
&= \left(\dfrac{c_3}{c_5}\right) \cdot \dfrac{g_1(n)}{g_2(n)}
\\
&\leq c_1 \cdot \dfrac{g_1(n)}{g_2(n)}
\end{split}
\]
Since \(c_0\), \(c_1\) are both constants, we have shown that the
proposition holds. Thus the proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Suppose \(f(n) \in O(g(n))\).
\\
\textbf{Part One}
Prove that \(f(n) + g(n) \in O(g(n))\).
\begin{proof}
We will show that \(f(n) + g(n) \in O(g(n))\) by using the definition of Big-Oh.
Suppose that \(f(n) \in O(g(n))\). That means \(\exists c_0 \exists n_0
\forall n \geq n_0,\ f(n) \leq c_0 \cdot g(n)\).
\\
Now we must just show that \(\exists c_1 \exists n_0 \forall n \geq
n_0\ f(n) + g(n) \leq c_1 \cdot g(n)\).
\\
By taking \(f(n) \leq c \cdot g(n)\), we can add \(g(n)\) to both sides
giving us:
\[
f(n) + g(n) \leq c \cdot g(n) + g(n)
\]
Since \(c\) is just a constant, this gives us the following:
\[
f(n) + g(n) \leq (c + 1) \cdot g(n)
\]
Which means our \(n_0\) stays the same but our constant just becomes
\(c_1 = c_0 + 1\). Since this proves what we wished to prove, our proof
is complete.
\end{proof}
\textbf{Part Two}
Prove that \(O(f(n) + g(n)) = O(g(n))\).
\begin{proof}
To prove that \(O(f(n) + g(n)) = O(g(n))\), we need to show that
\(O(f(n) + g(n)) \subseteq O(g(n))\) and \(O(g(n)) \subseteq O(f(n) +
g(n))\) because Big-Oh notation creates a set of functions.
\\
First, we must show that \(O(f(n) + g(n)) \subseteq O(g(n))\) We can do
this by proving that for every \(h(n) \in O(f(n) + g(n))\), it will
exist in \(O(g(n))\) or more formally: there exists a \(c\) and \(n_0\)
such that for all \(n \geq n_0\), \(h(n) \leq c \cdot g(n)\).
\\
Suppose that \(f(n) \in O(g(n))\) and \(h(n) \in O(f(n) + g(n))\). This
means that for \(f(n)\), there exists a \(c_0\) and \(n_1\) such that
for all \(n \geq n_1\), \(f(n) \leq c_0 \cdot g(n)\). This also means
that for \(h(n)\), there exists a \(c_1\) and \(n_2\) such that for
all \(n \geq n_2\), \(h(n) \leq c_1 \cdot (f(n) + g(n))\).
\\
Using this, we get the following:
\[
\begin{split}
h(n) &\leq c_1 \cdot ((f(n) + g(n)))
\\
&\leq c_1 \cdot (c_0 \cdot g(n) + g(n))
\\
&= c_1 c_0 \cdot g(n) + c_1 \cdot g(n)
\\
&= (c_1 c_0 + c_1) \cdot g(n)
\\
&\leq c \cdot g(n)
\end{split}
\]
If we just let \(c = c_1 c_0 + c_1\) and \(n_0 = n_2 n_1 + n_2\), then
we can see that \(h(n) \in O(g(n))\) and the first part of the proof is
complete.
\pagebreak
Second, we must show that \(O(g(n)) \subseteq O(f(n) + g(n))\) We can
do this by proving that for every \(h(n) \in O(g(n))\), it will exist
in \(O(f(n) + g(n))\), or more formally: there exists a \(c\) and \(n_0\)
such that for all \(n \geq n_0\), \(h(n) \leq c \cdot (f(n) + g(n))\)
\\
Suppose that \(f(n) \in O(g(n))\) and \(h(n) \in O(g(n))\). This means
that for \(f(n)\), there exists a \(c_0\) and \(n_1\) such that for all
\(n \geq n_1\), \(f(n) \leq c_0 \cdot g(n)\). This also means that for
\(h(n)\), there exists a \(c_1\) and \(n_1\) such that for all \(n \geq
n_2\), \(h(n) \leq c_1 \cdot g(n)\).
\\
Using this, we get the following:
\[
\begin{split}
h(n) &\leq c_1 \cdot g(n)
\\
&\leq (c_0 + c_1) \cdot g(n)
\\
&= c_0 \cdot g(n) + c_1 \cdot g(n)
\\
&\leq c_0 \cdot f(n) + c_1 \cdot g(n)
\\
&\leq (c_0 + c_1) \cdot (f(n) + g(n))
\\
&\leq c \cdot (f(n) + g(n))
\end{split}
\]
If we let \(c = c_0 + c_1\) and \(n_0 = n_1 + n_2\), then we can
see that \(h(n) \in O(f(n) + g(n))\). Thus since we have proven each
side of the equality of sets, our proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Prove or disprove: Big Oh defines an equivalence relation on the set of all
functions: \(f : \mathbb{N} \to \mathbb{R}\).
\\
\textbf{Counterexample}
Let \(f(n) = n\) and \(g(n) = n^2\).
\\
According to the definition of an equivalence relation, the relation
creates essentially partitions where each element belongs to one and only
one partition.
\\
More formally, the properties that this implies are the following:
\begin{enumerate}
\item Reflexivity: \(a R a\).
\item Symmetry: if \(a R b\), then \(b R a\).
\item Transitivity: if \(a R b\) and \(b R c\), then \(a R c\).
\end{enumerate}
Using the second property of an equivalence relation, it is easy to see
that Big-Oh isn't an equivalence relation because since \(n \in O(n^2)\), it
should follow that \(n^2 \in O(n)\), but we know that isn't the case. Thus
it is a counterexample and the proposition is false.
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Cover a grid of squares with \(2^n\) rows and \(2^n\) columns, which means
\({(2^n)}^2\) squares in the grid. The only thing you can use to cover it
is L-shaped pieces.
\\
Prove it is possible to cover for any \(n\) using induction.
\begin{proof}
\textbf{Base}
To prove the base case, we will prove that a grid with squares
can be covered when \(n = 0\) and \(n = 1\) for comprehensiveness.
\\
When \(n = 0\), the case is trivial. The number of rows equals \(2^n =
2^0 = 1\), the columns also equal \(2^n = 2^0 = 1\). This is just a
grid with one tile. This requires 0 L-shaped pieces. Only one square is
uncovered and there are no overlaps. The adversary must then choose
that square. Thus the base when \(n = 0\) is satisfied.
\\
When \(n = 1\), the number of rows and columns both are \(2^n = 2^1 =
2\). This is just a square with 4 total squares.
\\
Our adversary can then has four options of which to choose. It can
either choose the top left, top right, bottom left, or bottom right.
\\
Without loss of generality, in all cases, the square that is chosen can
be left uncovered by placing just one L-shaped piece such that it is
rotated leaving three squares covered and the chosen square uncovered.
Thus it can be seen that when \(n = 1\), the base case is still
satisfied.
\\
\textbf{Step}
In the step, we can assume that for \(n\) the problem of covering the
grid of \({(2^n)}^2\) is solvable. By assuming that, we will show that
the problem is also solvable when \(n = n + 1\), thus completing the
induction and proving the problem.
\\
When \(n = n + 1\), that means there will be \({(2^{n + 1})}^2\)
squares in the grid. This means when the adversary picks his square,
there will be \({(2^{n + 1})}^2 - 1\) squares. Since there are 3 squares
in the L-shaped piece:
\[
\begin{split}
{(2^{n + 1})}^2 - 1 &= (2^{n + 1}) \cdot (2^{n + 1}) - 1
\\
&= 4^{n + 1} - 1
\\
&= (4_0 \cdot 4_1 \cdot 4_2 \cdot \hdots \cdot 4_{n} \cdot 4_{n + 1}) - 1
\\
&= (4 - 1) \cdot (4_1 \cdot 4_2 \cdot \hdots \cdot 4_{n} \cdot 4_{n + 1})
\\
&= 3 \cdot (4_1 \cdot 4_2 \cdot \hdots \cdot 4_{n} \cdot 4_{n + 1})
\\
&= 3k
\end{split}
\]
where \(k \in \mathbb{Z}\). Thus it is divisible by three meaning that we
can completely cover the grid of squares with our L-shape tiles.
\\
The grid also contains \(4^{n}\) 4-by-4 grids. By greedily covering it
starting with the square the adversary picks, it will completely cover
the grid. Thus the proposition holds for \(n = n + 1\) and the proof by
induction is complete.
\end{proof}
\end{homeworkProblem}
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment