\documentclass{article}

\usepackage{../style}

%%\usepackage{../langs}

\begin{document}

\section*{Coursework 6 (Scala)}

This coursework is about Scala and is worth 10\%. The first and second

part are due on 16 November at 11pm, and the third part on 21 December

at 11pm. You are asked to implement three programs about list

processing and recursion. The third part is more advanced and might

include material you have not yet seen in the first lecture.

\noindent

submissions! They are not needed. This means you cannot use 

\subsection*{Disclaimer}

It should be understood that the work you submit represents

exception is the Scala code I showed during the lectures or

uploaded to KEATS, which you can freely use.\bigskip

\subsection*{Part 1 (3 Marks)}

This part is about recursion. You are asked to implement a Scala

program that tests examples of the \emph{$3n + 1$-conjecture}, also

called \emph{Collatz conjecture}. This conjecture can be described as

follows: Start with any positive number $n$ greater than $0$:

\begin{itemize}

\item If $n$ is even, divide it by $2$ to obtain $n / 2$.

\item If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n +

  1$.

\item Repeat this process and you will always end up with $1$.

\end{itemize}

\noindent

For example if you start with $6$, respectively $9$, you obtain the

series

\[

\begin{array}{@{}l@{\hspace{5mm}}l@{}}

6, 3, 10, 5, 16, 8, 4, 2, 1 & \text{(= 9 steps)}\\

9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1  & \text{(= 20 steps)}\\

\end{array}

\]

\noindent

As you can see, the numbers go up and down like a roller-coaster, but

curiously they seem to always terminate in $1$. The conjecture is that

this will \emph{always} happen for every number greater than

