\documentclass[10pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}





\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother


\usepackage[round]{natbib}
\let\cite\citep



\pagenumbering{gobble}


\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}



\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}









\iflatexml
\documentclass[11pt]{article}
\fi
% \usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts} % Not (yet) supported by LaTeXML.
\usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts}
% \usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts} % Not (yet) supported by LaTeXML.
% \usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts} % Not (yet) supported by LaTeXML.
\usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts}
\usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts}
\usepackage{fullpage,graphicx,latexsym,picinpar,amsbsy,amsmath,amsfonts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%  LETTERS 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\bart}{{\bar t}}

\newcommand{\bfP}{{\bf{P}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                                                                                
\newcommand{\parend}[1]{{\left( #1  \right) }}
\newcommand{\spparend}[1]{{\left(\, #1  \,\right) }}
\newcommand{\angled}[1]{{\left\langle #1  \right\rangle }}
\newcommand{\brackd}[1]{{\left[ #1  \right] }}
\newcommand{\spbrackd}[1]{{\left[\, #1  \,\right] }}
\newcommand{\braced}[1]{{\left\{ #1  \right\} }}
\newcommand{\leftbraced}[1]{{\left\{ #1  \right. }}
\newcommand{\floor}[1]{{\left\lfloor #1\right\rfloor}}
\newcommand{\ceiling}[1]{{\left\lceil #1\right\rceil}}
\newcommand{\barred}[1]{{\left|#1\right|}}
\newcommand{\doublebarred}[1]{{\left|\left|#1\right|\right|}}
\newcommand{\spaced}[1]{{\, #1\, }}
\newcommand{\suchthat}{{\spaced{|}}}
\newcommand{\numof}{{\sharp}}
\newcommand{\assign}{{\,\leftarrow\,}}
\newcommand{\myaccept}{{\mbox{\tiny accept}}}
\newcommand{\myreject}{{\mbox{\tiny reject}}}
\newcommand{\blanksymbol}{{\sqcup}}
                                                                                                                         
\newcommand{\veps}{{\varepsilon}}
\newcommand{\Sigmastar}{{\Sigma^\ast}}
                           
\newcommand{\half}{\mbox{$\frac{1}{2}$}}    
\newcommand{\threehalfs}{\mbox{$\frac{3}{2}$}}   
\newcommand{\domino}[2]{\left[\frac{#1}{#2}\right]}  

%%%%%%%%%%%% complexity classes

\newcommand{\PP}{\mathbb{P}}
\newcommand{\NP}{\mathbb{NP}}
\newcommand{\PSPACE}{\mathbb{PSPACE}}
\newcommand{\coNP}{\textrm{co}\mathbb{NP}}
\newcommand{\DLOG}{\mathbb{L}}
\newcommand{\NLOG}{\mathbb{NL}}
\newcommand{\NL}{\mathbb{NL}}

%%%%%%%%%%% decision problems

\newcommand{\PCP}{\sc{PCP}}
\newcommand{\Path}{\sc{Path}}
\newcommand{\GenGeo}{\sc{Generalized Geography}}

\newcommand{\malytm}{{\mbox{\tiny TM}}}
\newcommand{\malycfg}{{\mbox{\tiny CFG}}}
\newcommand{\Atm}{\mbox{\rm A}_\malytm}
\newcommand{\complAtm}{{\overline{\mbox{\rm A}}}_\malytm}
\newcommand{\AllCFG}{{\mbox{\sc All}}_\malycfg}
\newcommand{\complAllCFG}{{\overline{\mbox{\sc All}}}_\malycfg}
\newcommand{\complL}{{\bar L}}
\newcommand{\TQBF}{\mbox{\sc TQBF}}
\newcommand{\SAT}{\mbox{\sc SAT}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% for homeworks
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\student}[2]{%
{\noindent\Large{ \emph{#1} SID {#2} } \hfill} \vskip 0.1in}

\newcommand{\assignment}[1]{\medskip\centerline{\large\bf CS 111 ASSIGNMENT {#1}}}

\newcommand{\duedate}[1]{{\centerline{due {#1}\medskip}}}     

\newcounter{problemnumber}                                                                                 

\newenvironment{problem}{{\vskip 0.1in \noindent
              \bf Problem~\addtocounter{problemnumber}{1}\arabic{problemnumber}:}}{}

\newcounter{solutionnumber}

\newenvironment{solution}{{\vskip 0.1in \noindent
             \bf Solution~\addtocounter{solutionnumber}{1}\arabic{solutionnumber}:}}
				{\ \newline\smallskip\lineacross\smallskip}

\newcommand{\lineacross}{\noindent\mbox{}\hrulefill\mbox{}}

\newcommand{\decproblem}[3]{%
\medskip
\noindent
\begin{list}{\hfill}{\setlength{\labelsep}{0in}
                       \setlength{\topsep}{0in}
                       \setlength{\partopsep}{0in}
                       \setlength{\leftmargin}{0in}
                       \setlength{\listparindent}{0in}
                       \setlength{\labelwidth}{0.5in}
                       \setlength{\itemindent}{0in}
                       \setlength{\itemsep}{0in}
                     }
\item{{{\sc{#1}}:}}
                \begin{list}{\hfill}{\setlength{\labelsep}{0.1in}
                       \setlength{\topsep}{0in}
                       \setlength{\partopsep}{0in}
                       \setlength{\leftmargin}{0.5in}
                       \setlength{\labelwidth}{0.5in}
                       \setlength{\listparindent}{0in}
                       \setlength{\itemindent}{0in}
                       \setlength{\itemsep}{0in}
                       }
                \item{{\em Instance:\ }}{#2}
                \item{{\em Query:\ }}{#3}
                \end{list}
\end{list}
\medskip
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%% for quizzes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\quizheader}{ {\large NAME: \hskip 3in SID:\hfill}
                                \newline\lineacross \medskip }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%% for final
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\namespace}{\noindent{\Large NAME: \hfill SID:\hskip 1.5in\ }\\\medskip\noindent\mbox{}\hrulefill\mbox{}}


\begin{document}

\title{Assignment 1}



\vspace{-1em}



  \date{}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup




\newpage



\sloppy


\student{Samantha Vu}{861291195} 

\student{Ashu Singh}{861167389} 
\assignment{1} 
\duedate{Friday, January 26}

\medskip

\lineacross

\begin{problem}
\textbf{(a)} Give an exact formula (as a function of \textit{$n$}) for the number of "hello"s printed by Algorithm
PRINTHELLOS below. First express it using the summation notation \(\Sigma\), and then derive a closed-form expression. Show your work.

\indent\emph{Note}: To derive a closed-form solution you will need a formula for the sum of squares of consecutive integers. You can look it up on the Internet.

\textbf{(b)} Give the asymptotic value of the number of "hello"s (using the Theta-notation). Include a brief justification.

\textbf{Algorithm} PrintHellos (\textit{$n$} : \textbf{integer})

\indent\textbf{for} \textit{j} - 1 \textbf{to} 2\textit{$n$} + 1 \textbf{do}

\indent \textbf{for} \textit{k} - 1 \textbf{to} \textit{\(j^2\)} \textbf{do} print("hello")

\indent\textbf{for} \textit{j} - 1 \textbf{to} \textit{\($n$^2\)} \textbf{do}

\indent \textbf{for} \textit{k} - 1 \textbf{to} \textit{j} \textbf{do} print("hello hello")

\end{problem}

\begin{solution}
\textbf{a)} Using the sum of squares of consecutive integers: 
$\displaystyle \sum_{j=1}^{n} {j^2}$ = $\frac{n(n+1)(2n+1)}{6}$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{(2n+1)[(2n+1)+1][2(2n+1)+1]}{6}$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{(2n+1)(2n+2)(4n+3)}{6}$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{(4n^2+6n+2)(4n+3)}{6}$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{(16n^3+12n^2+24n^2+18n+8n+6}{6}$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{16n^3+36n^2+26n+6}{6}$

So $\displaystyle \sum_{j=1}^{2n+1} {j^2+2n^2}$ = $\frac{16n^3+36n^2+26n+6}{6}+2n^2$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{1}{6}*[(16n^3+36n^2+26n+6)+12n^2]$

$\displaystyle \sum_{j=1}^{2n+1} {j^2}$ = $\frac{1}{6}*(16n^3+48n^2+26n+6)$

\textbf{b)} $f(n) = \frac{1}{6}*(16n^3+48n^2+26n+6)$

$O(n^3): \frac{1}{6}*(16n^3+48n^2+26n+6)\leq\frac{1}{6}*(16n^3+48n^3+26n^3+6n^3)$

\indent$= \frac{1}{6}*(16n^3+48n^2+26n+6)\leq16n^3$ for $n\geq1$

$\Omega(n^3): \frac{1}{6}*(16n^3+48n^2+26n+6)\geq\frac{1}{2}*n^3$ for $n\geq0$

$\frac{1}{2}*n^3\leq\frac{1}{6}*(16n^3+48n^2+26n+6)\leq16n^3$ for $n\geq1$

So, $f(n) = \theta(n^3)$.
\end{solution}

\begin{problem}
\textbf{(a)} Use mathematical induction to prove that \(2^{n+1}\) + \(3^{n+1}\) [?] \(2\cdot4^n\) for all integers 
$n [?] 3$.

\textbf{(b)} Let $f(n) =$ \(2^{n+1}\) + \(3^{n+1}\) and $g(n)$ = \(4^n\). Using the inequality from part (a) prove that $f(n) = O(g(n))$. You need to give a rigorous proof derived directly from the definition of $O$-notation, without using any theorems from class. (First, give a complete statement of the definition. Next, show how $f(n) = O(g(n))$ follows from this definition.)
\end{problem}

\begin{solution}
\textbf{a)} Base case: $n=3$

$2^4+3^4\leq2*4^3$

$97\leq128$ True

Assume: $n=k$ holds $2^{k+1}+3^{k+1}\leq2*4^k$

Prove: $n=k+1$ holds $2^{k+2}+3^{k+2}\leq2*4^k+1$

LHS = $2^{k+2}+3^{k+2}$

$2*2^{k+1}+3*3^{k+1}\leq4*2^{k+1}+4*3^{k+1}$

$2*2^{k+1}+3*3^{k+1}\leq4(2^{k+1}+3^{k+1})$

$2*2^{k+1}+2*3^{k+1}\leq4(2*4^k)$

$2*2^{k+1}+2*3^{k+1}\leq2*4^{k+1}$

\textbf{b)} $f(n) = 2^{n+1}+3^{n+1}$

$g(n) = O(4^n)$

Prove $f(n) = O(g(n))$

$f(n)\leq c*g(n)$ for $n\geq3 \rightarrow c = 2$

$2^{n+1}+3^{n+1}\leq2*4^n$ for $n\geq3$, as proven in part (a)

So $f(n) = O(g(n))$.
\end{solution}

\begin{problem}
Give asymptotic estimates, using the $\theta$-notation, for the following functions:

\textbf{(a) } $14n^4+2n^5+3n$

\textbf{(b) } $n^5logn+3n^{0.9}+17n^4$

\textbf{(c) } $7n^2+\frac{2n^4}{logn}+3nlog^4n$

\textbf{(d) } $11*2^n+n^9log^2n+5n^2$

\textbf{(e) } $log^{11}n+n^22^n+3^n$

Justify your answer. (Here, you don't need to give a complete rigorous proof. Give only an informal explanation using asymptotic relations between the basic reference functions: \(n^c\),\(\log n\),and \(c^n\).)
\end{problem}

\begin{solution}
\textbf{a) } $f(n) = 14n^4+2n^5+3n$

$14n^4+2n^5+3n\geq2n^5$, so $f(n)=\Omega(n^5)$.

$14n^4+2n^5+3n\leq14n^5+2n^5+3n^5$

\indent$\leq19n^5$, so $f(n)=O(n^5)$.

Thus, $f(n)=\theta(n^5)$.

\textbf{b) } $f(n) = n^5logn+3n^{0.9}+17n^4$

$n^5logn+3n^{0.9}+17n^4\geq n^5logn$, so $f(n)=\Omega(n^5logn)$.

$f(n) = O(n^5logn)+O(n^5)+O(n^5)$, so $f(n)=O(n^5logn)$.

Thus, $f(n)=\theta(n^5logn)$.

\textbf{c) } $f(n) = 7n^2+2n^4/logn+3nlog^4n$

$7n^2+2n^4/logn+3nlog^4n\geq 2n^4/logn$, so $f(n)=\Omega(n^4/logn)$.

$f(n) = O(n^2)+O(n^4/logn)+O(n)O(n)$, so $f(n)=O(n^4/logn)$.

Thus, $f(n)=\theta(n^4/logn)$.

\textbf{d) } $f(n) = 11\cdot2^n+n^9log^2n+5n^2$

$11\cdot2^n+n^9log^2n+5n^2\geq 2^n$, so $f(n)=\Omega(2^n)$.

$f(n) = O(2^n)+O(n)O(n)+O(n^2)$, so $f(n)=O(2^n)$.

Thus, $f(n)=\theta(2^n)$.

\textbf{e) } $f(n) = log^{11}n+n^22^n+3^n$

$log^{11}n+n^22^n+3^n\geq3^n$, so $f(n)=\Omega(3^n)$.

$f(n) = O(n)+O(\frac{3}{2}^n)*2^n+O(3^n)$, so $f(n)=O(3^n)$.

Thus, $f(n)=\theta(3^n)$.

\end{solution}

\selectlanguage{english}
\FloatBarrier
\end{document}

