\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{fancybox}
\usepackage{graphicx}

\newcommand{\DecKey}{\textsf{\sc DecreaseKey}}
\newcommand{\Insert}{\textsf{\sc Insert}}
\newcommand{\EMin}{\textsf{\sc ExtractMin}}
\newcommand{\Max}{\textsf{\sc Maximum}}
\newcommand{\EM}{\textsf{\sc ExtractMax}}
\newcommand{\Combine}{\textsf{\sc Combine}}
\newcommand{\DFS}{\textsf{\sc DFS}}
\newcommand{\EXPLORE}{\textsf{\sc Explore}}
\newcommand{\RSelect}{\textsf{\sc RSelect}}

\newcommand{\VISITED}{\mathord{\it visited}}
\newcommand{\TRUE}{\mathord{\it true}}
\newcommand{\FALSE}{\mathord{\it false}}
\newcommand{\CC}{\mathord{\it cc}}
\newcommand{\CCN}{\mathord{\it ccnumber}}
\newcommand{\largest}{\mathord{\it largest}}

%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsule}[2]{\vspace{0.5em}
  \shadowbox{%
    \begin{minipage}{.90\linewidth}%
      \textbf{#1:}~#2%
    \end{minipage}}
  \vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document} 

\begin{center} \Large\bf
COMP 3804 --- Assignment 2 
\end{center} 

\noindent {\bf Due:} Thursday February 15, 23:59.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      Brightspace.

\begin{center}
\hfill\shadowbox{
  \begin{minipage}{.90\linewidth}
    {\textsf{Use the following format to name your file:
        \[ {\tt LastName\_StudentId\_a2.pdf}
        \]
      }}
  \end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
      emails of the type ``my internet connection broke down at
      23:57'' or ``my scanner stopped working at 23:58'', or
      ``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
      of discussion only. When writing your solutions, you must do so
      in your own words.
\item Past experience has shown conclusively that those who do not put
      adequate effort into the assignments do not learn the material and
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers.
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\newpage 

\begin{question}
Write your name and student number.
\end{question}

\begin{question} 
Since you all miss COMP 2804 so much, let's start with a basic 
probability question. First some notation: If $x_1,x_2,\ldots,x_m$ are 
real numbers, then their product is written as 
\[ \prod_{i=1}^m x_i = x_1 \cdot x_2 \cdot x_3 \cdots x_m . 
\] 

Let $(S,\Pr)$ be a probability space, let $m \geq 2$ be an integer, 
and let $B_1,B_2,\ldots,B_m$ be a sequence of events in this space. 
In this question, you will prove that 

\begin{equation}  
\label{eqchain} 
   \Pr \left( B_1 \cap B_2 \cap \cdots \cap B_m 
                 \right) 
  =  \Pr \left( B_1 \right) \cdot \prod_{i=2}^{m} 
       \Pr \left( B_i \mid B_1 \cap B_2 \cap \cdots \cap B_{i-1} 
           \right) . 
\end{equation} 

\noindent 
{\bf Question 2.1:} 
Using the definition of conditional probability, prove that 
(\ref{eqchain}) holds when $m=2$.  

\noindent 
{\bf Question 2.2:} 
Using the definition of conditional probability, prove that 
(\ref{eqchain}) holds when $m=3$.  

\noindent 
{\bf Question 2.3:} 
Using induction and the definition of conditional probability, prove 
that (\ref{eqchain}) holds for every integer $m \geq 2$. 
\end{question}

\begin{question}
In class, we have seen the following randomized selection algorithm: 

\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\RSelect(S,k)$: \\
{\bf Input:} Sequence $S$ of numbers, integer $k$ with 
$1 \leq |S| \leq k$ \\
{\bf Output:} $k$-th smallest number in $S$ \\ 
{\bf if} $|S|=1$ \\ 
{\bf then} return the only element in $S$ \\ 
{\bf else} \= $p=$ uniformly random element in $S$; \\ 
           \> by scanning $S$ and {\bf making $|S|-1$ comparisons}, 
              divide it into \\ 
           \> $S_< = \{ x \in S : x < p \}$, \\ 
           \> $S_= = \{ x \in S : x = p \}$, \\ 
           \> $S_> = \{ x \in S : x > p \}$; \\ 
           \> {\bf if} $k \leq |S_<|$ \\
           \> {\bf then} $\RSelect(S_<,k)$ \\ 
           \> {\bf else} \= {\bf if} $k \geq 1 + |S_<| + |S_=|$ \\ 
           \>            \> {\bf then} $\RSelect(S_>,k-|S_<|-|S_=|)$ \\ 
           \>            \> {\bf else} return $p$ \\
           \>            \> {\bf endif} \\
           \> {\bf endif} \\
{\bf endif} \\
\end{tabbing}
\end{quote}

Let $T$ be the random variable whose value is the { \bf number of 
comparisons} made by this algorithm. With $n$ denoting the length of the 
sequence $S$, we have shown that the expected value of $T$ is $O(n)$. 

A natural question to ask is if the value of $T$ is $O(n)$ 
\emph{with high probability}, i.e., does there exist a positive constant  
$C$, such that 
\[ \lim_{n \rightarrow \infty} \Pr (T \leq Cn) = 1 ?
\] 
In this question, you will prove that the answer is ``no''. 

\vspace{0.5em} 

{\bf In the rest of this question, we assume that the sequence $S$ 
contains the numbers $1,2,3,\ldots,n$ in sorted order. We are 
going to run algorithm $\RSelect(S,1)$.} 

\vspace{0.5em} 

Algorithm $\RSelect(S,1)$ and its recursive calls choose pivots 
$p_1,p_2,p_3,\ldots$: 
\begin{itemize} 
\item $p_1$ is chosen uniformly at random in $\{1,2,\ldots,n\}$. 
\item If $p_1 \neq 1$, then $p_2$ is chosen uniformly at random in 
$\{1,2,\ldots,p_1-1\}$. 
\item If $p_2 \neq 1$, then $p_3$ is chosen uniformly at random in 
$\{1,2,\ldots,p_2-1\}$. 
\item If $p_3 \neq 1$, then $p_4$ is chosen uniformly at random in 
$\{1,2,\ldots,p_3-1\}$. 
\item Etcetera. 
\end{itemize} 
Let $C$ be an arbitrary positive integer, and let $n$ be a very large 
integer that is a multiple of $4C$. Divide the set $\{1,2,\ldots,n\}$ 
into $2C+1$ subsets, as indicated in the figure below. The subset $S_0$ 
has size $n/2$, whereas each subset $S_i$, for $1 \leq i \leq 2C$, has  
size $n/(4C)$. 

\begin{center}
\includegraphics[scale=0.60]{divide}
\end{center}

Define the events 
\[ A = \mbox{``$T > Cn$''} 
\]
and, for each $i=1,2,\ldots,2C$, 
\[ B_i = \mbox{``$p_ i \in S_i$''.} 
\]

\noindent 
{\bf Question 3.1:} 
Prove that 
\[ \Pr \left( B_1 \cap B_2 \cap \cdots \cap B_{2C} \right) 
    \leq \Pr(A) . 
\] 

\noindent 
{\bf Question 3.2:} 
Use Question~2 to prove that 
\[ \Pr(A) \geq \left(1/(4C) \right)^{2C} . 
\]

\noindent 
{\bf Question 3.5:} 
Conclude that 
\[ \Pr(T \leq Cn) \leq 1 - \left(1/(4C) \right)^{2C} . 
\]
\end{question}

\begin{question}
You are given a min-heap $A[1 \ldots n]$ and a variable $\largest$ 
that stores the largest number in this min-heap. 

In class, we have seen algorithms $\Insert(A,x)$ (which adds the number 
$x$ to the min-heap and restores the heap property) and $\EMin(A)$ (which 
removes the smallest number from the heap and restores the heap property). 

Explain, in a few sentences, how these two algorithms can be modified
such that the value of $\largest$ is correctly maintained. The running 
times of the two modified algorithms must still be $O(\log n)$. 
\end{question}

\begin{question}
Let $m$ be a large integer and consider $m$ non-empty sorted lists 
$L_1,L_2,\ldots,L_m$. All numbers in these lists are integers. Let $n$ 
be the total length of all these lists. 

Describe an algorithm that computes, in $O(n \log m)$ time, two integers 
$a$ and $b$, with $a \leq b$, such that 
\begin{itemize}
\item each list $L_i$ contains at least one number from the set 
$\{a,a+1,\ldots,b\}$ and 
\item the difference $b-a$ is minimum. 
\end{itemize}
For example, if $m=4$, 
\[ \begin{array}{lcl} 
     L_1 & = & (2,3,4,8,10,15) \\
     L_2 & = & (1,5,12) \\
     L_3 & = & (7,8,15,16) \\
     L_4 & = & (3,6) , 
   \end{array} 
\]
then the output can be $(a,b)=(4,7)$ or $(a,b)=(5,8)$. 

As always, justify the correctness of your algorithm and explain why 
the running time is $O(n \log m)$. 

\noindent 
\emph{Hint:} Use a min-heap of size $m$ and use Question~4. For the 
example, draw it like this, then stare at it until you ``see'' the 
algorithm:  

\begin{center}
     \includegraphics[scale=0.7]{example}
\end{center}
\end{question}

\newpage 

\begin{question}
Consider the following undirected graph:

\begin{center}
     \includegraphics[scale=0.6]{graph}
\end{center}

\noindent 
{\bf Question 6.1:} 
Draw the $\DFS$-forest obtained by running algorithm $\DFS$ on this 
graph. Recall that algorithm $\DFS$ uses algorithm $\EXPLORE$ as a 
subroutine. 

In the forest, draw each tree edge as a solid edge, and draw each back 
edge as a dotted edge. 

Whenever there is a choice of vertices (see the two lines labeled (*)), 
pick the one that is alphabetically first. 

\noindent 
{\bf Question 6.2:} 
Do the same, but now, whenever there is a choice of vertices (see the 
two lines labeled (*)), pick the one that is alphabetically last. 
\end{question}

\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\DFS(G)$: \\
{\bf for each} vertex $u$ \\
{\bf do} $\VISITED(u) = \FALSE$ \\
{\bf endfor}; \\
$\CC = 0$; \\ 
{\bf for each} vertex $v$ \ \ \ \ \ (*) \\
{\bf do} \= {\bf if} $\VISITED(v) = \FALSE$ \\
         \> {\bf then} \= $\CC = \CC + 1$ \\ 
         \>            \> $\EXPLORE(v)$  \\
         \> {\bf endif} \\
{\bf endfor} \\
\end{tabbing}
\end{quote}

\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\EXPLORE(v)$: \\
$\VISITED(v) = \TRUE$; \\
$\CCN(v) = \CC$; \\ 
{\bf for each} edge $\{v,u\}$ \ \ \ \ \ (*) \\
{\bf do} \= {\bf if} $\VISITED(u) = \FALSE$ \\
         \> {\bf then} \= $\EXPLORE(u)$ \\
         \> {\bf endif} \\
{\bf endfor} \\
\end{tabbing}
\end{quote}

\begin{question}
Prove that an undirected graph $G=(V,E)$ is bipartite if and only if 
$G$ does not contain any cycle having an odd number of edges.  
\end{question}

\begin{question}
Since Taylor Swift and Travis Kelce miss each other very much, they 
decide to meet. Taylor and Travis live in a connected, undirected, 
non-bipartite graph $G=(V,E)$. Taylor lives at vertex $s$, whereas 
Travis lives at vertex $k$. 

Taylor and Travis move in steps. In each step, Taylor must move from her 
current vertex to a neighboring vertex, and Travis must move from his 
current vertex to a neighboring vertex. 

Prove that there exists a moving strategy such that Taylor and Travis 
meet each other at the same vertex.  

\noindent 
\emph{Hint:} 
While moving around in the graph, each of Taylor and Travis may visit 
the same vertex more than once, and may traverse the same edge more 
than once. 

If the graph $G$ consists of the single edge $\{s,k\}$, then they 
will never be at the same vertex. But in this case $G$ is bipartite.  

If the graph contains a path having $8$ edges, Taylor lives at one 
end-vertex, and Travis lives at the other end-vertex, will they ever 
be at the same vertex?  

Question~7 is useful. 

\end{question}

\end{document} 
