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