\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{url}


\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}

\title{CS140 - Assignment 7\\\small{\emph{Due: Sunday, October 27 at 11:59pm}}}
\author{}
\date{}

\begin{document}

\maketitle

\begin{center}
\includegraphics[scale=0.4]{figures/big_picture.jpg}
\footnotesize{http://www.smbc-comics.com/index.php?db=comics\&id=2217}
\end{center}

\newpage

\noindent For this assignment, you may (and are encouraged to) work with a partner.

\begin{enumerate}

\item \textbf{[5 points]} Huffman codes

Suppose the symbols $a$, $b$, $c$, $d$, $e$ occur with frequencies 30, 20, 15, 40, 60 respectively, in a file.

\begin{enumerate}

\item What is the Huffman encoding of the alphabet?  Note, follow the algorithm in class, where the smallest value is the left branch and the next smallest is the right branch.  For encoding, the left branch will be 0 and the right branch 1.

\item If this encoding is applied to the file, what is the length of the encoded file in bits?

\end{enumerate}
\end{enumerate}

\section*{Greedy or DP}

One of the problems below can be solved more efficiently using a greedy approach and the other cannot (i.e. you must use dynamic programming).  For each problem clearly describe your algorithm and state the run-time.  For the dynamic programming problem, make sure to describe the table and how it is filled in, etc.  For the greedy problem, argue (a formal proof isn't necessary) that your solution is optimal.

\begin{enumerate}

\setcounter{enumi}{1}

\item \textbf{[10 points]} You're going on a road trip with friends.  Unfortunately, your headlights are broken, so you can only drive in the daytime.  Therefore, on any given day you can drive no more than $d$ miles.  You have a map with $n$ different hotels along your path that are potential stopping points and the distances from your start point along your path to each hotel $x_1 < x_2 < ... < x_n$.  Your final destination is the last hotel.  Describe an algorithm that determines which hotels you should stay in if you want to minimize the number of days it takes you to get to your destination.

\item \textbf{[10 points]} Same setup as above, however, you also want to do some sightseeing along the way.  To make sure you don't spend too little or too much time in any one place, you decide to add a penalty for having too much free time.  If you travel $x$ miles in a day, then the penalty for that day is $(d - x)^2$.  Describe an algorithm that determines the hotel sequence that minimizes the total penalty, that is the sum of the daily penalties over all travel days.

\end{enumerate}

\section*{More fun}

\begin{enumerate}

\setcounter{enumi}{3}


\item \textbf{[10 points]} Given a set of points ${x_1, x_2, ..., x_n}$ on the real line, describe a greedy algorithm that determines the smallest set of unit-length (i.e., length=1) closed intervals that contains all of the given points.  State the worst case running time and prove that your algorithm is correct.  You do not need write pseudo-code, but make your description clear.

\end{enumerate}

\end{document}
