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

\title{CS140 - Assignment 4\\\small{Due: Sunday,  Feb. 19 at 8pm}}
\author{}
\date{}


\begin{document}
\maketitle

\begin{center}
\includegraphics[scale=0.6]{figures/entomology.jpg}

\footnotesize{http://www.xkcd.com/1012/}
\end{center}

\noindent You may (and are encouraged) to work with a partner on this assignment.  It can be anyone in the class or you may also choose not have to work with a partner.

\noindent \emph{Looking ahead:} For the next assignment (Assignment 5) if you decide you want to work with a partner I will ask for you to work with someone that you haven't previously worked with.

\begin{enumerate}

\item \textbf{[25 points]} Stock Market Problem - the code

Implement your algorithm from the previous assignment for the stock market problem in Python, C, or
  Java (ask me first if you want to use another language).

  Your code must allow the user to specify two filenames, say {\tt
    infile.txt} and {\tt outfile.txt} on the command line (we don't
  want to edit your code).  For example:
  \begin{itemize}
  \item If using C, your code might be compiled and executed as follows:
\begin{verbatim}
  % gcc stockmarket.c -o stockmarket
  % ./stockmarket infile.txt outfile.txt
\end{verbatim}
\item If using Python 3\footnote{See the
  \url{https://docs.python.org/3/howto/argparse.html} module.}, your
  code might be executed as follows:
\begin{verbatim}
  % python3 stockmarket.py infile.txt outfile.txt
\end{verbatim}
\item If using Java\footnote{See \url{https://docs.oracle.com/javase/tutorial/essential/environment/cmdLineArgs.html}}, your code might be compiled and
  executed as follows:
\begin{verbatim}
  % javac StockMarket.java
  % java StockMarket infile.txt outfile.txt
\end{verbatim}
  \end{itemize}
    
  The contents of the input file will be in the
  following form:
  \begin{verbatim}
    8
    42
    40
    45
    45
    44
    43
    50
    49
\end{verbatim}
The first line specifies the number of days (which may not always be a power of 2).  The
following lines give the value of the stock on each day.  

In this case the output file should contain the following:
\begin{verbatim}
    3
    2
    40
    45
    45
\end{verbatim}
The first line gives the length of the longest non-decreasing subsequence,
the second line gives the day on which the subsequence begins (note the
1-based indexing!), and the rest of the lines give the prices of the
stock on the days included in the subsequence.  If there is more than one
longest non-decreasimg subsequence, your code can return either one.

Most of the grade for this problem will be based on correctly implementing a
divide-and-conquer algorithm that solves the problem described in
last week's assignment.  Note that we will evaluate outputs using
{\tt diff} so please make sure your output 
is in the format described above!  We may also
consider code efficiency in an absolute (wall clock) sense.  

(Small) sample input and output files are on the course webpage.


\item \textbf{[25 points]} More Fun with Binary Search Trees
 
\begin{enumerate}

\item \textbf{[5 points]} Is the operation of deletion ``commutative'' in that deleting $x$ and then $y$ from a binary search tree always leaves the same tree as deleting $y$ and then $x$? Argue why it is or give a counterexample.  \textit{Hint:} There are three different cases for deleting in a binary tree.  Make sure you think about all of them. (We'll use the algorithm discussed in class, i.e., if a node has two children, it is replaced with its successor.)

\item \textbf{[20 points]} Balanced? 

Red-black trees maintain a set of five properties; in class we showed
that maintaining those properties guarantees that the height of a
red-black tree with $n$ nodes is never more than $2\log(n+1)$.
Consider another balanced binary search tree which maintains the
following invariant: for any node $x$, the heights of the left and
right subtrees of $x$ differ by at most $1$.  We'll call these 1off
trees.

\begin{enumerate}
\item {[14 points]} Prove by strong induction on the height of the tree that a 1off
  tree with height $h$ has at least $f(h)$ nodes, where $f(h)$ is the
  $h$th Fibonacci number.  (Recall that $f(n) = f(n-1)+f(n-2)$ and
  that $f(0) = f(1) = 1$.)
\item {[3 points]} Use the previous part to show that a 1off tree with height $h$ has
  at least $2f(h-2)$ nodes.
\item {[3 points]} Finally show that a 1off tree with $n$ nodes has $O(\log n)$ height.
\end{enumerate}

\end{enumerate}


\subsection*{Submitting}

On Gradescope, you'll see two separate entries for this assignment (Assignment 4.1 for problem 1 and Assignment 4.2 for problem 2).  For problem 1, submit your code as a single file with the appropriate extension.  For problem 2, your answer should be a pdf, like you usually submit.


\end{enumerate}
\end{document}
