\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 2 (due Tuesday, September 13th 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 Given an undirected graph $G=(V,E)$ we defined its
  {\em square}, denoted by $\text{square}(G)$ as the graph $G'=(V,E')$
  where $uv \in E'$ iff there is a path of length at most $2$ between
  $u$ and $v$ in $G$. That is, $uv \in E'$ if $uv \in E$ or if
  there is a node $w$ such that $uw, wv \in E$. In class we saw
  an algorithm for the maximum weight independent set problem in
  a tree $T=(V,E)$. Design and analyze an algorithm for the maximum
  weight independent set problem for the square of a given tree $T=(V,E)$.

\item Let $G=(V,E)$ be a directed graph and let $k$ be an integer.
  Describe an efficient algorithm that given two nodes $s, t \in V$
  checks whether there is an $s$-$t$ {\em walk} in $G$ that contains
  at least $k$ distinct nodes. Note that it is important that we ask
  for a walk and not a simple path for otherwise the problem would be
  NP-Complete.
  \begin{itemize}
  \item Develop an algorithm when $G$ is a DAG.
  \item Develop an algorithm for the general case using the
    strong-component meta-graph of a given directed graph which is a
    DAG. (See Chapter 3 of Dasgupta etal book if you are unfamiliar
    with this notion.) {\em Hint:} What is the answer if $G$ is
    strongly connected?
  \end{itemize}
\item Consider the following multi-processor scheduling problem.  The
  input consists of $n$ jobs $J_1,J_2,\ldots, J_n$ and $m$ identical
  machines $M_1,M_2,\ldots,M_m$. Each job $J_i$ has a non-negative
  size $s_i$.  The goal is to assign the jobs to the machines to
  minimize the maximum load over all machines. The load of a machine
  is the sum of the sizes of the jobs assigned to it. This is an
  NP-Hard problem. However, here we will consider the setting where
  there are only $3$ distinct job sizes $\{a,b,c\}$. That is, $s_i \in
  \{a,b,c\}$ for $1 \le i \le n$. Describe a polynomial-time algorithm
  for this problem. You need not answer this part but can you obtain a
  polynomial time algorithm when the number of distinct job sizes is
  at most $k$ where $k$ is some fixed constant?
\end{enumerate}


\newpage

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

\begin{itemize}
\item Did you do some of the DP problems mentioned in the previous home work?
Below you will find more challenging ones.
\item Given a graph $G=(V,E)$ a matching is a set of edges $E'
  \subseteq E$ such that no two edges in $E'$ share an end
  point. Describe an efficient algorithm that given a tree $T=(V,E)$
  and non-negative weights $w: E \rightarrow \mathbb{R}_+$ finds a
  maximum weight matching in $T$.
\item See Homework 2 from Spring 2016 taught by Jeff Erickson.
\url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw2.pdf}
\item See Homeworks 2 and 3 from Fall 2015 taught by Sariel Har-Peled. 
All the problems are on dynamic programming. They are a bit challenging.
\url{https://courses.engr.illinois.edu/cs473/fa2015/w/hw/hw_02.pdf} and
\url{https://courses.engr.illinois.edu/cs473/fa2015/w/hw/hw_03.pdf}.
\item There are several nice shortest path problems in both text books
and at the end of Jeff's notes on shortest paths. Check them out.
\item Given a directed graph $G=(V,E)$ with non-negative edge lengths
  $\ell: E \rightarrow \mathbb{R}_+$, describe an algorithm that finds
  the shortest cycle in $G$ that contains a specific node
  $s$. Describe an algorithm to find the shortest cycle containing $s$
  with at most $k$ edges. Describe an algorithm to find a cycle $C$
  with minimum {\em average} length where the average length of a
  cycle $C$ is defined as $\ell(C)/|C|$.
\end{itemize}


\end{document}

