--- a/cws/cw01.tex Thu Apr 23 14:49:54 2020 +0100
+++ b/cws/cw01.tex Wed Aug 12 00:56:20 2020 +0100
@@ -4,23 +4,18 @@
\usepackage{disclaimer}
\usepackage{../langs}
+
+
\begin{document}
-\section*{Part 6 (Scala)}
+\section*{Preliminary Part 6 (Scala)}
\mbox{}\hfill\textit{``The most effective debugging tool is still careful thought,}\\
\mbox{}\hfill\textit{coupled with judiciously placed print statements.''}\smallskip\\
-\mbox{}\hfill\textit{ --- Brian W. Kernighan, in Unix for Beginners (1979)}\medskip\bigskip
+\mbox{}\hfill\textit{ --- Brian W. Kernighan, in Unix for Beginners (1979)}\bigskip
-\noindent
-This part is about Scala. You are asked to implement two programs
-about list processing and recursion. The preliminary part (3\%) is due
-on \cwSIX{} at 4pm, and the core part on \cwSIXa{} at 4pm. The core
-part is more advanced and might include material you have not yet seen
-in the first lecture.\bigskip
-
-\IMPORTANT{}
+\IMPORTANT{This part is about Scala. It is due on \cwSIX{} at 4pm and worth 3\%.}
\noindent
Also note that the running time of each part will be restricted to a
@@ -37,15 +32,14 @@
\noindent
In addition, the Scala coursework comes with a reference implementation
-in form of \texttt{jar}-files. This allows you to run any test cases
-on your own computer. For example you can call Scala on the command
-line with the option \texttt{-cp collatz.jar} and then query any
-function from the template file. Say you want to find out what
-the functions \texttt{collatz} and \texttt{collatz\_max}
-produce: for this you just need to prefix them with the object name
-\texttt{CW6a} (and \texttt{CW6b} respectively for \texttt{drumb.jar}).
-If you want to find out what these functions produce for the argument
-\texttt{6}, you would type something like:
+in form of \texttt{jar}-files. This allows you to run any test cases on
+your own computer. For example you can call Scala on the command line
+with the option \texttt{-cp collatz.jar} and then query any function
+from the template file. Say you want to find out what the functions
+\texttt{collatz} and \texttt{collatz\_max} produce: for this you just
+need to prefix them with the object name \texttt{CW6a}. If you want to
+find out what these functions produce for the argument \texttt{6}, you
+would type something like:
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala -cp collatz.jar
@@ -59,38 +53,23 @@
\subsection*{Hints}
\noindent
-\textbf{For Preliminary Part:} useful math operators: \texttt{\%} for modulo; useful
+\textbf{For Preliminary Part:} useful math operators: \texttt{\%} for modulo, \texttt{\&} for bit-wise and; useful
functions: \mbox{\texttt{(1\,to\,10)}} for ranges, \texttt{.toInt},
-\texttt{.toList} for conversions, \texttt{List(...).max} for the
+\texttt{.toList} for conversions, you can use \texttt{List(...).max} for the
maximum of a list, \texttt{List(...).indexOf(...)} for the first index of
a value in a list.\bigskip
-\noindent
-\textbf{For Core Part:} useful string functions:
-\texttt{.startsWith(...)} for checking whether a string has a given
-prefix, \texttt{\_ ++ \_} for concatenating two strings; useful option
-functions: \texttt{.flatten} flattens a list of options such that it
-filters way all \texttt{None}'s, \texttt{Try(...).getOrElse ...} runs
-some code that might raise an exception---if yes, then a default value
-can be given; useful list functions: \texttt{.head} for obtaining the
-first element in a non-empty list, \texttt{.length} for the length of
-a list; \texttt{.filter(...)} for filtering out elements in a list;
-\texttt{.getLines.toList} for obtaining a list of lines from a file;
-\texttt{.split(",").toList} for splitting strings according to a
-comma.\bigskip
-\noindent
-\textbf{Note!} Fortunately Scala supports operator overloading. But
-make sure you understand the difference between \texttt{100 / 3} and
-\texttt{100.0 / 3}!
\newpage
\subsection*{Preliminary Part (3 Marks, file collatz.scala)}
-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$:
+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}.\video{https://www.youtube.com./watch?v=LqKpkdRRLZw} 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$.
@@ -101,8 +80,8 @@
\noindent
For example if you start with, say, $6$ and $9$, you obtain the
-two series
-
+two \emph{Collatz series}
+%
\[
\begin{array}{@{}l@{\hspace{5mm}}l@{}}
6, 3, 10, 5, 16, 8, 4, 2, 1 & \text{(= 8 steps)}\\
@@ -112,21 +91,20 @@
\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 heard
- about, said about this conjecture: ``Mathematics may not [yet] 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
+curiously they seem to always terminate in $1$. Nobody knows why. 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 heard about, said
+about this conjecture: ``Mathematics may not [yet] 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\here{https://xkcd.com/710/}). If you are able to solve this
+conjecture, you will definitely get famous.}\bigskip
\noindent
\textbf{Tasks}
@@ -135,11 +113,12 @@
\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 $8$ steps and in
- case of starting with $9$, it takes $19$ (see above). In order to
+ case of starting with $9$, it takes $19$ (see above). We assume it
+ takes $0$ steps, if we start with $1$. 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]
+ $1$ Million. \hfill[1 Mark]
\item[(2)] Write a second function that takes an upper bound as
an argument and calculates the steps for all numbers in the range from
@@ -148,6 +127,27 @@
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]}
+
+\item[(3)] Write a function that calculates \emph{hard
+ numbers} \here{https://medium.com/cantors-paradise/the-collatz-conjecture-some-shocking-results-from-180-000-iterations-7fea130d0377}
+ in the Collatz series---these are the last odd numbers just before a
+ power of two is reached. For this, implement an
+ \textit{is-power-of-two} function which tests whether a number is a
+ power of two. The easiest way to implement this is by using the
+ bit-operator $\&$. For a power of two, say $n$ with $n > 0$, it
+ holds that $n \;\&\; (n - 1)$ is equal to zero. I let you think why
+ this is the case. The function \textit{is-hard} calculates whether
+ $3n + 1$ is a power of two. Finally the \textit{last-odd} function
+ calculates the last odd number before a power of 2 in the Collatz
+ series. This means for example when starting with 6 and also with 9,
+ we receive 5 as the last odd number. Surprisingly a lot of numbers
+ have 5 as last-odd number. But for example for 113 we obtain 85,
+ because of the series
+ %
+ \[113, 340, 170, \,\fbox{85}\,, 256, 128, 64, 32, 16, 8, 4, 2, 1\]
+
+ The \textit{last-odd} function will only be called with numbers that are not
+ powers of 2 themselves.
\end{itemize}
\noindent
@@ -168,174 +168,6 @@
-\subsection*{Core Part (7 Marks, file drumb.scala)}
-
-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 dumb 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. (Be careful to also test cases where you trade with 3 stocks.)
-\item Next year in January, we look at 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 were de-listed).
-\item We do this for 41 years until January 2019 and check what would
- have become out of our \$100.
-\end{itemize}
-
-\noindent
-Until Yahoo was bought by Altaba a few years ago, historical stock market
-data for such back-of-the-envelope calculations was freely available
-online. Unfortunately nowadays this kind of data is more difficult to
-obtain, unless you are prepared to pay extortionate prices or be
-severely rate-limited. Therefore this part comes with a number
-of files containing CSV-lists with the historical stock prices for the
-companies in our portfolios. Use these files for the following
-tasks.\bigskip
-
-\newpage
-\noindent
-\textbf{Tasks}
-
-\begin{itemize}
-\item[(1)] Write a function \texttt{get\_january\_data} that takes a
- stock symbol and a year as arguments. The function reads the
- corresponding CSV-file and returns the list of strings that start
- with the given year (each line in the CSV-list is of the form
- \texttt{someyear-01-someday,someprice}).\hfill[1 Mark]
-
-\item[(2)] Write a function \texttt{get\_first\_price} that takes
- again a stock symbol and a year as arguments. It should return the
- first January price for the stock symbol in the given year. For this
- it uses the list of strings generated by
- \texttt{get\_january\_data}. 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
- and then select the earliest, or first, entry in this list. The
- stock price of this entry should be converted into a double. Such a
- price might not exist, in case the company does not exist in the given
- year. For example, if you query for Google in January of 1980, then
- clearly Google did not exist yet. Therefore you are asked to
- return a trade price with type \texttt{Option[Double]}\ldots\texttt{None}
- will be the value for when no price exists; \texttt{Some} if there is a
- price.\hfill[1 Mark]
-
-\item[(3)] Write a function \texttt{get\_prices} that takes a
- portfolio (a list of stock symbols), a years range and gets all the
- first trading prices for each year in the range. 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(312.204773), Some(26.782711)),
- List(Some(301.0466), Some(41.244694)),
- List(Some(331.462585), Some(51.464207))))
-\end{verbatim}\hfill[1 Mark]
-
-
-%\end{itemize}
-
-%\subsection*{Advanced Part 3 (4 Marks, continue in file drumb.scala)}
-%
-%\noindent
-%\textbf{Tasks}
-
-%\begin{itemize}
-
-\item[(4)] 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}}
- \]
-
- If the change factor is defined, you should return it
- as \texttt{Some(change\_factor)}; if not, you should return
- \texttt{None}.\mbox{}\hfill\mbox{[1 Mark]}
-
-\item[(5)] Write a function that calculates all change factors
- (deltas) for the prices we obtained in Task (2). 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.03573991804411003), Some(0.539974575389325)),
- List(Some(0.10103414222249969), Some(0.24777764141006836)))
-\end{verbatim}
-
- That means Google did a bit badly in 2010, while Apple did very well.
- Both did OK in 2011. Make sure you handle the cases where a company is
- not listed in a year. In such cases the change factor should be \texttt{None}
- (recall Task~(4)).
- \mbox{}\hfill\mbox{[1 Mark]}
-
-\item[(6)] 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 involving Google and Apple:
-
- \begin{verbatim}
- $50 * -0.03573991804411003 + $50 * 0.539974575389325
- = $25.21173286726075
- \end{verbatim}
-
- as profit for that year, and our new balance for 2011 is \$125 when
- converted to a \texttt{Long}.\mbox{}\hfill\mbox{[1 Mark]}
-
-\item[(7)] 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.
- For this use the function and results generated under (6).\\
- \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 2019 would have turned a starting
-balance of \$100 into roughly \$39,162 for real estate and a whopping
-\$462,199 for blue chips. Note when comparing these results with your
-own calculations: there might be some small rounding errors, which
-when compounded lead to moderately different values.\bigskip
-
-
-\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.\medskip
\end{document}