\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 23 November+ −
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.+ −
Make sure the files you submit can be processed by just calling+ −
\texttt{scala <<filename.scala>>}. + −
+ −
+ −
\subsection*{Disclaimer}+ −
+ −
It should be understood that the work you submit represents+ −
your own effort. You have not copied from anyone else. An+ −
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+ −
+ −
\newpage+ −
\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+ −
$1$ million. \hfill[2 Marks]+ −
+ −
\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 1 to 1 million where $837,799$ takes 525 steps+ −
%%\item[$\bullet$] $1 - 10$ million where $8,400,511$ takes 686 steps+ −
\end{itemize}\bigskip+ −
+ −
+ −
+ −
\subsection*{Part 2 (4 Marks)}+ −
+ −
This part is about list processing---it's a variant of+ −
``buy-low-sell-high'' in Scala. It uses the online financial data+ −
service from Yahoo.\bigskip + −
+ −
\noindent+ −
\textbf{Tasks (file trade.scala):}+ −
+ −
\begin{itemize}+ −
\item[(1)] Given a list of prices for a commodity, for example+ −
+ −
\[+ −
\texttt{List(28.0, 18.0, 20.0, 26.0, 24.0)}+ −
\]+ −
+ −
\noindent+ −
you need to write a function that returns a pair of indices for when+ −
to buy and when to sell this commodity. In the example above it should+ −
return the pair $\texttt{(1, 3)}$ because at index $1$ the price is lowest and+ −
then at index $3$ the price is highest. Note the prices are given as+ −
lists of \texttt{Double}s.\newline \mbox{} \hfill[1 Mark]+ −
+ −
\item[(2)] Write a function that requests a comma-separated value (CSV) list+ −
from the Yahoo websevice that provides historical data for stock+ −
indices. For example if you query the URL+ −
+ −
\begin{center}+ −
\url{http://ichart.yahoo.com/table.csv?s=GOOG}+ −
\end{center}+ −
+ −
\noindent where \texttt{GOOG} stands for Google's stock market symbol,+ −
then you will receive a CSV-list of the daily stock prices since+ −
Google was listed. You can also try this with other stock market+ −
symbols, for instance AAPL, MSFT, IBM, FB, YHOO, AMZN, BIDU and so+ −
on. + −
+ −
This function should return a List of strings, where each string+ −
is one line in this CVS-list (representing one day's+ −
data). Note that Yahoo generates its answer such that the newest data+ −
is at the front of this list, and the oldest data is at the end.+ −
\hfill[1 Mark]+ −
+ −
\item[(3)] As you can see, the financial data from Yahoo is organised in 7 columns,+ −
for example+ −
+ −
{\small\begin{verbatim}+ −
Date,Open,High,Low,Close,Volume,Adj Close+ −
2016-11-04,750.659973,770.359985,750.560974,762.02002,2126900,762.02002+ −
2016-11-03,767.25,769.950012,759.030029,762.130005,1914000,762.130005+ −
2016-11-02,778.200012,781.650024,763.450012,768.700012,1872400,768.700012+ −
2016-11-01,782.890015,789.48999,775.539978,783.609985,2404500,783.609985+ −
....+ −
\end{verbatim}}+ −
+ −
\noindent+ −
Write a function that ignores the first line (the header) and then+ −
extracts from each line the date (first column) and the Adjusted Close+ −
price (last column). The Adjusted Close price should be converted into+ −
a \texttt{Double}. So the result of this function is a list of pairs where the+ −
first components are strings (the dates) and the second are doubles+ −
(the adjusted close prices).\newline\mbox{}\hfill\mbox{[1 Mark]}+ −
+ −
\item[(4)] Write a function that takes a stock market symbol as+ −
argument (you can assume it is a valid one, like GOOG or AAPL). The+ −
function calculates the \underline{dates} when you should have+ −
bought the corresponding shares (lowest price) and when you should+ −
have sold them (highest price).\hfill\mbox{[1 Mark]}+ −
\end{itemize}+ −
+ −
\noindent+ −
\textbf{Test Data:}+ −
In case of Google, the financial data records 3077 entries starting+ −
from 2004-08-19 until 2016-11-04 (which is the last entry on the day+ −
when I prepared the course work...namely on 6 November; remember stock+ −
markets are typically closed on weekends and no financial data is+ −
produced then; also I did not count the header line). The lowest+ −
shareprice for Google was on 2004-09-03 with \$49.95513 per share and the+ −
highest on 2016-10-24 with \$813.109985 per share.\bigskip+ −
+ −
\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).+ −
+ −
Since the question about Mr Drumb's business acumen remains open, let's do a+ −
quick back-of-the-envelope calculation in Scala whether his claim has+ −
any merit. Let's suppose we are given \$100 in 1978 and we follow a+ −
really dump investment strategy, namely:+ −
+ −
\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).+ −
\item We do this for 38 years until January 2016 and check what would+ −
have become out of our \$100.+ −
\end{itemize}\medskip + −
+ −
\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: + −