10 part is due on 16 November at 11:00, and the second part on 23

    10 part is due on 16 November at 11:00, and the third part on 23 November

    11 November at 11:00. You are asked to implement three programs about

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

    12 list processing and recursion.

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

    13 

    13 include material you have not yet heard about in the first lecture.

    14 \subsubsection*{Disclaimer}

    14 

    15 \subsection*{Disclaimer}

    22 \subsubsection*{Part 1 (3 Marks)}

    23 \subsection*{Part 1 (3 Marks)}

    25 program that tests examples of the \emph{$3n + 1$-conjecture}. This

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

    26 conjecture can be described as follows: Start with any positive number

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

    27 $n$ greater than $0$. If $n$ is even, divide it by $2$ to obtain $n /

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

    28 2$. If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n +

    29 

    29 1$. Repeat this process and you will always end up with $1$.  For

    30 \begin{itemize}

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

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

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

    33   1$.

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

    35 \end{itemize}

    36 

    37 \noindent

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

    39 series

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

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

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

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

    41 curiously they seem to always terminate in $1$.  While it is

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

    42 relatively easy to test this conjecture with particular numbers, it is

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

    43 an interesting open problem to \emph{prove} that the conjecture is

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

    44 true for all numbers ($> 0$). Paul Erd\"o{}s, a famous mathematician

    53   particular numbers, it is an interesting open problem to

    45 you might have hard about, said about this conjecture: ``Mathematics

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

    46 may not be ready for such problems.'' and also offered \$500 cash

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

    47 prize for its solution. Jeffrey Lagarias, another mathematician,

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

    48 claimed that based only on known information about this problem,

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

    49 ``this is an extraordinarily difficult problem, completely out of

    58   solution. Jeffrey Lagarias, another mathematician, claimed that

    50 reach of present day mathematics.'' There is also a

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

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

    60   extraordinarily difficult problem, completely out of reach of

    52 conjecture.\medskip

    61   present day mathematics.'' There is also a

    53 

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

    54 \noindent

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

    55 \textbf{Tasks:} (1) You are asked to implement a recursive function that

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

    56 calculates the number of steps needed number until a series ends with

    65 

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

    66 \newpage

    58 starting with $9$, it takes $20$ (see above). In order to try out this

    67 \noindent

    59 function with large numbers, you should use \texttt{Long} as argument

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

    60 type instead of \texttt{Int}.  You can assume this function will be

    69 

    61 called with numbers between $1$ and $10$ million.

    70 \begin{itemize}

    62 

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

    63 (2) Then write a second function that takes an upper bound as argument

    72   calculates the number of steps needed until a series ends

    64 and calculates the steps for all numbers in the range from 1 upto this

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

    65 bound, and returns the maximum of steps needed by a number in that

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

    66 range. This function should produce for ranges

    75   try out this function with large numbers, you should use

    67 

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

    68 \begin{itemize}

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

    69 \item $1 - 10$ where $9$ takes 20 steps

    78   $1$ million. \hfill[2 Marks]

    70 \item $1 - 100$ where $97$ takes 119 steps,

    79 

    71 \item $1 - 1,000$ where $871$ takes 179 steps,

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

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

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

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

    82   1 upto this bound. It returns the maximum number of steps and the

    74 \item $1 - 1$ million where $837,799$ takes 525 steps, and

    83   corresponding number that needs that many steps.  The first

    75 \item $1 - 10$ million where $8,400,511$ takes 686 steps

    84   component of the pair is the number of steps and the second is the

    76 \end{itemize}  

    85   corresponding number. \hfill[1 Mark]

    77 

    86 \end{itemize}

    78 

    87 

    79 \subsubsection*{Part 2 (4 Marks)}

    88 \noindent

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

    90 

    91 \begin{itemize}

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

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

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

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

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

    97 \item 1 to 1 million where $837,799$ takes 525 steps

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

    99 \end{itemize}\bigskip

   100   

   101 

   102 

   103 \subsection*{Part 2 (4 Marks)}

    82 Buy-low-sell-high in Scala. (1) Given a list of prices for a commodity,

   106 ``buy-low-sell-high'' in Scala. It uses the online financial data

    83 for example

   107 service from Yahoo.\bigskip 

   108 

   109 \noindent

   110 \textbf{Tasks (file trade.scala):}

   111 

   112 \begin{itemize}

   113 \item[(1)] Given a list of prices for a commodity, for example

    90 you need to write a function that returns a pair for when to buy and

   120 you need to write a function that returns a pair of indices for when

    91 when to sell this commodity. In the example above it should return

   121 to buy and when to sell this commodity. In the example above it should

    92 $\texttt{(1, 3)}$ because at index $1$ the price is lowest and then at

   122 return the pair $\texttt{(1, 3)}$ because at index $1$ the price is lowest and

    93 index $3$ the price is highest. Note the prices are given as lists of

   123 then at index $3$ the price is highest. Note the prices are given as

    94 \texttt{Float}s.

   124 lists of \texttt{Float}s. \hfill[1 Mark]

    95 

   125 

    96 (2) Write a function that requests a comma-separated value list from a

   126 \item[(2)] Write a function that requests a comma-separated value (CSV) list

    97 Yahoo websevice that provides historical data for stock indices. For

   127   from the Yahoo websevice that provides historical data for stock

    98 example if you query the URL

   128   indices. For example if you query the URL

   105 then you will receive a comma-separated value list of the daily stock

   135 then you will receive a CSV-list of the daily stock prices since

   106 prices since Google was floated. You can also try this with other

   136 Google was listed. You can also try this with other strock market

   107 strock market symbols, for instance AAPL, MSFT, IBM, FB, YHOO, AMZN,

   137 symbols, for instance AAPL, MSFT, IBM, FB, YHOO, AMZN, BIDU and so

   108 BIDU and so on. This function should return a List of strings, where

   138 on. 

   109 each string is one line in this comma-separated value list

   139 

   110 (representing one days data). Note that Yahoo generates its answer

   140 This function should return a List of strings, where each string

   111 such that the newest data is at the front of this list, and the oldest

   141 is one line in this CVS-list (representing one day's

   112 data is at the end.

   142 data). Note that Yahoo generates its answer such that the newest data

   113 

   143 is at the front of this list, and the oldest data is at the end.

   114 (3) As you can see, the financial data from Yahoo is organised in 7 columns,

   144 \hfill[1 Mark]

   145 

   146 \item[(3)] As you can see, the financial data from Yahoo is organised in 7 columns,

   130 a float. So the result of this function is a list of pairs where the

   162 a \texttt{Double}. So the result of this function is a list of pairs where the

   131 first components are strings (the dates) and the second are floats

   163 first components are strings (the dates) and the second are doubles

   132 (the adjusted close prices).

   164 (the adjusted close prices).\newline\mbox{}\hfill\mbox{[1 Mark]}

   133 

   165 

   134 (4) Write a function that takes a stock market symbol as argument (you

   166 \item[(4)] Write a function that takes a stock market symbol as

   135 can assume it is a valid one, like GOOG, AAPL, MSFT, IBM, FB, YHOO,

   167   argument (you can assume it is a valid one, like GOOG or AAPL). The

   136 AMZN, BIDU). The function calculates the dates when you should have

   168   function calculates the \underline{dates} when you should have

   137 bought Google shares (lowest price) and when you should have sold them

   169   bought the corresponding shares (lowest price) and when you should

   138 (highest price).\medskip

   170   have sold them (highest price).\hfill\mbox{[1 Mark]}

   171 \end{itemize}

   144 when I prepared the course work...on 6 November; remember stock

   177 when I prepared the course work...namely on 6 November; remember stock

   147 for Goole was on 2004-09-03 with \$49.95513 per share and the

   180 shareprice for Google was on 2004-09-03 with \$49.95513 per share and the

   148 highest on 2016-10-24 with \$813.109985 per share.

   181 highest on 2016-10-24 with \$813.109985 per share.\bigskip

   149 

   182 

   150 

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

   151 

   184 

   152 \subsubsection*{Part 3 (3 Marks)}

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

   153 

   186 approximately 200 Million Dollar from his father. Mr Drump prides

   187 himself to be a brilliant bussiness man because nowadays it is

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

   189 because Mr Drump refuses to make his tax records public).

   190 

   191 The question about Mr Drump's bussiness acumen remains. So let's do a

   192 quick back-of-the-envelope calculation in Scala whether his claim has

   193 any merit. Let's suppose we are given \$100 in 1978 and we follow a

   194 really dump investment strategy, namely:

   195 

   196 \begin{itemize}

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

   198   or some Real Estate stocks.

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

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

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

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

   203   from each.

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

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

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

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

   208   some companies went bust or de-listed).

   209 \item We do this for 38 years until January 2016 and check what would

   210   have become out of our \$100.

   211 \end{itemize}\medskip  

   212 

   213 \noindent

   214 \textbf{Tasks (file drump.scala):}

   215 

   216 \begin{itemize}

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

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

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

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

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

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

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

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

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

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

   227 

   228   \begin{center}\small

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

   230   \end{center}

   231 

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

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

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

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

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

   237   Therefore you need to return a trade price as

   238   \texttt{Option[Double]}.

   239 

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

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

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

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

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

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

   246 

   247 \begin{verbatim}

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

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

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

   251 \end{verbatim}\hfill[1 Mark]

   252  

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

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

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

   256   years. In this case you can calculate

   257 

   258   \[

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

   260   \]

   261 

   262   

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

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

   265   example of Google and Apple for the years 2010 to 2012 gives

   266   the 4 change factors:

   267 

   268 \begin{verbatim}  

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

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

   271 \end{verbatim}

   272 

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

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

   275 

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

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

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

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

   280   unchanged. Otherwise we invest in each existing company an equal

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

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

   283   received in our running example

   284 

   285   \begin{verbatim}

   286   $50 * -0.03573991820699504 + $50 * 0.5399747522663995

   287                                          = $25.211741702970222

   288   \end{verbatim}

   289 

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

   291   converted to a \texttt{Long}.

   292   

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

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

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

   296 \end{itemize}\medskip  

   297 

   298 \noindent

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

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

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

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

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

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

   305 

   306 \noindent

   307 \textbf{Moral:} Reflecting on our assumptions, we are overestimating

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

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

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

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

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

   313 his inheritance, a really dumb investment strategy would have done

   314 equally well, if not much better.