\documentclass{exam}
 
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{amsmath}
 
% First we setup the header and footer
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\header{COL351: Analysis and Design of Algorithms (CSE, IITD, Semester-I-2020-21)}{}{Homework-00}
\footer{}{\thepage  \, of \numpages}{}
 
% We want the points for each question displayed on the left
%\pointname{points}
%\pointsinmargin
 
% Automatically total the points - make sure to compile TWICE
\addpoints
 
\begin{document}


\begin{center} 
\fbox{\parbox{5.5in}{
\vspace{-0.1in}
\begin{itemize}
\item \small{Homework solutions should be neatly written or typed and turned in through {\bf Gradescope} by 11:59pm on the due date. No late homeworks will be accepted for any reason.  You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible (neatly written and not too faint) or your homework may not be graded.}

\item \small{Students should consult their textbook, class notes, lecture slides, instructors, TAs, and tutors when 
they need help with homework. Students should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don't understand what the question is asking you to do. Other questions are best addressed in office hours.}

\item \small{Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.}

\item \small{For questions that require pseudocode, you can follow the same format as the textbook, or you can write pseudocode in your own style, as long as you specify what your notation means. For example, are you using ``='' to mean assignment or to check equality? You are welcome to use any algorithm from class as a subroutine in your pseudocode. For example, if you want to sort list $A$ using {\tt InsertionSort}, you can call {\tt InsertionSort($A$)} instead of writing out the pseudocode for {\tt InsertionSort}.}
\end{itemize}
\vspace{-0.1in}
}}
\end{center}

\vspace{0.1in}


\vspace{0.1in}
% Some general text together with number of questions and total points possible
There are \numquestions\, questions for a total of \numpoints\, points.
\vspace{0.1in}
\hrule
 \vspace{0.2in}
\begin{questions}
 
% First question, worth 3 points
\question[10] Let $f(n)$ and $g(n)$ be functions from the nonnegative integers to the positive real numbers. Prove the following transitive property from the definition of big-$O$: \\
\begin{center}
If $f (n) \in O(g (n))$ and $g (n) \in O(h(n))$ then
$f (n) \in O(h(n)).$
\end{center}



\vspace{0.3in}



\question \underline{State True or False}:
\begin{parts}
\part[2] $2 \cdot (3^n) \in \Theta(3 \cdot (2^n))$


\part[2] $(n^6+2n+1)^2 \in \Omega((3n^3+4n^2)^4)$


\part[2] $\log n \in \Omega((\log{n})+n)$


\part[2] $n\log n+n \in O(n\log n)$


\part[2] $\log (n^{10}) \in \Theta(\log(n))$


\part[2] $\sum_{i=1}^n i^k \in \Theta(n^{k+1})$


\part[2] $(\log(n))^{\log(n)} \in O(n/\log(n))$


\part[2] $n! \in O(2^n)$

\end{parts}







\vspace{0.3in}







\question Given two lists $A$ of size $m$ and $B$ of length $n$, our goal is to construct a list of all elements in list $A$ that are also in list $B$. Consider the following two algorithms to solve this problem.

\begin{framed}
{\bf procedure} {\tt Search1}(List $A$ of size $m$, List $B$ of size $n$)\\
1. \hspace*{0.1in} Initialize an empty list $L$.\\
2. \hspace*{0.1in} {\tt SORT} list $B$\\
3. \hspace*{0.1in} {\bf for} each item $a \in A$,\\
4. \hspace*{0.3in} {\bf if} ({\tt BinarySearch($a, B$)} $\neq$ 0), {\bf then} \\
5. \hspace*{0.5in} Append $a$ to list $L$.\\
6. \hspace*{0.1in} {\bf return} $L$
\end{framed} 

\underline{\bf Note}: Assume that the {\tt SORT} algorithm used in {\tt Search1} algorithm above takes time proportional to $k \log k$ on an input list of size $k$.

\begin{framed}
{\bf procedure} {\tt Search2}(List $A$ of size $m$, List $B$ of size $n$)\\
1. \hspace*{0.1in} Initialize an empty list $L$\\
2. \hspace*{0.1in} {\bf for} each item $a \in A$,\\
3. \hspace*{0.3in} {\bf if} ({\tt LinearSearch($a, B$)} $\neq 0$), {\bf then}\\
4. \hspace*{0.5in} Append $a$ to list $L$.\\
5. \hspace*{0.1in} {\bf return} $L$
\end{framed}

Answer the following questions:
\begin{parts}
\part[2] Calculate the runtime of {\tt Search1} in $\Theta$ notation, in terms of $m$ and $n$.

\part[2]
Calculate the runtime of {\tt Search2} in $\Theta$ notation, in terms of $m$ and $n$.


\part[2]
When $m \in \Theta(1)$, which algorithm has faster runtime asymptotically?


\part[2]
When $m \in \Theta(n)$, which algorithm has faster runtime asymptotically?


\part[2]
Find a function $f(n)$ so that when $m \in \Theta(f(n))$, both algorithms have equal runtime asymptotically.
\end{parts}











\vspace{0.3in}






\question Show that if $c$ is a positive real number, then $g(n) = 1 +c + c^2 + ... + c^n$ is:
\begin{parts}
\part[3]
$\Theta(1)$ if $c<1.$



\part[3]
$\Theta(n)$ if $c=1.$



\part[3]
$\Theta(c^n)$ if $c>1.$
\end{parts}









\vspace{0.3in}











\question The Fibonacci numbers $F_0, F_1, ...,$ are defined by 
$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n - 2}$$
\begin{parts}
\part[4]
Use induction to prove that $F_n\ge 2^{0.5n}$ for $n \ge 6$.
\part[4]
Use induction to prove that $F_n\le 2^n$ for $n \ge 0$.
\part[2]
What can we conclude about the growth of $F_n$?
\end{parts}




\end{questions}
\end{document}