\documentclass[answers]{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-4}
\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 1, 2 and 3.}
\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}
 




\question[10] Given an array $A[1...n]$ containing $n$ {\bf distinct} integers sorted in increasing order, design an algorithm that determines if there is an index $i$ such that $A[i] = i$. Give proof of correctness and running time analysis.

\begin{solution}
{\it Write your solution here}:
\end{solution}



\vspace{0.2in}





\question[15]
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.2in}


\question[15]
One ordered pair $v=(v_1,v_2)$ dominates another ordered pair $u=(u_1,u_2)$ if $v_1\geq u_1$ and $v_2 \geq u_2$. Given a set $S$ of ordered pairs, an ordered pair $u\in S$ is called \emph{Pareto optimal} for $S$ if there is no $v\in S$ such that $v$ dominates $u$. Give an efficient algorithm that takes as input a list of $n$ ordered pairs and outputs the subset of all Pareto-optimal pairs in $S$.
 Provide a proof of correctness along with the runtime analysis.




\vspace{0.2in}




\question[15]
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[15] 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[15] 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.2in}





\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}






 %%%%%%%%%%

 

\end{questions}
\end{document}