solution.pdf

solution.tex

\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}