\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,epsfig}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}
\reversemarginpar
\setlength{\marginparsep}{-15mm}
\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
% Here we define the \question and \subquestion commands.
%
% Use \question{X} to start a question worth X marks (the argument is
% expected). Use \subquestion for a subquestion of unspecified
% weight or \subquestion[Y] for a subquestion worth Y marks.
% The argument is optional, and if present must be in square brackets.
% These macros are not smart enough to check that subquestions add up
% the total of X marks (in part because we want to allow the flexibility
% of not specifying the weight of subparts).
%
\newcounter{qctr}
\newcounter{subqctr}
\newcommand{\qno}{\addtocounter{qctr}{1}\arabic{qctr}}
\newcommand{\question}[1]{\setcounter{subqctr}{0}\noindent\textbf{Question \qno.} ({#1} marks)\enspace}
\newcommand{\subqno}{\addtocounter{subqctr}{1}\alph{subqctr}}
\newcommand{\subquestion}[1][]{
\ifthenelse{\equal{#1}{}}
{\noindent\textbf{\subqno.} \enspace}
{\noindent\textbf{\subqno.} ({#1} marks)\enspace}
}
% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{CS6901} % e.g. B38
%\def\Campus{St. George} % e.g. Scarborough
\def\AssignmentNo{2} % e.g. 1
\def\DateHandedOut{Fall, 2016} % e.g. September 18, 2002
\def\DateDue{Oct 27, 2016} % e.g. October 1, 2002
\def\TimeDue{7pm} % e.g. 11 am
\begin{document}
\noindent
Computer Science \CourseCode \hfill \DateHandedOut\\
\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue, by \TimeDue\\
\end{center}
\hrule\smallskip
For all algorithms design problems, state how you model the problem (if needed), describe your algorithm in words, then give a pseudocode.
\begin{enumerate}
\item \textbf{Maintenance costs} \marginpar{[30]} \\
A telecom company is running its fiber optic network through rural Newfoundland around Gander. With the harsh weather here, they are mainly concerned with the maintenance costs of the network than with the costs of laying the fiber. A local consultant gives them estimates of maintenance cost per year of various possible links between different villages (including Gander).
\begin{enumerate}
\item State which computational problem they need to solve to find the least costly way of providing a fiber network to these villages.
\item Suppose that after they announce their connection scheme, some village offers them to cover some of the costs if it gets a direct link to Gander. Give a linear-time algorithm to decide whether the offer is good enough. The inputs to your algorithm are the previous connection scheme, all the original estimates and the new cost of the link between this village and Gander.
\item Now, suppose that after they built the network, there was a flood, and one of the links they built got washed away. To prevent that happening again, they would need to put in extra infrastructure if they rebuild that link, increasing its maintenance cost. Give a linear-time algorithm that determines whether to rebuild the link or to build a new link elsewhere.
\end{enumerate}
\item \textbf{Greedy algorithms} \marginpar{[30]} \\
Consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with a south endpoint and a north endpoint, with locations of all houses mapped on it. ) You want to place cell phone base stations at certain points along the road, so that every house is within four kilometers of one of the base stations.
\begin{enumerate}
\item Give a linear-time algorithm that achieves this goal, using as few base stations as possible. Your input is the list of houses along the road from south to north, where coordinates of every house is just its distance from the south end of the road.
\item Now, prove the correctness of your algorithm using induction. That is, define a "promising" partial solution and show that at every step of the algorithm your solution is indeed promising.
\end{enumerate}
\item \textbf{Number of solutions} \marginpar{[20]} \\
Consider the single-source shortest path problem with positive edge weights.
\begin{enumerate}
\item Give an example of a graph on 3 vertices $s, v,t$ and with three directed edges, where there is more than one shortest path from $s$ to $t$.
\item Give an $O(m \log n)$ algorithm that computes, for each vertex $v$ in the graph, the number of shortest paths from $s$ to $v$. Hint: modify one of the algorithms we covered in class.
\end{enumerate}
\item \textbf{Shortest path with negative edges} \marginpar{[20]} \\
I have mentioned in class that on a directed acyclic graphs many problems become easier. Let's take advantage of that, in this case for solving single-source shortest path problem with negative weights. Give an algorithm that checks if the input graph is a DAG, and if so, solves single-source shortest-path problem, otherwise outputs "Use Bellman-Ford". The input to your algorithm is $G,s, c$, where $c\colon E \to \mathbb{R}$. The total running time of your algorithm should be $O(m+n)$.
\end{enumerate}
\end{document}