\documentclass{exam}
 
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{amsmath}
 \usepackage{mdframed}
 \usepackage{xcolor}
 
% First, we setup the header and footer
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\header{COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2023-24)}{}{Homework-1}
\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:59 pm on the due date. No late homework 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, instructor, and TAs 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.}

\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 requiring pseudocode, you can follow the same format as we do in class or write pseudocode in your style, as long as you specify your notation. 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 several 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 ({\it Analysing recursive functions}) In this question, you are asked to analyse two recursive functions.

\begin{parts}
\part[10] Consider the following recursive function that takes as input a positive integer. 
\begin{framed}
\texttt{F($n$)}\\
\hspace*{0.1in} $\cdot$ If ($n > 1$) \texttt{F($\lfloor n/2 \rfloor$)}\\
\hspace*{0.1in} $\cdot$ print(``Hello World'')
\end{framed}
Give the \textbf{exact} expression, in terms of $n$, for the number of times ``Hello World'' is printed when a call to $F(n)$ is made. Argue the correctness of your expression using mathematical induction.

\begin{solution}
({\it You may type your solution in this space here.})
\end{solution}




\vspace{0.1in}

\part[15] Consider the following recursive function that takes as input two positive integers $n$ and $m$.

\begin{framed}
{\tt G($n, m$)}\\
\hspace*{0.1in} $\cdot$ if ($n = 0$ OR $m = 0$)return;\\
\hspace*{0.1in} $\cdot$ print(``Hello World")\\
\hspace*{0.1in} $\cdot$ {\tt G($n-1, m$)}\\
\hspace*{0.1in} $\cdot$ {\tt G($n, m-1$)}
\end{framed}
Give the \textbf{exact} expression, in terms of $n$ and $m$, for the number of times ``Hello World'' is printed when a call to \texttt{G($n, m$)} is made. Argue the correctness of your expression using mathematical induction.
\end{parts}


\vspace{0.3in}




\question ({\it Proof techniques review}) Let us quickly review a few proof techniques you must have studied in your introductory Mathematics course.

\begin{mdframed}[backgroundcolor=green!20]
\begin{itemize}
\item \underline{Direct proof}: \textit{Used for showing statements of the form $p$ implies $q$. We assume that $p$ is true and use axioms, definitions, and previously proven theorems, together with rules of inference, to show that $q$ must also be true.}
\item \underline{Proof by contraposition}: \textit{Used for proving statements of the form $p$ implies $q$. We take $\neg q$ as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that $\neg p$ must follow.}
\item \underline{Proof by contradiction}: \textit{Suppose we want to prove that a statement $p$ is true and suppose we can find a contradiction $q$ such that $\neg p$ implies $q$. Since $q$ is false, but $\neg p$ implies $q$, we can conclude that $\neg p$ is false, which means that $p$ is true.  The contradiction $q$ is usually of the form $r \wedge \neg r$ for some proposition $r$.}
\item \underline{Counterexample}: \textit{Suppose we want to show that the statement for all $x$, $P(x)$ is false. Then we only need to find a counterexample: an example $x$ for which $P(x)$ is false.}
\item \underline{Mathematical induction}: Used for proving statements of the form $\forall n, P(n)$. This has already been discussed in class.
\end{itemize}
\end{mdframed}

Solve the proof problems that follow:
\begin{parts}
\part[3] Give a direct proof of the statement: ``If $n$ is odd, then $n^2$ is odd".

\part[3] Prove by contraposition that ``if $n^2$ is odd, then $n$ is odd".

\part[3] Give proof by contradiction of the statement: ``at least four of any 22 days must fall on the same day of the week."

\part[3] Use a counterexample to show that the statement ``Every positive integer is the sum of squares of two integers" is false.

\part[3] Show using mathematical induction that for all $n \geq 0$, $1 + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + ... + \frac{1}{2^n} = \frac{1 - (\frac{1}{2})^{n+1}}{1 - \frac{1}{2}}$.
\end{parts}


\vspace{0.3in}



\question ({\it Working with the definition of big-O})
\begin{mdframed}[backgroundcolor=green!20]
Big-O notation requires practice to become comfortable. There is a bit of mathematical jugglery since the definition involves a quantified statement. However, the mathematics involved should not be new to you. 
All that is required is to work with the quantified statement. Let us consider an example. Suppose there is an exponential-time algorithm with a running time expression $2^n$. Would it be correct to say that the running time is $O(3^n)$? Yes, this would be correct. Let us work with the definition to verify this. To show that $2^n$ is $O(3^n)$, all we need to do is to give constants $c>0$ and $n_0>0$ such that $\forall n \geq n_0, 2^n \leq c \cdot 3^n$. It is easy to check that this holds for constants $c=1$ and $n_0=1$.

Let us consider the reverse case. That is, suppose the running time of an algorithm is $3^n$. Would it be correct to say that the running time is $O(2^n)$? No, this would not be correct. The way to argue that $3^n$ is \textbf{not} $O(2^n)$ is to show the negation of the quantified statement for this example.
That is, we need to show that for \textbf{any} constants $c > 0, n_0 > 0$, there exists $n \geq n_0$ such that $3^n > c \cdot 2^n$. 
Note that $3^n > c \cdot 2^n \Leftrightarrow (3/2)^n > c \Leftrightarrow n > \log_{3/2}{c}$. 
So, for any constant $c$, $3^n > c \cdot 2^n$ when $n > \log_{3/2}{c}$. So, for any constants $c>0$ and $n_0>0$, let us try $n' = \max{(\lceil \log_{3/2}{c} +1\rceil, n_0)}$. We find that 
$3^{n'} > c \cdot 2^{n'}$ and furthermore $n' \geq n_0$. From this, we conclude that $3^n$ is not $O(2^n)$.
\end{mdframed}

Prove or disprove the following statements:
\begin{parts}
\part[3] $2^{\sqrt{\log{n}}}$ is $O(n)$.
\part[7] $(9 n 2^n + 3^n)$ is $\Omega(n 3^n)$.
\end{parts}



\vspace{0.3in}




\question ({\em More practice with big-O definition})
Prove or disprove the following statements:
\begin{parts}
\part[5] If $d(n)$ is $O(f(n))$ and $f(n)$ is $O(g(n))$, then $d(n)$ is $O(g(n))$.
\part[5] $\max{\{f(n), g(n)\}}$ is $O(f(n) + g(n))$.
\part[5] If $a(n)$ is $O(f(n))$ and $b(n)$ is $O(g(n))$, then $a(n) + b(n)$ is $O(f(n) + g(n))$.
\part[5] If $f(n)$ is $O(g(n))$, then $2^{f(n)}$ is $O(2^{g(n)})$.
\part[5] If $f(n)$ is $O(g(n))$, then $f(2n)$ is $O(g(2n))$.
\end{parts}




\vspace{0.3in}




\question[15] ({\it Arguing correctness using induction}) Argue using induction that the following algorithm correctly computes the value of $a^n$ when given positive integers $a$ and $n$ as input.
\begin{framed}
\texttt{Exponentiate(a, n)}\\
\hspace*{0.1in} $\cdot$ if ($n=0$) return($1$)\\
\hspace*{0.1in} $\cdot$ $t = $ \texttt{Exponentiate($a, \lfloor n/2 \rfloor$)}\\
\hspace*{0.1in} $\cdot$ if ($n$ is even) return($t \cdot t$)\\
\hspace*{0.1in} $\cdot$ else return($t \cdot t \cdot a$)
\end{framed}




\vspace{0.3in}




\question ({\em Analysing running time}) We start with a brief discussion.
\begin{mdframed}[backgroundcolor=green!20]
As discussed in class, the big-O notation allows us to ignore the hairy details we may need to keep track of otherwise. Let us consider the example of the Insertion Sort algorithm below for this discussion.
\begin{framed}
\texttt{InsertionSort($A, n$)}\\
\hspace*{0.02in} $\cdot$ for $i$ = $1$ to $n$\\
\hspace*{0.1in} $\cdot$ $j$ = $i-1$\\
\hspace*{0.1in} $\cdot$ while($j > 0$ and $A[j] > A[i]$) $j$- -\\
\hspace*{0.1in} $\cdot$ for $k$ = $j$+1 to $i$-1\\
\hspace*{0.2in} $\cdot$ Swap $A[i]$ and $A[k]$
\end{framed}
The first line of the algorithm is a `for' statement. How many basic operations does this `for' statement contribute? Getting a precise count will require some deeper analysis of its implementation mechanism. It should involve a comparison operation in every iteration since one needs to check if the variable $i$ has exceeded $n$. It should include arithmetic operation since the variable $i$ needs to be incremented by $1$ at the end of each iteration. Are these all the operations? Not really. The increment operation involves loading the variable and storing it after the increment. Keeping track of all these hairy details may be too cumbersome. A quick way to account for all possible basic operations is to say that the contribution to the number of operations coming from every iteration of the outer `for' statement is a constant. So, the number of operations contributed by the outer `for' statement is $an+b$ for some constants $a, b$. This is the level of granularity at which we shall do the counting to keep things simple.
\end{mdframed}

Answer the questions that follow:
\begin{parts}
\part[2] What is the worst-case number of operations contributed by the while-loop in the $i^{th}$ iteration of the outer for-loop as a function of $i$? 
({\em You can give an expression in terms of symbols for constants as we did for the outer `for' statement in the discussion. This will be sufficient since the big-O will allow us to ignore the specific constants.})
\part[2] Similarly, what is the worst-case number of operations contributed by the inner for-loop in the $i^{th}$ iteration of the outer for-loop as a function of $i$? Again, express using symbolic constants.
\part[2] Use expressions of the previous two parts to give the worst-case number of operations executed by the algorithm. Use big-O notation. Give a brief explanation.
\part[4] Show that your running time analysis in the previous part is tight.
\end{parts}




\end{questions}
\end{document}