This is pdfTeX, Version 3.141592653-2.6-1.40.22 (MiKTeX 21.3) (preloaded format=pdflatex 2021.4.25) 20 JUN 2021 12:07 entering extended mode **%%Do not change font size *\documentclass[12pt]{article} (/home/vip/.miktex/texmfs/install/tex/latex/tools/.tex LaTeX2e <2020-10-01> patch level 1 L3 programming layer <2020-10-05> xparse <2020-03-03> File ignored) *\usepackage{amsthm,amssymb,fullpage} (/home/vip/.miktex/texmfs/install/tex/latex/base/article.cls Document Class: article 2020/04/10 v1.4m Standard LaTeX document class (/home/vip/.miktex/texmfs/install/tex/latex/base/size12.clo File: size12.clo 2020/04/10 v1.4m Standard LaTeX file (size option) ) \c@part=\count175 \c@section=\count176 \c@subsection=\count177 \c@subsubsection=\count178 \c@paragraph=\count179 \c@subparagraph=\count180 \c@figure=\count181 \c@table=\count182 \abovecaptionskip=\skip47 \belowcaptionskip=\skip48 \bibindent=\dimen138 ) *\begin{document} (/home/vip/.miktex/texmfs/install/tex/latex/amscls/amsthm.sty Package: amsthm 2020/05/29 v2.20.6 \thm@style=\toks15 \thm@bodyfont=\toks16 \thm@headfont=\toks17 \thm@notefont=\toks18 \thm@headpunct=\toks19 \thm@preskip=\skip49 \thm@postskip=\skip50 \thm@headsep=\skip51 \dth@everypar=\toks20 ) (/home/vip/.miktex/texmfs/install/tex/latex/amsfonts/amssymb.sty Package: amssymb 2013/01/14 v3.01 AMS font symbols (/home/vip/.miktex/texmfs/install/tex/latex/amsfonts/amsfonts.sty Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support \@emptytoks=\toks21 \symAMSa=\mathgroup4 \symAMSb=\mathgroup5 LaTeX Font Info: Redeclaring math symbol \hbar on input line 98. LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold' (Font) U/euf/m/n --> U/euf/b/n on input line 106. )) (/home/vip/.miktex/texmfs/install/tex/latex/preprint/fullpage.sty Package: fullpage 1999/02/23 1.1 (PWD) \FP@margin=\skip52 ) (/home/vip/.miktex/texmfs/install/tex/latex/l3backend/l3backend-pdftex.def File: l3backend-pdftex.def 2020-09-24 L3 backend support: PDF output (pdfTeX) \l__kernel_color_stack_int=\count183 \l__pdf_internal_box=\box47 ) No file texput.aux. \openout1 = `texput.aux'. LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for TS1/cmr/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 0. LaTeX Font Info: ... okay on input line 0. * (Please type a command or say `\end') *\begin{center} *\begin{tabular}{|c|} LaTeX Font Info: Trying to load font information for U+msa on input line 0. (/home/vip/.miktex/texmfs/install/tex/latex/amsfonts/umsa.fd File: umsa.fd 2013/01/14 v3.01 AMS symbols A ) LaTeX Font Info: Trying to load font information for U+msb on input line 0. (/home/vip/.miktex/texmfs/install/tex/latex/amsfonts/umsb.fd File: umsb.fd 2013/01/14 v3.01 AMS symbols B ) *\hline *CS 5800: Algorithms \hspace{9cm} Virgil Pavlu\\ *{\bfseries \large Homework 5: Dynamic Programming part I}\\ \hline * (Please type a command or say `\end') *\end{tabular} *\end{center} * (Please type a command or say `\end') *%\section{Write here} *% \textbf{\large{Instructions}} *% *% \begin{enumerate} *% \item Please review the grading policy outlined in the course information p age. *% \item You must also write down with whom you worked on the assignment. If th is 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 number s, the actual exercises and their solutions are different, so make sure you are using the $3^{rd}$ edition. *% \end{enumerate} * (Please type a command or say `\end') * (Please type a command or say `\end') *\textbf{\large{Problems}} *\begin{enumerate} *\item (15 pts) Exercise 15.4-5 (if you did not submit it for previous HW). *\item (15 pts) Exercise 15.2-1. * (Please type a command or say `\end') *% \item (15 pts) Exercise 15.2-3. *\item (15 pts) Exercise 15.3-2. *\item (20 pts) Exercise 15.3-5. *\item (20 pts) Problem 15-5. *\item (30 pts) (Note: you should decide to use Greedy or DP on this problem) P rof. Curly is planning a cross-country road-trip from Boston to Seattle on Inte rstate 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 variou s price wars among them, it might actually be cheaper to rent one car from Bost on 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. * (Please type a command or say `\end') *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 contrai nts. (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$ majo r cities along Interstate 90 and ordered them from East to West, where City 1 i s 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 algo rithm which solves this problem, argue that your algorithm is correct, and anal yze its running time and space requirements. Your algorithm or algorithms shoul d 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} * (Please type a command or say `\end') *\end{document} [1 {/home/vip/.miktex/texmfs/data/pdftex/config/pdftex.map}] (texput.aux) Here is how much of TeX's memory you used: 1038 strings out of 482160 14377 string characters out of 2932112 269928 words of memory out of 3000000 17403 multiletter control sequences out of 15000+200000 540347 words of font info for 49 fonts, out of 3000000 for 9000 0 hyphenation exceptions out of 8191 46i,7n,55p,915b,209s stack positions out of 5000i,500n,10000p,200000b,50000s Output written on texput.pdf (1 page, 44431 bytes). PDF statistics: 18 PDF objects out of 1000 (max. 8388607) 0 named destinations out of 1000 (max. 500000) 1 words of extra memory for PDF output out of 10000 (max. 10000000)