\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{microtype}
\usepackage{nicefrac}
\usepackage[small]{complexity}
\renewcommand{\S}{\defaultS}
\renewcommand{\L}{\ComplexityFont{L}}
\newcommand{\ETIME}{\ComplexityFont{E}}
\usepackage[colorlinks=true]{hyperref}
\hypersetup{
linkcolor=[rgb]{0.5, 0.2, 0.2},
citecolor=[rgb]{0.2, 0.5, 0.2},
urlcolor =[rgb]{0.2, 0.2, 0.5}
}
\newcommand{\thecourse}{cs473: Algorithms}
\newcommand{\handout}[5]{
%\renewcommand{\thepage}{#1-\arabic{page}}
\noindent%
\begin{center}%
\framebox{%
\vbox{%
\vspace{1mm}%
\hbox to 5.78in { {\bf \thecourse} \hfill #2 }%
\vspace{4mm}%
\hbox to 5.78in { {\Large \hfill #5 \hfill} }%
\vspace{4mm}%
\hbox to 5.78in { {#3 \hfill #4} }%
}%
}%
\end{center}%
\vspace*{4mm}%
}%
\setlength\parindent{0pt}
% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
\newif\ifstaritem
\newcommand{\setupstarnumerate}{%
\global\staritemfalse
\let\origmakelabel\makelabel
\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
\def\makelabel##1{%
\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
\global\staritemfalse}%
}
% math
\newcommand{\N}{\mathbb{N}}
\newcommand{\bits}{\ensuremath{\{0,1\}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\rX}{\mathsf{X}}
\newcommand{\rY}{\mathsf{Y}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\vec}[1]{\overline{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\DeclareMathOperator{\squar}{square}
\begin{document}
\handout{0}{Assigned: \textit{Tue., Sep. 10, 2019}}{\parbox{2in}{Prof.\ Michael A. Forbes\\ Prof. Chandra Chekuri}}{Due: \textit{Wed., Sep. 18, 2019 (10:00am)}}{Problem Set \#2}
Some reminders about logistics.
\begin{itemize}
\item \textbf{Submission Policy:} See the course webpage for how to submit your pset via gradescope.
\item \textbf{Collaboration Policy:} For this problem set you are allowed to work in groups of up to three. Only one copy should be submitted per group on gradescope. See the course webpage for more details.
\item \textbf{Late Policy:} Late psets are not accepted. Instead, we will drop several of your lowest pset problem scores; see the course webpage for more details.
\end{itemize}
All (non-optional) problems are of equal value.
\begin{enumerate}
\item \label{1} Suppose you have $k$ dollars to invest in $n$ investment options. Investing $a$ dollars in option $i$ will fetch you a profit of $f_i(a)$ dollars --- these are complicated investments and hence the actual return is not a well-defined function but rather given as a table entry. Investments can be only be done in full dollar amounts. How do you spread your $k$ dollars among the $n$ options to maximize your profit?
Mathematically we formalize it as follows. We are given $n$ functions $f_1,f_2,\ldots,f_n$ which can be accessed as sub-routines. Given an integer $a$ we can obtain the value $f_i(a)$ in constant time. We wish to solve the following problem: given integer $k\ge 0$ find integers $k_1,k_2,\ldots,k_n \ge 0$ to maximize $\sum_{i=1}^n f_i(k_i)$ subject to the condition that $\sum_{i=1}^n k_i \le k$ (not all $k$ dollars need to be invested if it is not profitable to do so).
\begin{enumerate}
\item Describe an algorithm for this problem that runs in time polynomial in $k$ and $n$.
\item Describe how to implement your algorithm so that it uses $O(k)$ space.
\end{enumerate}
\item We have seen an algorithm to solve the maximum weight independent set problem in a given node-weighted tree. Consider the following generalization. The input now consists of a tree $T=(V,E)$ with non-negative integer weights $w:V\to\mathbb{Z}_{\ge 0}$ and also an integer $k$. Describe an efficient algorithm that computes the maximum weight independent set with $\le k$ nodes.
\emph{Hint:} Consider using the algorithm from problem \eqref{1}.
\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)$-\emph{walk} in $G$ that contains $\ge 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{enumerate}
\item Develop an algorithm when $G$ is a directed acyclic graph (DAG).
\item Develop an algorithm for the general case using the meta-graph DAG of strongly-connected components of a directed graph. (If you are unfamiliar with this concept, then see for example Chapter 3 of Dasgupta-Papadimitriou-Vazirani).
\emph{Hint:} What is the answer if $G$ is strongly connected?
\end{enumerate}
\item (\textbf{optional}, \emph{not} for submission) Given an undirected graph $G=(V,E)$ we defined its \emph{square}, denoted by $\squar(G)$ as the graph $G'=(V,E')$ where $(u,v)\in E'$ iff there is a path of length $\le 2$ between $u$ and $v$ in $G$. That is, $(u,v)\in E'$ if $(u,v)\in E$ or if there is a node $w$ such that $(u,w),(w,v)\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 (\textbf{optional}, \emph{not} for submission) Given a tree $T=(V,E)$ describe an efficient algorithm to count the number of (\emph{all}, not necessarily maximum) independent sets in $T$. Also for counting the number of (\emph{all}, not necessarily minimal) dominating sets in $T$.
\item (\textbf{optional}, \emph{not} for submission) 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 \emph{load} of a machine is the sum of the sizes of the jobs assigned to it. This is an \NP-hard problem in general.
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$. In this case it suffices to specify the job instance by $m$, the sizes $a,b,c$, and $3$ integers $n_a,n_b,n_c$ which indicate the number of jobs of each size. Describe an algorithm that runs in $(n+m)^{O(1)}$ time for this problem where $n=n_a+n_b+n_c$ is the total number of jobs.
\emph{Hint:} The number 3 is not important. In fact one can devise an $(n+m)^{O(k)}$-time algorithm if the jobs have only $k$ distinct job sizes.
\end{enumerate}
\end{document}