%---------change this every homework
% place your email id between the braces so that your homework has a name
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{sat nov 5, 2016 at 11.59p}
\def\duelocation{via \href{https://gradescope.com/courses/4095}{gradescope}}
\def\hnumber{3}
\def\course{\href{https://shelat.ccis.neu.edu/16f-4800}{cs4800 - algorithms - f'16}}
%-------------------------------------

\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02} 
\definecolor{cit}{rgb}{0.05,0.2,0.45} 
%\pagestyle{myheadings}
\markboth{\yourname}{\yourname}

\thispagestyle{empty}

\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
   \renewcommand{\thepage}{H\hnumber-\arabic{page}}
   \noindent
   \begin{center}
      \vbox{
    \hbox to \columnwidth {\sc{\course} --- shelat/nguy{\~{\^{e}}}n \hfill}
    \vspace{-2mm}
    \hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
      }
   \end{center}
   \vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent\textbf{Solution:}#1}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\usepackage{clrscode}
\usepackage[T1]{fontenc}

\begin{document}
\handout
\begin{itemize}
\item The assignment is due at Gradescope on Saturday, November 5 at 11:59pm. Late assignments will not be accepted. Submit early and often.

\item You are permitted to study with friends and
      discuss the problems; however, {\em you must write up you own
        solutions, in your own words}. Do not submit anything you
        cannot explain. 
     If you do collaborate with any of the other students on any
      problem, please do list all your collaborators in your
      submission for each problem. 
      
      \item Finding solutions to homework problems on the web, or by asking
 students not enrolled in the class is strictly prohibited. 

\item We require that all homework submissions are prepared in Latex. If you need to draw any diagrams,
however, you may draw them with your hand.  Please use \emph{a new page to begin each answer.} 
\end{itemize}



\begin{problem} Programming Prim \end{problem}
In this problem, you will program Prim's MST algorithm in function \texttt{calculateTree} in the file \texttt{Prim.java} that accompanies this homework.  The source file describes the input and the expected output. You should use the Heap datastructure that we provide for you in the file \texttt{Heap.java} and you can consult \texttt{HeapTest.java} to see how to use the class.


\begin{problem} Programming Dijkstra \end{problem}
In this problem, you will program Dijkstra's algorithm in the function \texttt{calculatePaths} in the file \texttt{Dijkstra.java} that accompanies this assignment.

\begin{problem} Steiner tree approximation \end{problem}
The Steiner tree problem is very closely related to the minimum spanning tree, but it has one extra \emph{flexibility} which makes the problem much harder to solve.  In the Steiner tree problem, you are given a graph $G=(V,E)$, and you wish to find a tree of minimum weight that connects  the nodes in some subset $R\subset V$ (i.e. not all the nodes in $V$ have to be connected). This problem can be used to place fire stations on intersections in a city so as to minimize the travel time to any particular house, or, in our case, it will help the City of Boston design a new bus system that helps connect all of \emph{your} favorite landmarks in Boston.

In this problem, we are going to use the functions \texttt{calculateTree} and \texttt{calculatePaths} to find an \emph{approximate} Steiner tree for a graph $G$. The algorithm works as follows:
 \begin{enumerate}
 	\item For each node $x\in R$, compute the shortest paths $\delta_{x,y}$ for all the other nodes $y\in R$ using \texttt{calculatePaths}.
	\item Create a new graph $G_R=(R,E_R)$ where the edges $E_R$ are the complete set of edges between all nodes.  Define new weights $w_R(x,y)$ for the edge between $x,y\in R$ to be $\delta(x,y)$ that was computed in the previous step.
	\item Now compute a minimum spanning tree $T_R$ on $G_R$ using \texttt{calculateTrees}.
	\item Now solve the original problem by extending $T_R$ into a tree for $G$ as follows: for each edge $(x,y)\in T_R$, replace the edge with the shortest path from $x$ to $y$ computed in the first step.
\end{enumerate}

Complete the function \texttt{main} in the file \texttt{Steiner.java} with the algorithm above.  We have included a \texttt{graph.txt} file which contains all of the streets in Boston, and methods to read that graph, and to read a file of special locations from \texttt{locations.txt}.  Our stub program also provides a method to write your tree to a KML file which can be viewed using either Google Earth or Google Maps (use google to discover how).

\noindent The image below shows a sample tree rendered in Google Earth based on the locations file.

\noindent \includegraphics[width=\columnwidth]{steiner/tree.png}


	



\begin{problem} Another all pairs shortest path \end{problem}

Set $\textsc{bshort}_{i,j,k}$ to be the shortest path from $i$ to $j$ that uses at most $k$ edges.  Note this is different from the $\textsc{ashort}$ variable that we used in class in that we do not restrict the intermediate nodes to be  $1\ldots k$ in this formulation. State a recursive formula for $\textsc{bshort}$.    Devise an algorithm that uses this recurrence.  What is the running time of this algorithm?


\begin{problem}Negative Cycles\end{problem}
In lecture, we argued that the Bellman-Ford algorithm can be made to detect a negative
cycle by running for one more iteration and seeing if any of the verticies have a shorter
path.  Prove this by showing that if graph $G=(V,E,w)$ has a negative cycle, then there exists a vertex $v\in V$ for which $\textsc{short}_{V-1,v} > \textsc{short}_{V,v}$.







\end{document}
