\documentclass[12pt,twoside]{article}
\usepackage{amsmath,graphicx}
\newcommand{\profs}{Professors Ron Rivest and Srini Devadas}
\newcommand{\subj}{6.006}
\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}
\newcommand{\htitle}[3]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}
{\textit{Introduction to Algorithms: 6.006}\hfill\name\newline
Massachusetts Institute of Technology \hfill #3\newline
\profs\hfill Handout #1\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf #2}\end{center}}
\newcommand{\handout}[3]{\thispagestyle{empty}
\markboth{Handout #1: #2}{Handout #1: #2}
\pagestyle{myheadings}\htitle{#1}{#2}{#3}}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\newcommand{\name}{INSERT NAME HERE}
\begin{document}
\handout{9}{Problem Set 3}{October 11, 2007}
\setlength{\parindent}{0pt}
\newcommand{\solution}{
\medskip
{\bf Solution:}
}
\newcommand{\collaborators}[1]{
\qquad {\bf Collaborators:} #1
}
This problem set is due {\bf October 23} at {\bf 11:59PM}.
Solutions should be turned in through the course website in PS or PDF
form using \LaTeX\ or scanned handwritten solutions, or they may be
handwritten and turned in to a member of the 6.006 course staff on or
before the due date. Hand-drawn diagrams may also be referenced in
your \LaTeX\ writeup and turned in at the next day's recitation.
A template for writing up solutions in \LaTeX\ is available on the
course website.
\medskip
\hrulefill
\medskip
Exercises are for extra practice and should not be turned in.
{\bf Exercises:}
\begin{itemize}
\item Consider the amount of memory used in a dynamic programming
approach to a problem. Show, by means if illustration, that even
though you do need to solve all subproblems and save their solutions
for later use, you might not need to save all of the these solutions
\emph{simultaneously}; the memory actually used might be less than
the number of subproblems.
\item Is there any significant difference between the following two
approaches to dynamic programming, in terms of their efficiency?
\begin{enumerate}
\item Solve all subproblems, in order of size, from smallest to
largest.
\item Solve each problem and subproblem recursively, starting with
the largest subproblem, but saving (via memoization) previous
solutions to a subproblem to avoid having to solve it more than
once.
\end{enumerate}
Explain.
\item Exercise 15.3-5 from CLRS.
\end{itemize}
\hrulefill
\begin{enumerate}
\item Image Compression
In the image compression example in class, we divided up the image
into $k \times k$ blocks and found the ``best'' partition of the
image into $t$ non-overlapping monochrome rectangles, with each
rectangle a union of blocks. We used the sum of squares of
differences between the actual pixel values and the average pixel
value in each region as a metric for deciding what partition was
``best''. Suppose that instead, our metric was the sum of squares
of differences between the actual pixel values and the \emph{median}
pixel value in a region.
{\bf (8 points)} Explain why dynamic programming may not be a good
approach to finding the ``best'' partition of the image in this
case.
\item Tris
In this problem, we consider a simplified version of Tetris. (If
you are not familiar with this game, ask a TA or look it up on
Wikipedia.)
In this game, each piece is made from 3 squares, so it is either a
``bar'' (3 in a row) or an ``ell''. Rotations are not allowed, so
there are 2 types of bars and 4 types of ells, accounting for
orientation.
Let us assume that the playing field is three squares wide and
arbitrarily tall. The pieces fall from top to bottom, one at a
time, and can be shifted left and right but not rotated, until they
rest on the bottom of the playing field or a previously placed
piece. Once a pieces ``touches down'', it can't be moved further
(e.g. horizontally). Lines are not cleared when they fill up.
Suppose you know ahead of time what the sequence of $n$ pieces will
be (bars or ells and their orientations). How well can the pieces
be packed into the bottom?
Give an algorithm to minimize the total height (height of the
highest column) of the stack of pieces, and among stacks with the
the minimum height, to minimize the number of ``holes'' (unfilled
squares that are below any filled squares). That is, your algorithm
returns the height and the number of holes.
A: \includegraphics[width=1cm]{ell-ul} \qquad \qquad
B: \includegraphics[width=1cm]{ell-dr}
For example, consider these ell pieces A and B. If we get two A
pieces, the smallest height is 3, with 1 hole; with 2 B pieces, we
can get height 3 with 2 holes; with A followed by B, height 2 with 0
holes; and with B followed by A, height 4 with 1 hole.
\emph{Hint:} Consider the ``state'' of the the puzzle after $k$
pieces have been placed as a triple $(a,b,c)$ where $a+b+c=3k+h$,
representing the height of the stack in columns 1, 2, and 3
respectively, where $h$ is the number of holes.
\begin{enumerate}
\item {\bf (12 points)} Explain carefully how your algorithm works.
\item {\bf (8 points)} Show that your algorithm runs in time
polynomial in $n$.
\item {\bf Optional:} Describe an algorithm to solve this problem
when rotations are permitted, and explain how the problem is
different.
\item {\bf Optional:} Does your approach generalize to standard
Tetris? What if filled lines in Tetris no longer are cleared?
\end{enumerate}
\item Winning the Stock Market
Suppose you started with \$1000 on the day you were born. If you had
perfect future knowledge of daily stock prices, how much money could
you have had on January 1, 2007, and what trades would you have had
to make to get there?
To put some limits on the open-ended nature of this question, we
introduce a few restrictions:
\begin{itemize}
\item You may only trade the 30 stocks in the current Dow Jones
Industrial Average. The daily stock price data is available in
the 6.006 locker on Athena in /mit/6.006/stocks/ or from
http://courses.csail.mit.edu/6.006/fall07/data/stocks/.
\item You may only buy and sell at the daily closing price (use the
``adjusted close'' column in the data, which takes stock splits into
account).
\item You may only execute trades, in which you change some
combination of cash and stocks for a different combination of cash
and stocks of an equal value, at most once every 60 days.
\item You are allowed to hold fractional numbers of shares. There
is no upper bound on the number of shares you can have.
\item You may not short sell stocks.
\item At the end, you must hold only cash (no stocks).
\end{itemize}
You may find the \texttt{csv} package useful for reading the
comma-separated-values price data files, and the \texttt{date} class
from the \texttt{datetime} package useful for manipulating dates.
\texttt{csv} documentation is available from
http://docs.python.org/lib/module-csv.html; for \texttt{date}, see
http://docs.python.org/lib/datetime-date.html.
An example usage of csv to read all the stock prices of IBM into a
list L:
\texttt{L = list(csv.reader(open("IBM.csv")))}
An example of finding the number of days' difference between two
dates:
\texttt{(datetime.date(2007,10,11) - datetime.date(2007,9,4)).days}
\begin{enumerate}
\item{\bf (4 points)} Show that the optimal strategy is never to
hold more than one kind of stock.
\emph{Note:} For this part, it is important that you can hold
fractional shares!
\item{\bf (12 points)} Let $d$ be the total number of days with
price data, $n$ be the total number of allowable stocks, and $t$
the minimum number of days between trades. Give an efficient
dynamic programming algorithm and describe its running time in
terms of $d$, $n$, and $t$.
\item{\bf (2 points)} How much money would you have had on January
1, 2007?
\item{\bf (1 point)} Suppose there is a 1\% transaction fee
associated with each trade. That is, if you owned 100 shares of
X, each worth \$10, and the price of a share of Y were \$5, you
could sell X and receive \$990, or sell X and buy Y, receiving
198 shares of Y. How much money would you have had on January 1,
2007?
\item{\bf (1 point)} Suppose there is a 10\% transaction fee.
How much money would you have had on January 1, 2007?
\item{\bf (2 points)} What is the average yearly rate of return
$r$ on your initial investment for each of the previous 3 parts?
$(1+r)^t$ should be the ratio of your final amount to your
initial investment, where $t$ is the time between the day you
were born and January 1, 2007 in years (possibly fractional).
\end{enumerate}
The items you should turn in are:
\begin{itemize}
\item{\bf (10 points)} Your code, containing a function
\texttt{most\_money(fee)}, which returns the amount of money you
would have on January 1, 2007, starting with \$1000 on the day you
were born, with \texttt{fee} = 0, 0.01, or 0.1 for each of the
three cases. You can assume that the .csv data files will be in
the same directory from which your function will be run.
\item A file listing the optimal trades for each
of the three cases: no transaction fee, 1\%, and 10\%.
\end{itemize}
\end{enumerate}
\end{document}