0.\footnote{While it is relatively easy to test this conjecture with

  particular numbers, it is an interesting open problem to

  \emph{prove} that the conjecture is true for \emph{all} numbers ($>

  0$). Paul Erd\"o{}s, a famous mathematician you might have hard

  about, said about this conjecture: ``Mathematics may not be ready

  for such problems.'' and also offered a \$500 cash prize for its

  solution. Jeffrey Lagarias, another mathematician, claimed that

  based only on known information about this problem, ``this is an

  extraordinarily difficult problem, completely out of reach of

  present day mathematics.'' There is also a

  \href{https://xkcd.com/710/}{xkcd} cartoon about this conjecture

  (click \href{https://xkcd.com/710/}{here}). If you are able to solve

  this conjecture, you will definitely get famous.}\bigskip

\noindent

\textbf{Tasks (file collatz.scala):}

\begin{itemize}

\item[(1)] You are asked to implement a recursive function that

  calculates the number of steps needed until a series ends

  with $1$. In case of starting with $6$, it takes $9$ steps and in

  case of starting with $9$, it takes $20$ (see above). In order to

  try out this function with large numbers, you should use

  \texttt{Long} as argument type, instead of \texttt{Int}.  You can

  assume this function will be called with numbers between $1$ and

\item[(2)] Write a second function that takes an upper bound as

  argument and calculates the steps for all numbers in the range from

  1 up to this bound. It returns the maximum number of steps and the

  corresponding number that needs that many steps.  More precisely

  it returns a pair where the first

  component is the number of steps and the second is the

  corresponding number. \hfill\mbox{[1 Mark]}

\end{itemize}

\noindent

\textbf{Test Data:} Some test ranges are:

\begin{itemize}

\item 1 to 10 where $9$ takes 20 steps 

\item 1 to 100 where $97$ takes 119 steps,

\item 1 to 1,000 where $871$ takes 179 steps,

\item 1 to 10,000 where $6,171$ takes 262 steps,

\item 1 to 100,000 where $77,031$ takes 351 steps, 

  %%\item[$\bullet$] $1 - 10$ million where $8,400,511$ takes 686 steps

\noindent

\begin{itemize}

\begin{center}

\end{center}

\noindent

\end{itemize}

\noindent

\subsection*{Advanced Part 3 (3 Marks)}

A purely fictional character named Mr T.~Drumb inherited in 1978

approximately 200 Million Dollar from his father. Mr Drumb prides

himself to be a brilliant business man because nowadays it is

estimated he is 3 Billion Dollar worth (one is not sure, of course,

because Mr Drumb refuses to make his tax records public).

\begin{itemize}

\item We blindly choose a portfolio of stocks, say some Blue-Chip stocks

  or some Real Estate stocks.

\item If some of the stocks in our portfolio are traded in January of

  a year, we invest our money in equal amounts in each of these

  stocks.  For example if we have \$100 and there are four stocks that

  are traded in our portfolio, we buy \$25 worth of stocks

  from each.

\item Next year in January, we look how our stocks did, liquidate

  everything, and re-invest our (hopefully) increased money in again

  the stocks from our portfolio (there might be more stocks available,

  if companies from our portfolio got listed in that year, or less if

  some companies went bust or de-listed).

  have become out of our \$100.

\noindent

\textbf{Tasks (file drumb.scala):}

\begin{itemize}

\item[(1.a)] Write a function that queries the Yahoo financial data

  service and obtains the first trade (adjusted close price) of a

  stock symbol and a year. A problem is that normally a stock exchange

  is not open on 1st of January, but depending on the day of the week

  on a later day (maybe 3rd or 4th). The easiest way to solve this

  problem is to obtain the whole January data for a stock symbol as

  CSV-list and then select the earliest entry in this list. For this

  you can specify a date range with the Yahoo service. For example if

  you want to obtain all January data for Google in 2000, you can form

  the query:\mbox{}\\[-8mm]

  \begin{center}\small

    \mbox{\url{http://ichart.yahoo.com/table.csv?s=GOOG&a=0&b=1&c=2000&d=1&e=1&f=2000}}

  \end{center}

  For other companies and years, you need to change the stock symbol

  (\texttt{GOOG}) and the year \texttt{2000} (in the \texttt{c} and

  \texttt{f} argument of the query). Such a request might fail, if the

  company does not exist during this period. For example, if you query

  for Google in January of 1980, then clearly Google did not exists yet.

  Therefore you are asked to return a trade price as

  \texttt{Option[Double]}.

\item[(1.b)] Write a function that takes a portfolio (a list of stock symbols),

  a years range and gets all the first trading prices for each year. You should

  organise this as a list of lists of \texttt{Option[Double]}'s. The inner lists

  are for all stock symbols from the portfolio and the outer list for the years.

  For example for Google and Apple in years 2010 (first line), 2011

  (second line) and 2012 (third line) you obtain:

\begin{verbatim}

  List(List(Some(313.062468), Some(27.847252)), 

       List(Some(301.873641), Some(42.884065)),

       List(Some(332.373186), Some(53.509768)))

\end{verbatim}\hfill[1 Mark]

\item[(2.a)] Write a function that calculates the \emph{change factor} (delta)

  for how a stock price has changed from one year to the next. This is

  only well-defined, if the corresponding company has been traded in both

  years. In this case you can calculate

  \[

  \frac{price_{new} - price_{old}}{price_{old}}

  \]

\item[(2.b)] Write a function that calculates all change factors

  (deltas) for the prices we obtained under Task 1. For the running

  example of Google and Apple for the years 2010 to 2012 you should

  obtain 4 change factors:

\begin{verbatim}  

  List(List(Some(-0.03573991820699504), Some(0.5399747522663995))

          List(Some(0.10103414428290529), Some(0.24777742035415723)))

\end{verbatim}

  That means Google did a bit badly in 2010, while Apple did very well.

  Both did OK in 2011.\hfill\mbox{[1 Mark]}

\item[(3.a)] Write a function that calculates the ``yield'', or

  balance, for one year for our portfolio.  This function takes the

  change factors, the starting balance and the year as arguments. If

  no company from our portfolio existed in that year, the balance is

  unchanged. Otherwise we invest in each existing company an equal

  amount of our balance. Using the change factors computed under Task

  2, calculate the new balance. Say we had \$100 in 2010, we would have

  received in our running example

  \begin{verbatim}

  $50 * -0.03573991820699504 + $50 * 0.5399747522663995

                                         = $25.211741702970222

  \end{verbatim}

  as profit for that year, and our new balance for 2011 is \$125 when

  converted to a \texttt{Long}.

\item[(3.b)] Write a function that calculates the overall balance

  for a range of years where each year the yearly profit is compounded to

  the new balances and then re-invested into our portfolio.\mbox{}\hfill\mbox{[1 Mark]}

\end{itemize}\medskip  

\noindent

\textbf{Test Data:} File \texttt{drumb.scala} contains two portfolios

collected from the S\&P 500, one for blue-chip companies, including

Facebook, Amazon and Baidu; and another for listed real-estate companies, whose

names I have never heard of. Following the dumb investment strategy

from 1978 until 2016 would have turned a starting balance of \$100

into \$23,794 for real estate and a whopping \$524,609 for blue chips.\medskip

\noindent

\textbf{Moral:} Reflecting on our assumptions, we are over-estimating

our yield in many ways: first, who can know in 1978 about what will

turn out to be a blue chip company.  Also, since the portfolios are

chosen from the current S\&P 500, they do not include the myriad

of companies that went bust or were de-listed over the years.

So where does this leave our fictional character Mr T.~Drumb? Well, given

his inheritance, a really dumb investment strategy would have done

equally well, if not much better.

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: