%%Do not change font size
\documentclass[12pt]{article}
\usepackage{amsthm,amssymb,fullpage}
\begin{document}

\begin{center}
\begin{tabular}{|c|}
\hline
CS 5800: Algorithms \hspace{9cm} Virgil Pavlu\\
{\bfseries \large Homework 5: Dynamic Programming part I}\\ \hline

\end{tabular}
\end{center}

%\section{Write here}
% \textbf{\large{Instructions}}
% 
% \begin{enumerate}
% \item Please review the grading policy  outlined in the course information page.
% \item You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.
% \item Problem numbers (like Exercise 3.1-1) are corresponding to CLRS $3^{rd}$ edition. While the $2^{nd}$ edition has similar problems with similar numbers, the actual exercises and their solutions are different, so make sure you are using the $3^{rd}$ edition.
% \end{enumerate}


\textbf{\large{Problems}}
\begin{enumerate}
\item (15 pts) Exercise 14.4-5 (if you did not submit it for previous HW).
\item (15 pts) Exercise 14.2-1.
  
% \item (15 pts) Exercise 14.2-3.
\item (optional, no credit) Exercise 14.3-2.
\item (20 pts) Exercise 14.3-5.
\item (20 pts) Problem 14-5.
\item (30 pts) (Note: you should decide to use Greedy or DP on this problem) Prof. Curly is planning a cross-country road-trip from Boston to Seattle on Interstate 90, and he needs to rent a car. His first inclination was to call up the various car rental agencies to find the best price for renting a vehicle from Boston to Seattle, but he has learned, much to his dismay, that this may not be an optimal strategy. Due to the plethora of car rental agencies and the various price wars among them, it might actually be cheaper to rent one car from Boston to Cleveland with Hertz, followed by a second car from Cleveland to Chicago with Avis, and so on, than to rent any single car from Boston to Seattle.

Prof. Curly is not opposed to stopping in a major city along Interstate 90 to change rental cars; however, he does not wish to backtrack, due to time contraints. (In other words, a trip from Boston to Chicago, Chicago to Cleveland, and Cleveland to Seattle is out of the question.) Prof. Curly has selected $n$ major cities along Interstate 90 and ordered them from East to West, where City 1 is Boston and City $n$ is Seattle. He has constructed a table $T[i,j]$ which for all $i < j$ contains the cost of the cheapest single rental car from City $i$ to City $j$. Prof. Curly wants to travel as cheaply as possible. Devise an algorithm which solves this problem, argue that your algorithm is correct, and analyze its running time and space requirements. Your algorithm or algorithms should output both the total cost of the trip and the various cities at which rental cars must be dropped off and/or picked up. 
\end{enumerate}

\end{document}
