%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}


\begin{document}
% Do not modify 


%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\begin{textblock*}{30cm}(-1.7cm,-2.3cm)
\noindent {\large CS 381-Fall 2019} \\
\noindent {\large Name: } \\
\noindent {\large Purdue ID: } \\
\noindent {\large Date: \today}
\end{textblock*}

\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 1} \\ 
\textbf{Due Date: September 03, 2019 at 11:59PM on Gradescope.} \\
\textbf{Instructor: Jeremiah Blocki}\\
\end{center}

\subsection*{Homework Guideline Reminders}
\begin{itemize}
    \item Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures.
    \item Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded.
\end{itemize}

%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1 (25 points)}

Use mathematical induction (either weak or strong) to show the following statements:
\begin{enumerate}[label=\textbf{(\alph*)}]
\item $n! > \pi^n$ for all integers $n \geq 7$.
\item $\sum_{i = 1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}$ for all integers $n \geq 1$.
\item Any integer $n \geq 2$ can be expressed as the product of 1 or more prime numbers.
\end{enumerate}

\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\

\subsection*{Question 2 (25 points)}
\begin{enumerate}[label=\textbf{(\alph*)}]
    \item Rank the following functions representing running times from smallest to largest (in terms of growth rate with respect to $n$). Group functions together if they are in the same equivalence class (i.e. $f(n)$ and $g(n)$ are in the same equivalence class if $f(n) = \Theta(g(n))$). Logarithms are base 2 unless stated otherwise. You only need to show the final ordering with equivalence classes, no need to explain your answers (except those in part b).
    \begin{center}
        $(n+1)!$ , $8^{\log n}$ , $5\log n$ , $n\log (n^3)$ , $3^{n+2}$ , $3^{n / 2}$ , $\sqrt{n} + (\log n)^5$ , $\log (\log n)^5$ , $0.9^n$ , $\frac{\log n}{\log \log n}$ , $(\sqrt{2})^{\log n}$ , $2^n$ , $n^2 (\log n)^4 + 2n^3$ , $3^{n-3}$ , $\log \log (n+1)$ , $\log(4n^3)$
    \end{center}
    
    \item Show your complete work when comparing the following function pairs. Provide the $C$ and $k$ values in the formal definition when asserting a big O, $\Omega$, or $\Theta$ relationship (e.g. $f(n)$ is O($g(n)$) if there exists $C > 0$ and $k \geq 0$ such that $f(n) \leq Cg(n)$ for all $n \geq k$).
    \begin{enumerate}[label=(\roman*)]
        \item $3^{n / 2}$ vs. $2^n$
        \item $8^{\log n}$ vs. $n^2 (\log n)^4 + 2n^3$
        \item $(\sqrt{2})^{\log n}$ vs. $\sqrt{n} + (\log n)^5$
    \end{enumerate}
\end{enumerate}

\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\

\subsection*{Question 3 (25 Points)}
How many times is function $F$ called in each code segment? Clearly explain your answer and express the bounds in terms of $n$ in big-O notation.

\begin{enumerate}[label=\textbf{(\alph*)}]
\item Code Segment:

\begin{algorithm}[H]
\caption{Code Segment 1}
\label{alg:segment1}
\begin{algorithmic}[1]
    \For{($i = n$; $i > 1$; $i = i/3$)}
        \For{($j = 0$; $j < n$; $j=j+1$)}
            \State{F(i,j)}
        \EndFor
    \EndFor
\end{algorithmic}
\end{algorithm}

\item Code Segment:

\begin{algorithm}[H]
\caption{Code Segment 2}
\label{alg:segment1}
\begin{algorithmic}[1]
    \For{($i = 0$; $i < n^2$; $i = i + 1$)}
        \For{($j = 0$; $j < n$; $j = j + 3$)}
            \For{($k = 0$; $k < j$; $k = k + 1$)}
                \State{F(i, j, k)}
            \EndFor
        \EndFor
    \EndFor
\end{algorithmic}
\end{algorithm}

\end{enumerate}

\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\

\subsection*{Question 4 (25 Points)}
Evaluate the following sum exactly in terms of $n$ and $m$.
$$\sum_{i = 1}^n \sum_{j = 1}^m \left(2(j - 1) + \frac{i^2}{2^{j}}\right)$$
\medskip

\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\

\end{document}