\documentclass{article}

% \usepackage{minted} % Good for syntax highlighting but complex to install
% \usepackage{verbose} % Allows you to write code directly but no syntax highlighting
% Algorithm packages for ...
\usepackage{amsmath}
\usepackage{algorithm}  % the algorithm environment (similar to a figure environment)
\usepackage{algorithmicx} % for algorithmic environment with commands useful in pseudo-code
\usepackage[noend]{algpseudocode} % Additional commands such as \Function{}{}
% Additional packages
\usepackage{fullpage,latexsym,amsmath,amsfonts}
\usepackage{enumerate} % List package
% \input{macros.tex}
\newcounter{problemnumber}
\newenvironment{problem}{
    {\vskip 0.1in \noindent
        \bf Problem~\addtocounter{problemnumber}{1}\arabic{problemnumber}:}
    }{}
\newenvironment{solution}{
    {\vskip 0.1in \noindent
        \bf Solution~\arabic{problemnumber}
    }
}
{\ \newline\smallskip\lineacross\smallskip}
\newcommand{\lineacross}{\noindent\mbox{}\hrulefill\mbox{}}

\title{CS 141 Assignment 1}
\author{Daniel Stinson-Diess 861266420} % Replace with your name and SID


\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
The Fibonacci numbers are the numbers in the following integer
sequence.
\smallskip

\begin{center}
    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
\end{center}

\noindent In  mathematical  terms,  the  sequence  F  n  of  Fibonacci  numbers  is  defined  by  the  recurrence relation:
\smallskip

\begin{center}
    $F_n = F_(n-1) + F_(n-2)$, where $F_0 = 0$, and $F_1 = 1$.
\end{center}

\noindent Discuss the correctness of the following algorithms that calculate Fibonacci numbers:

\end{problem}
\begin{solution}

\begin{enumerate}
    \item The first algorithm is incorrect because does not have any base cases in the recursive function so this will endlessly subtract the values on \emph{n} going into the negative integers and under flowing back to the vary large integers until a stack overflow is reached causing the program to cease execution.

    \item The second algorithm correctly generates the Fibonacci numbers. This can be shown using a loop invariant which is:

    \item The third algorithm is incorrect because it generates the wrong values for the Fibonacci sequence. The error in the algorithm is that within the for loop, the order in which variable \emph{b}, and \emph{a} are assigned should be reversed, and that correction would correctly return the Fibonacci number for \emph{n}
\end{enumerate}

\end{solution}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
(20 points) Is the following statement true or false?

$$ 3^n = \Theta(2^n)$$

\noindent Justify your answer using the basic definition of the $\Theta$-notation.
\end{problem}

\begin{solution}
\vskip 0.1in

\noindent $\Theta$ is a tight asymptotic bound on the function, implying both a $O(2^n)$ and $\Omega(2^n)$. With an upper-bound of $2^n$ on the function $3^n$ this is clearly false because for no choice for the constant \emph{c} will the statement: $3^n \leq c*f(n)$ for sufficiently large values of \emph{n}.
\end{solution}
\newpage

\begin{problem}
(20 points) Give a tight bound (using the big-theta notation) on the time complexity of following method as a function of n.  For simplicity, you can assume n to be a power of two.
\begin{algorithm}[h]
    \caption{WeirdLoop}
    \begin{algorithmic}[1]
        \Function{WeirdLoop}{$n: \mbox{\bf integer}$}
            \State $i \leftarrow n$
            \While{$i \geq 1$}
                \For{$j \leftarrow 1 \text{\textbf{ to }} i$}
                    \State $k \leftarrow 1$
                    \While{$k \leq n$}
                        \State $k \leftarrow 2k$
                    \EndWhile
                    \State $ i \leftarrow i/2$
                \EndFor
            \EndWhile
        \EndFunction
    \end{algorithmic}
\end{algorithm}
\end{problem}
\begin{solution}
 $$T(n) = \Theta(n*log^2(n))$$

\begin{itemize}
    \item The outer while loop will run a total of log(n) times
    \item The for loop will run for a worst case of n times
    \item The inner while loop will also run for a worst case of log(n) times
\end{itemize}
\end{solution}
\newpage


\begin{problem}
(20 points) Order the following list of functions by the big-Oh notation, i.e.,rank them by order of growth. Group together (for example, by underlining) those functions
that are big-Theta of one another. Logarithms are base two unless indicated otherwise.



\end{problem}

\begin{solution}
\vskip 0.1in

\end{solution}
\newpage

\begin{problem}
(20 points) Given \emph{n} non-negative integers $a_1$, $a_2$, ... $a_n$, where each represents a point at coordinate $(i, a_i)$. \emph{n} vertical lines are drawn such that the two endpoints of line \emph{i} is at $(i, a_i)$ and $(i,0)$.  Find two lines, which together with x-axis forms a container, such that the container contains the most water.

\begin{enumerate}
    \item  Solve  the  problem  with  brute-force  approach.   What  is  the  time  complexity  of  this approach?
    \item Is there any better solution? If so, describe your solution with time complexity analysis.
\end{enumerate}

\noindent \emph{Note:} You may not slant the container and \emph{n} is at least 2.
\end{problem}

\begin{solution}
\vskip 0.1in

\end{solution}

\end{document}