\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{fullpage}
% \usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012 \\
	\rm
	Homework 12\\
	Due Thursday, April 12
\end{center}
 
\begin{enumerate}
 \item \Points{35} \Name{DC-Tree!}
         You've been hired by \verb+Nile.com+, a new online bookstore.   Nile's warehouses have 
         tracks embedded in the floor and a collection of $k$ robots move along these tracks picking
         up books, etc.   The network of tracks form a rectilinear tree:
         There are no cycles and each piece of track is straight.  Notice that the tracks are continuous 
        so a robot can be located at any point along the track.   In other words, any undirected acyclic graph
        in which the edges are drawn as straight line segments forms a legitimate network of track
         except that the robots can be located anywhere along any edge of the tree and not just at the vertices.
         
         Generalize the $DC$ line algorithm that we saw in class to a similar algorithm for rectilinear trees.  Describe
         the algorithm very carefully.  Then show that your algorithm is still $k$-competitive.     
        
        Recall that in the DC line algorithm, all robots that can ``see'' the request -- that is, those that do not have another robot between them and the request point -- move towards it.  Your algorithm for the tree will need to generalize this notion.
        Since you are now operating in a tree, a robot may ``see'' the request point and move towards it, but then have its ``view'' of the request point cut-off by another robot.
        Thus, your algorithm will have some number of robots moving initially.  At some point, some
         of the robots may stop moving while others continue.  Later, a few more robots may stop moving.  
         To make your analysis as clean and clear as possible, it's helpful to divide your analysis into a number of ``phases'' where the first phase is the time period when the initial group of robots are moving.
         That phase ends and the next one begins the moment one or more robots stop moving.
\end{enumerate}

 \end{document}