\documentclass[11pt]{article}

%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}

%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}

\begin{document}
\setlength{\parskip}{.1 in}

\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Fall 2016}
\\[0.5ex]
\textbf{HW 3 (due Tuesday, September 20th at 8pm)}
\end{center}

\noindent
This homework contains three problems. {\bf Read the instructions for
  submitting homework on the course webpage}. 

\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with upto three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.



\begin{enumerate}
%----------------------------------------------------------------------
\item You are given a directed graph $G=(V,E)$ where each edge $e$ has
  a length/cost $c_e$ and you want to find shortest path distances
  from a given node $s$ to all the nodes in $V$. Suppose there are 
  only $k$ edges $f_1=(u_1,v_1), f_2=(u_2,v_2), \ldots, f_k=(u_k,v_k)$
  that have negative length, and the rest have non-negative
  lengths. Here think $k$ is small, say a constant number.  The
  Bellman-Ford algorithm for shortest paths with negative length edges
  takes $O(nm)$ time where $n=|V|$ and $m=|E|$. Show that you can take
  advantage of the fact that there are only $k$ negative
  length edges to find shortest path distances from $s$ in $O(k n \log
  n + km )$ time --- effectively this is the running time for running
  Dijkstra's algorithm $k$ times. Your algorithm should output the following:
  {\em either} that the graph has a negative length cycle reachable
  from $s$, {\em or} the shortest path distances from $s$ to all the
  nodes $v \in V$.

 {\em Hint:} First solve the case when there is only a single negative
 length edge. You will get half the credit if you only solve this case.
 Then solve the case of two negative length edges and see if
 you can generalize that approach. Note that this is only one approach, there
 may be others.

\item In the selection problem we are given an array $A$ of $n$
  numbers (not necessarily sorted) and an integer $k$, and the goal is
  to output the rank $k$ element of $A$.  Consider a randomized
  algorithm where we pick a number $x$ uniformly at random from $A$
  and use it as a pivot as in quick sort to partition $A$ into numbers
  less than equal to $x$ and numbers greater than $x$. The algorithm
  recurses on one of these arrays depending on $k$ and the size of the
  two arrays. It can be shown that this algorithm runs in $O(n)$
  expected time and has the advantage of being quite simple when
  compared to the median of median (deterministic) algorithm.
\begin{itemize}
\item[$(A)$] Write down a description of randomized quick selection in
  pseudocode.  Show that the expected depth of the recursion of
  randomized quick selection is $O(\log n)$. (You can also prove that
  the expected running time is $O(n)$ but you should prove this for yourself
  since it will help you in the next part. However, you don't have to submit it
  as part of the home work.)

{\em Hint:} Write a recurrence for the depth of the recursion.
\item[$(B)$] Let $A_1, A_2, \dots , A_h$ be $h$ {\em sorted} arrays where
  $A_i$ has $n_i$ elements. Let $n = \sum_{i=1}^h n_i$.  Assume that
  the arrays have distinct elements. Describe a randomized algorithm
  that given integer $k$ finds the $k$'th smallest element in the
  combined set of arrays in $O(h \log^2 n)$ expected time.

  {\em Hint:} Adapt the randomized quick selection algorithm and the
  analysis from the first part.
%\item Extra credit: A deterministic algorithm for the second part above. In fact a
%time bound of $O(h \log n)$ is achievable.
\end{itemize}


\item Let $G = (V, E)$ be an undirected graph. Recall that $S\subseteq
  V$ is a dominating set if the following property holds: for every
  $u\in V$ we have $u\in S$ or some neighbor of $u$ is in $S$. In the
  domatic partition problem we are given a graph $G$ and the goal is
  to find a maximum number of mutually disjoint dominating sets in
  $G$. Let $\delta$ be the degree of a minimum degree node in $G$. It
  is easy to see that the domatic number is at most $(\delta + 1)$
  since each dominating set has to contain $u$ or some neighbor of $u$
  where $u$ is a node with degree $\delta$. In this problem we will
  see that the domatic number of a graph on $n$ nodes and minimum
  degree $\delta$ is at least as large as $\lceil \frac{\delta+1}{c
    \ln n}\rceil$ for some sufficient large universal constant
  $c$. Note that this guarantees only $1$ dominating set if $\delta <
  c \ln n$ (the entire vertex set can be chosen as the dominating
  set). Let $k =\lceil \frac{\delta+1}{c \ln n}\rceil$. Consider the
  following randomized algorithm. For each node $u$ independently
  assign a color $g(u)$ that is chosen uniformly at random from the
  colors $\{1, 2, \dots , k\}$.
\begin{itemize}
\item[$(A)$] For a fixed node $v$ and a fixed color $i$ show that with
  probability at least $1-\frac{1}{n^2}$ there is a node with color
  $i$ that is either $v$ or a neighbor of $v$. Choose $c$ sufficiently
  large to ensure this.
\item[$(B)$] Using the above show that for a fixed color $i$ the set
  of nodes that are colored $i$ form a dominating set for $G$ with
  probability at least $1 - \frac{1}{n}$.
\item[$(C)$] Using the above two parts argue that the domatic number
  of $G$ is at least $k$.

{\em Hint:} The simple union bound is useful for this problem.
\end{itemize}
\end{enumerate}


\vspace{1in}

{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}

\begin{itemize}
\item Show that quick select takes $O(n)$ time in expectation. See if you can
prove that the number of comparisons is at most $4n$ for an array of size $n$.
\item Solve the first problem on shortest paths  via dynamic programming 
in the file below. \url{https://courses.engr.illinois.edu/cs374/fa2015/labs/lab16-shortest-path-dynamic-prog.pdf}.
\item Solve the first problem on shortest walks in the file below.
\url{https://courses.engr.illinois.edu/cs374/fa2015/homework/hw8.pdf}.
\item Read Jeff's notes on randomized quick sort but in particular the nuts and bolts problem. Solve some of the basic problems on probability and randomized algorithms at the back of the notes. \url{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/09-nutsbolts.pdf}.
\end{itemize}


\end{document}

