% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.

\documentclass[12pt,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CS 584/684 Algorithm Design and Analysis}
\def\term{Portland State U, Winter 2021}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { \hfill \large{\course} \hfill }
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill \textbf{#5}  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { \term \hfill \emph{#2}}
       \hbox to 5.78in { {#3 \hfill \emph{#4}}}
      }
   }
   \end{center}
   \vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}

%-----defs and commands-----%
\def\veps{\varepsilon}
\newcommand{\bit}{\{0,1\}}
\newcommand{\negl}{\text{negl}}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
\newcommand{\alg}[1]{\textsf{#1}}
%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
 \studenttrue 
% \studentfalse

\def\texbp{5} % bonus for typing in latex
\def\hwnum{5} %
\def\issuedate{02/09/21} % 
\def\duedate{02/16/21} % 
\def\yourname{your name} % type your name here

%------------------------------%
\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi

\noindent \textbf{Instructions.} This problem set contains \numpages\
pages (including this cover page) and \numquestions\ questions. A
random subset of problems will be graded.

\begin{itemize}
\item Your solutions will be graded on \emph{correctness} and
  \emph{clarity}. You should only submit work that you believe to be
  correct, and you will get significantly more partial credit if you
  clearly identify the gap(s) in your solution. It is good practice to
  start any long solution with an informal (but accurate) summary that
  describes the main idea. You may opt for the ``I take 15\%'' option.

\item You need to submit a PDF file before the deadline. Either a
  clear scan of you handwriting or a typeset document is accepted. You
  will get $\texbp$ bonus points for typing in LaTeX (Download and use
  the accompany TeX file).

\item You may collaborate with others on this problem set. However,
  you must \textbf{{write up your own solutions}} and \textbf{{list
      your collaborators and any external sources}} for each
  problem. Be ready to explain your solutions orally to a course staff
  if asked.

\item For problems that require you to provide an algorithm, you must
  give a precise description of the algorithm, together with a proof
  of correctness and an analysis of its running time. You may use
  algorithms from class as subroutines. You may also use any facts
  that we proved in class or from the book.

\end{itemize}

\newpage

\begin{questions}

  \question[15] Suppose you are given a set $L$ of $n$ line segments
  in the plane, where each segment has one endpoint on the vertical
  line $x = 0$ and one endpoint on the vertical line $x = 1$, and all
  $2n$ endpoints are distinct. Describe an algorithm to compute the
  largest subset of $L$ in which no pair of segments intersects.

\newpage

\question (Shortest path with bounded negative edges) Suppose we are
given a directed graph $G$ with weighted edges and two vertices $s$
and $t$.
\begin{parts}
    \part[15] Describe an algorithm to find the shortest path
    from $s$ to $t$ when exactly one edge in $G$ has negative weight.
\newpage 
    \bonuspart[10] Describe an algorithm to find the
    shortest path from $s$ to $t$ when exactly $k$ edges in $G$ have
    negative weights. How does the running time of your algorithm
    depend on $k$?
\end{parts}
\newpage

\question (Arbitrage) Arbitrage is the use of discrepancies in
currency exchange rates to transform one unit of a currency into more
than one unit of the same currency. For example (exchange rates not
up to date), suppose 1 US dollar buys 71 Indian rupees, 1 Indian rupee
buys 1.6 Japanese yen, and 1 Japanese yen buys 0.0093 US dollars. Then
by converting currencies, a trader can start with 1 US dollar and buy
$71\times 1.6 \times 0.0093 = 1.0565$ US dollars, thus making a profit
of 5.65 percent.

Suppose that you are given $n$ currencies $c_1,c_2,\ldots,c_n$ and an
$n\times n$ table $R$ of exchange rates, such that one unit of
currency $c_i$ buys $R[i,j]$ units of currency $j$.

Describe an algorithm to determine whether or not there exists a
sequence of currencies $\langle c_{i_1},\ldots, c_{i_k}\rangle $ such
that
\[ R[i_1,i_2] \cdot R[i_2,i_3] \cdots R[i_{k-1},i_k]\cdot R[i_k, i_1]
  > 1 \, .\]

You may assume that there is an algorithm to detect negative-weight
cycles in a graph running in time $O(mn)$.

\end{questions}


\end{document}


