\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,amssymb,algorithm,algorithmic}
\pagestyle{fancy}
%\usepackage{cs5114}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\setcourse{CS 4104}
\setsem{Spring 2017}
\sethwnum{4}
\chead{\course (\sem): Homework \hwnum}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework \hwnum}}
\author{\course (\sem)}
\date{Assigned on Wednesday, March 1, 2017. \\Submit PDF solutions on Canvas\\ by the
beginning of class on Wednesday, March 15, 2017.}
\maketitle
\input{instructions}
\newpage
\begin{description}
\item[Problem 1] (10 points) Solve the recurrence $T(n) = T( \lfloor
\sqrt{n} \rfloor) +
1$. In words, the $T(n)$ is the running time of an algorithm that
creates one sub-problem of the size equal to the square root of $n$,
solves this sub-problem recursively, and spends one more unit of time.
You can assume that $T(1) = T(2) = 1$ and that $n > 2$ in the
recurrence relation. Remember to prove your solution by induction,
even if you use the ``unrolling'' method to guess a solution.
% \solution{
% }
\item[Problem 2] (30 points) Let $G = (V, E)$ be an undirected connected
graph and let $c: E \rightarrow \reals^+$ be a function specifying the
costs of the edges, i.e., every edge has a positive cost. Assume that
no two edges have the same cost. Given a set $S \subset V$, where $S$
contains at least one element and is not equal to $V$, let $e_S$
denote the edge in $E$ defined by applying the cut property to $S$,
i.e., $$e_S = {\arg \min}_{e \in \cut{S}} c_e.$$ In this
definition, the function ``$\arg\min$'' is just like ``$\min$'' but returns
the argument (in this case the edge) that achieves the minimum. Let
$F$ be set of all such edges, i.e., $F = \{ e_S, S \subset V, S \not=
\emptyset\}$. In the definition of $F$, $S$ ranges over \emph{all}
subsets of $V$ other than the empty set and $V$ itself. Answer the following questions, providing proofs for all
but the first question.
\begin{enumerate}[(i)]
\item (5 points) How many distinct cuts does $G$ have? We will use the
same definition as in class: a cut is a set of edges whose removal
disconnects $G$ into two non-empty connected components. Two cuts
are distinct if they do not contain exactly the same set of
edges. For this question, just provide an upper bound.
\item (8 points) Consider the graph induced by the set of edges in $F$,
i.e., the graph $G' = (V, F)$. Is $G'$ connected?
\item (7 points) Does $G'$ contain a cycle?
\item (5 points) How many edges does $F$ contain?
\item (5 points) What conclusion can you draw from your answers to the
previous statements?
\end{enumerate}
% \solution{
% }
\item[Problem 3] (15 points) Consider the version of Dijkstra's
algorithm shown below written by someone with access to a priority queue data structure that supports
\emph{only} the \textsc{Insert} and \textsc{ExtractMin}
operations. Due to this constraint, the difference between this
version and the one discussed in class is that instead of the
$\textsc{ChangeKey}(Q, x, d'(x))$ operation in
Step~\ref{step:change-key}, this version simply inserts the pair
$(x, d'(x))$ into $Q$. The danger with this algorithm is that a node
$x$ may occur several times in $Q$ with different values of
$d'(x)$. Answer the following questions.
\begin{enumerate}
\item (5 points) When the algorithm inserts a pair $(x, d_1)$ into
$Q$, suppose the pair $(x, d_2)$ is already in $Q$. What is the
relationship between $d_1$ and $d_2$?
\item (5 points) Using this relationship, how will you fix this
algorithm? You just have to describe your correction in words, e.g.,
by saying ``I will add the following command after Step X: \ldots''
You do not have to prove the correctness of your algorithm.
\item (5 points) What is the running time of this algorithm? Just
state the bound in terms of the number of nodes $n$ and the number
of edges $m$ in $G$.
\end{enumerate}
\begin{algorithm}[H]
\caption{{\sc Dijkstra's Algorithm($G, l, s$)}}
\begin{algorithmic}[1]
% \REQUIRE A set \calg of graphs, $0 \leq \beta,
% \sigma \leq 1$.
% \ENSURE All $(\beta, \sigma)$-hyperedges.
\STATE \textsc{Insert}$(Q, s, 0)$.
\WHILE{$S \not= V$}
\STATE $(v, d'(v)) = \textsc{ExtractMin}(Q)$ \label{step:extract-min}
\STATE Add $v$ to $S$ and set $d(v) = d'(v)$
\FOR{every node $x \in V - S$ such that $(v, x)$ is an
edge in $G$} \label{step:outgoing-neighbours}
\IF{$d(v) + l_{(v, x)} < d'(x)$}
\STATE $d'(x) = d(v) + l_{(v, x)}$
\STATE $\textsc{Insert}(Q, x, d'(x))$ \label{step:change-key}
\ENDIF
\ENDFOR
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\item[Problem 4] (30 points) Solve exercise~3 in Chapter~5
(pages~246--247) of your textbook. Let us call the equivalence class
with more than $n/2$ cards the \emph{important} class. It is enough for
your algorithm to return a card that belongs to this class, if it
exists, or no card at all. Note that the problem specifies that the
only operation you can perform on a pair of cards is to decide if they
are equivalent. You cannot perform any other operation, e.g., compare
them in order to sort them. Your proof of correctness must clearly
address why your algorithm will find a set of important class, if it
exists. There are many things that can go wrong. For instance, there
may be an important class for all $n$ cards but the recursive calls
don't find any important class (for the subset of cards they
process). Alternatively, the recursive calls may find a
\emph{different} important class. It is also possible that there is no
important class for all $n$ cards but your recursive calls find an
important class. Your algorithm or your proof of correctness must
consider all such bad eventualities and you must show that they cannot
happen.
% \solution{
% }
\item[Problem 5] (15 points) Given a sorted array of distinct integers
$A[1, \ldots n]$, you want to find out if there is an index $i$ such
that $A[i] = i$. Give a divide and conquer algorithm to solve this
problem. Of course, you must prove its correctness and analyse its
running time. Pay special attention to the proof of correctness,
especially to show that your algorithm is correct when it returns that
there is no such index.
% \solution{
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: