\documentclass{exam}
 
\usepackage{graphicx}
\usepackage{float}
\usepackage{amsmath}
\usepackage{subcaption}
 
% 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-3}
\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{The instructions are the same as in Homework-0, 1, 2.}
\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[5]

Solve the following recurrence relations. You may use the Master theorem wherever applicable.

(a) $T(n) = 3 T(n/3) + cn$,    T(1) = c

(b) $T(n) = 3 T(n/3) + cn^{2}$,  T(1) = c

(c) $T(n) = 3 T(n-1) + 1$, T(1) = 1



\vspace{0.3in}






\question[20]
Consider the following problem:  You are given a pointer to the root $r$ of a binary tree, where each vertex $v$
has pointers $v.lc$ and $v.rc$ to the left and right child, and a value $Val(v) > 0$ .  The value NIL represents
a null pointer, showing that $v$ has no child of that type.
You wish to find the path from $r$ to some leaf that minimizes the total values of vertices along that path. Give an algorithm to find the minimum sum of vertices along such a path along with a proof of correctness and runtime analysis.




\vspace{0.3in}








\question[20]
Let $S$ and $T$ be sorted arrays each containing $n$ elements. Design an algorithm to find the $n^{th}$ smallest element out of the $2n$ elements in $S$ and $T$ .
Discuss running time, and give proof of correctness.




\vspace{0.2in}




\question
An array $A[1...n]$ is said to have a majority element if more than half (i.e., $> n/2$) of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form ``is $A[i] \geq A[j]$?" (Think of the array elements as GIF files, say.) However you can answer questions of the form: ``is $A[i] = A[j]$?" in constant time.
 \begin{parts}
\part[10] Show how to solve this problem in $O(n \log{n})$ time. Provide a runtime analysis and proof of correctness.

({\it \underline{Hint}: Split the array $A$ into two arrays $A1$ and $A2$ of half the size. Does knowing the majority elements of $A1$ and $A2$ help you figure out the majority element of $A$? If so, you can use a divide-and-conquer approach.}) 



\part[10] Design a linear time algorithm. Provide a runtime analysis and proof of correctness.

({\it \underline{Hint}: Here is another divide-and-conquer approach: 
\begin{itemize}
\item Pair up the elements of $A$ arbitrarily, to get $n/2$ pairs (say $n$ is even)

\item Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them

\item Show that after this procedure there are at most $n/2$ elements left, and that if $A$ has a majority element then it's a majority in the remaining set as well)
\end{itemize}
}
\end{parts}



\vspace{0.3in}



\question Consider the following algorithm for deciding whether an undirected graph has a {\em Hamiltonian Path} from $x$ to $y$, i.e.,  a simple path in the graph from $x$ to $y$ going through all the nodes in $G$ exactly once.
($N(x)$ is the set of neighbors of $x$, i.e. nodes directly connected to $x$ in $G$).

\begin{framed}
{\tt HamPath(graph $G$, node $x$, node $y$)}\\
\hspace*{0.1in} - If $x=y$ is the only node in $G$ return $True$.\\
\hspace*{0.1in} - If no node in $G$ is connected to $x$, return $False$.\\
\hspace*{0.1in} - For each $z \in N(x)$ do:\\
\hspace*{0.4in} - If {\tt HamPath($G-\{x\},z,y$)}, return $True$.\\
\hspace*{0.1in} - return $False$
\end{framed}

\begin{parts}
\part[7] Give proof of correctness of the above backtracking algorithm.

\part[8] If every node of the graph $G$ has degree (number of neighbors)
at most $4$, how long will this algorithm take at most? 
{\it (Hint: you can get a tighter bound than the most obvious one.)}
\end{parts}




\vspace{0.3in}




\question[20] Design an $O(poly(n) \cdot 2^{n/4})$-time backtracking algorithm for the maximum independent set problem for graphs with bounded degree $3$ (these are graphs where all vertices have degree at most $3$). Give running time analysis and proof of correctness.



\end{questions}
\end{document}