\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms, Section 2 \\
Spring 2003 \\
\rm
Homework 8a\\
Due Thursday, March 27 \\
\end{center}


This following two problems are challenging but important;
please \emph{start thinking about them right away}.  
By all means, come and talk to Belinda if you have any questions about
the graph algorithms we've discussed so far in class (or if you need
candy, conversation, a skate-boarding lesson, etc.).
In addition to regular office hours, the usual Wednesday night time is
available; I'll be in my office around 9:30 and leave before 10pm if no
one shows up.

\begin{enumerate}

\item \textbf{[20 Points] Diameters.}
In this problem we will consider connected undirected graphs with
no cycles.  There are no weights on the edges.  The graphs are simply represented with
adjacency lists.  The distance between two vertices in such a graph is just the minimum number
of edges on a path between the vertices.  The \emph{diameter} of the graph is the maximum
distance between all pairs of vertices.  Make sure that you understand this definition well
before proceeding!
Now, describe an algorithm for computing the diameter of
a connected undirected graph with no cycles.  Carefully analyze and explain the running time
of your algorithm.  \emph{For full credit, your algorithm should be as fast as possible.}

        \item {\bf [25 points] An Algorithmic Get-Rich-Quick Scheme!}
        Your job at Millisoft was fun for awhile, but your reputation
        has gotten out and you've been hired back by the
        brokerage firm of Weil, Proffet, and Howe at a whopping
        salary.   (We won't be specific about the actual amount, but let's just
        say that your salary is most easily expressed using 
        scientific notation!)
        
        Weil, Proffet, and Howe has just entered the {\bf arbitrage}
        business.  Arbitrage is a money-making scheme involving
        anomalies in international currency exchange rates.
        For example, imagine that 1 U.S. dollar
        buys 0.8 Zambian kwachas, 1 Zambian kwacha buys 10 Mongolian
        tughriks, and 1 Mongolian tughrik buys 0.15 U.S. dollars.
        Then, by converting currencies, a trader can start with 1 U.S.
        dollar and buy $0.8 \times 10 \times 0.15 = 1.2$ U.S. dollars.
        By capitalizing on such anomalies quickly (before they're
        detected and corrected by the markets), huge amounts of money can be made.

        We'll assume that we're given $n$ currencies and the exchange
        rate between every pair of currencies.  That is, we are given
        currencies $c_{1}, \ldots, c_{n}$ and an
        $n \times n$ table $R$ such that one unit of currency $c_{i}$
        buys $R[i,j]$ units of currency $c_{j}$.

        \begin{enumerate}
                \item We'll begin with the following problem.
                Given the list of currencies and exchange rates and
                a particular currency $c_{i}$, determine the maximum
                amount of each currency that you can obtain, beginning
                with 1 unit of currency $c_{i}$.  \emph{For this part of
                the problem assume that there exist
                no cycles that allow you to get arbitrarily rich
                via arbitrage.}  Describe \emph{two} different algorithms for
                doing this - one based on a modification of Floyd-Warshall and
                one based on a modification of Bellman-Ford.  (Your algorithms can be
described in English.  Pseudo-code is not necessary.)
                Explain briefly 
                why each algorithm works.  Finally, explain the running times of
                each of the two algorithms.  

                \item Now assume that the exchange rates are such that it may be possible
	     to get rich via arbitrage.  That is, there may exist a cycle of currency exchanges that allows you to make more of your starting currency than you had initially.  Describe how you could modify each of your algorithms to determine
if
                it's possible to profit from arbitrage with the given
                currencies and exchange rates.  Prove that each of your
                modified algorithm works.  

	      \item Finally, describe and analyze the running time of an algorithm for finding the actual  sequence of currencies to be exchanged
	     that makes a profit using arbitrage, if such a cycle exists.   
        \end{enumerate}
\end{enumerate}




\end{document}

