57 \end{lstlisting}%$ |
51 \end{lstlisting}%$ |
58 |
52 |
59 \subsection*{Hints} |
53 \subsection*{Hints} |
60 |
54 |
61 \noindent |
55 \noindent |
62 \textbf{For Preliminary Part:} useful math operators: \texttt{\%} for modulo; useful |
56 \textbf{For Preliminary Part:} useful math operators: \texttt{\%} for modulo, \texttt{\&} for bit-wise and; useful |
63 functions: \mbox{\texttt{(1\,to\,10)}} for ranges, \texttt{.toInt}, |
57 functions: \mbox{\texttt{(1\,to\,10)}} for ranges, \texttt{.toInt}, |
64 \texttt{.toList} for conversions, \texttt{List(...).max} for the |
58 \texttt{.toList} for conversions, you can use \texttt{List(...).max} for the |
65 maximum of a list, \texttt{List(...).indexOf(...)} for the first index of |
59 maximum of a list, \texttt{List(...).indexOf(...)} for the first index of |
66 a value in a list.\bigskip |
60 a value in a list.\bigskip |
67 |
61 |
68 \noindent |
62 |
69 \textbf{For Core Part:} useful string functions: |
|
70 \texttt{.startsWith(...)} for checking whether a string has a given |
|
71 prefix, \texttt{\_ ++ \_} for concatenating two strings; useful option |
|
72 functions: \texttt{.flatten} flattens a list of options such that it |
|
73 filters way all \texttt{None}'s, \texttt{Try(...).getOrElse ...} runs |
|
74 some code that might raise an exception---if yes, then a default value |
|
75 can be given; useful list functions: \texttt{.head} for obtaining the |
|
76 first element in a non-empty list, \texttt{.length} for the length of |
|
77 a list; \texttt{.filter(...)} for filtering out elements in a list; |
|
78 \texttt{.getLines.toList} for obtaining a list of lines from a file; |
|
79 \texttt{.split(",").toList} for splitting strings according to a |
|
80 comma.\bigskip |
|
81 |
|
82 \noindent |
|
83 \textbf{Note!} Fortunately Scala supports operator overloading. But |
|
84 make sure you understand the difference between \texttt{100 / 3} and |
|
85 \texttt{100.0 / 3}! |
|
86 |
63 |
87 \newpage |
64 \newpage |
88 \subsection*{Preliminary Part (3 Marks, file collatz.scala)} |
65 \subsection*{Preliminary Part (3 Marks, file collatz.scala)} |
89 |
66 |
90 This part is about recursion. You are asked to implement a Scala |
67 This part is about recursion. You are asked to implement a Scala program |
91 program that tests examples of the \emph{$3n + 1$-conjecture}, also |
68 that tests examples of the \emph{$3n + 1$-conjecture}, also called |
92 called \emph{Collatz conjecture}. This conjecture can be described as |
69 \emph{Collatz |
93 follows: Start with any positive number $n$ greater than $0$: |
70 conjecture}.\video{https://www.youtube.com./watch?v=LqKpkdRRLZw} This |
|
71 conjecture can be described as follows: Start with any positive number |
|
72 $n$ greater than $0$: |
94 |
73 |
95 \begin{itemize} |
74 \begin{itemize} |
96 \item If $n$ is even, divide it by $2$ to obtain $n / 2$. |
75 \item If $n$ is even, divide it by $2$ to obtain $n / 2$. |
97 \item If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n + |
76 \item If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n + |
98 1$. |
77 1$. |
99 \item Repeat this process and you will always end up with $1$. |
78 \item Repeat this process and you will always end up with $1$. |
100 \end{itemize} |
79 \end{itemize} |
101 |
80 |
102 \noindent |
81 \noindent |
103 For example if you start with, say, $6$ and $9$, you obtain the |
82 For example if you start with, say, $6$ and $9$, you obtain the |
104 two series |
83 two \emph{Collatz series} |
105 |
84 % |
106 \[ |
85 \[ |
107 \begin{array}{@{}l@{\hspace{5mm}}l@{}} |
86 \begin{array}{@{}l@{\hspace{5mm}}l@{}} |
108 6, 3, 10, 5, 16, 8, 4, 2, 1 & \text{(= 8 steps)}\\ |
87 6, 3, 10, 5, 16, 8, 4, 2, 1 & \text{(= 8 steps)}\\ |
109 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 & \text{(= 19 steps)}\\ |
88 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 & \text{(= 19 steps)}\\ |
110 \end{array} |
89 \end{array} |
111 \] |
90 \] |
112 |
91 |
113 \noindent |
92 \noindent |
114 As you can see, the numbers go up and down like a roller-coaster, but |
93 As you can see, the numbers go up and down like a roller-coaster, but |
115 curiously they seem to always terminate in $1$. The conjecture is that |
94 curiously they seem to always terminate in $1$. Nobody knows why. The |
116 this will \emph{always} happen for every number greater than |
95 conjecture is that this will \emph{always} happen for every number |
117 0.\footnote{While it is relatively easy to test this conjecture with |
96 greater than 0.\footnote{While it is relatively easy to test this |
118 particular numbers, it is an interesting open problem to |
97 conjecture with particular numbers, it is an interesting open problem to |
119 \emph{prove} that the conjecture is true for \emph{all} numbers ($> |
98 \emph{prove} that the conjecture is true for \emph{all} numbers ($> 0$). |
120 0$). Paul Erd\"o{}s, a famous mathematician you might have heard |
99 Paul Erd\"o{}s, a famous mathematician you might have heard about, said |
121 about, said about this conjecture: ``Mathematics may not [yet] be ready |
100 about this conjecture: ``Mathematics may not [yet] be ready for such |
122 for such problems.'' and also offered a \$500 cash prize for its |
101 problems.'' and also offered a \$500 cash prize for its solution. |
123 solution. Jeffrey Lagarias, another mathematician, claimed that |
102 Jeffrey Lagarias, another mathematician, claimed that based only on |
124 based only on known information about this problem, ``this is an |
103 known information about this problem, ``this is an extraordinarily |
125 extraordinarily difficult problem, completely out of reach of |
104 difficult problem, completely out of reach of present day mathematics.'' |
126 present day mathematics.'' There is also a |
105 There is also a \href{https://xkcd.com/710/}{xkcd} cartoon about this |
127 \href{https://xkcd.com/710/}{xkcd} cartoon about this conjecture |
106 conjecture\here{https://xkcd.com/710/}). If you are able to solve this |
128 (click \href{https://xkcd.com/710/}{here}). If you are able to solve |
107 conjecture, you will definitely get famous.}\bigskip |
129 this conjecture, you will definitely get famous.}\bigskip |
|
130 |
108 |
131 \noindent |
109 \noindent |
132 \textbf{Tasks} |
110 \textbf{Tasks} |
133 |
111 |
134 \begin{itemize} |
112 \begin{itemize} |
135 \item[(1)] You are asked to implement a recursive function that |
113 \item[(1)] You are asked to implement a recursive function that |
136 calculates the number of steps needed until a series ends |
114 calculates the number of steps needed until a series ends |
137 with $1$. In case of starting with $6$, it takes $8$ steps and in |
115 with $1$. In case of starting with $6$, it takes $8$ steps and in |
138 case of starting with $9$, it takes $19$ (see above). In order to |
116 case of starting with $9$, it takes $19$ (see above). We assume it |
|
117 takes $0$ steps, if we start with $1$. In order to |
139 try out this function with large numbers, you should use |
118 try out this function with large numbers, you should use |
140 \texttt{Long} as argument type, instead of \texttt{Int}. You can |
119 \texttt{Long} as argument type, instead of \texttt{Int}. You can |
141 assume this function will be called with numbers between $1$ and |
120 assume this function will be called with numbers between $1$ and |
142 $1$ Million. \hfill[2 Marks] |
121 $1$ Million. \hfill[1 Mark] |
143 |
122 |
144 \item[(2)] Write a second function that takes an upper bound as |
123 \item[(2)] Write a second function that takes an upper bound as |
145 an argument and calculates the steps for all numbers in the range from |
124 an argument and calculates the steps for all numbers in the range from |
146 1 up to this bound (the bound including). It returns the maximum number of |
125 1 up to this bound (the bound including). It returns the maximum number of |
147 steps and the corresponding number that needs that many steps. More |
126 steps and the corresponding number that needs that many steps. More |
148 precisely it returns a pair where the first component is the number |
127 precisely it returns a pair where the first component is the number |
149 of steps and the second is the corresponding number. \hfill\mbox{[1 |
128 of steps and the second is the corresponding number. \hfill\mbox{[1 |
150 Mark]} |
129 Mark]} |
|
130 |
|
131 \item[(3)] Write a function that calculates \emph{hard |
|
132 numbers} \here{https://medium.com/cantors-paradise/the-collatz-conjecture-some-shocking-results-from-180-000-iterations-7fea130d0377} |
|
133 in the Collatz series---these are the last odd numbers just before a |
|
134 power of two is reached. For this, implement an |
|
135 \textit{is-power-of-two} function which tests whether a number is a |
|
136 power of two. The easiest way to implement this is by using the |
|
137 bit-operator $\&$. For a power of two, say $n$ with $n > 0$, it |
|
138 holds that $n \;\&\; (n - 1)$ is equal to zero. I let you think why |
|
139 this is the case. The function \textit{is-hard} calculates whether |
|
140 $3n + 1$ is a power of two. Finally the \textit{last-odd} function |
|
141 calculates the last odd number before a power of 2 in the Collatz |
|
142 series. This means for example when starting with 6 and also with 9, |
|
143 we receive 5 as the last odd number. Surprisingly a lot of numbers |
|
144 have 5 as last-odd number. But for example for 113 we obtain 85, |
|
145 because of the series |
|
146 % |
|
147 \[113, 340, 170, \,\fbox{85}\,, 256, 128, 64, 32, 16, 8, 4, 2, 1\] |
|
148 |
|
149 The \textit{last-odd} function will only be called with numbers that are not |
|
150 powers of 2 themselves. |
151 \end{itemize} |
151 \end{itemize} |
152 |
152 |
153 \noindent |
153 \noindent |
154 \textbf{Test Data:} Some test ranges are: |
154 \textbf{Test Data:} Some test ranges are: |
155 |
155 |
166 |
166 |
167 |
167 |
168 |
168 |
169 |
169 |
170 |
170 |
171 \subsection*{Core Part (7 Marks, file drumb.scala)} |
|
172 |
|
173 A purely fictional character named Mr T.~Drumb inherited in 1978 |
|
174 approximately 200 Million Dollar from his father. Mr Drumb prides |
|
175 himself to be a brilliant business man because nowadays it is |
|
176 estimated he is 3 Billion Dollar worth (one is not sure, of course, |
|
177 because Mr Drumb refuses to make his tax records public). |
|
178 |
|
179 Since the question about Mr Drumb's business acumen remains open, |
|
180 let's do a quick back-of-the-envelope calculation in Scala whether his |
|
181 claim has any merit. Let's suppose we are given \$100 in 1978 and we |
|
182 follow a really dumb investment strategy, namely: |
|
183 |
|
184 \begin{itemize} |
|
185 \item We blindly choose a portfolio of stocks, say some Blue-Chip stocks |
|
186 or some Real Estate stocks. |
|
187 \item If some of the stocks in our portfolio are traded in January of |
|
188 a year, we invest our money in equal amounts in each of these |
|
189 stocks. For example if we have \$100 and there are four stocks that |
|
190 are traded in our portfolio, we buy \$25 worth of stocks |
|
191 from each. (Be careful to also test cases where you trade with 3 stocks.) |
|
192 \item Next year in January, we look at how our stocks did, liquidate |
|
193 everything, and re-invest our (hopefully) increased money in again |
|
194 the stocks from our portfolio (there might be more stocks available, |
|
195 if companies from our portfolio got listed in that year, or less if |
|
196 some companies went bust or were de-listed). |
|
197 \item We do this for 41 years until January 2019 and check what would |
|
198 have become out of our \$100. |
|
199 \end{itemize} |
|
200 |
|
201 \noindent |
|
202 Until Yahoo was bought by Altaba a few years ago, historical stock market |
|
203 data for such back-of-the-envelope calculations was freely available |
|
204 online. Unfortunately nowadays this kind of data is more difficult to |
|
205 obtain, unless you are prepared to pay extortionate prices or be |
|
206 severely rate-limited. Therefore this part comes with a number |
|
207 of files containing CSV-lists with the historical stock prices for the |
|
208 companies in our portfolios. Use these files for the following |
|
209 tasks.\bigskip |
|
210 |
|
211 \newpage |
|
212 \noindent |
|
213 \textbf{Tasks} |
|
214 |
|
215 \begin{itemize} |
|
216 \item[(1)] Write a function \texttt{get\_january\_data} that takes a |
|
217 stock symbol and a year as arguments. The function reads the |
|
218 corresponding CSV-file and returns the list of strings that start |
|
219 with the given year (each line in the CSV-list is of the form |
|
220 \texttt{someyear-01-someday,someprice}).\hfill[1 Mark] |
|
221 |
|
222 \item[(2)] Write a function \texttt{get\_first\_price} that takes |
|
223 again a stock symbol and a year as arguments. It should return the |
|
224 first January price for the stock symbol in the given year. For this |
|
225 it uses the list of strings generated by |
|
226 \texttt{get\_january\_data}. A problem is that normally a stock |
|
227 exchange is not open on 1st of January, but depending on the day of |
|
228 the week on a later day (maybe 3rd or 4th). The easiest way to solve |
|
229 this problem is to obtain the whole January data for a stock symbol |
|
230 and then select the earliest, or first, entry in this list. The |
|
231 stock price of this entry should be converted into a double. Such a |
|
232 price might not exist, in case the company does not exist in the given |
|
233 year. For example, if you query for Google in January of 1980, then |
|
234 clearly Google did not exist yet. Therefore you are asked to |
|
235 return a trade price with type \texttt{Option[Double]}\ldots\texttt{None} |
|
236 will be the value for when no price exists; \texttt{Some} if there is a |
|
237 price.\hfill[1 Mark] |
|
238 |
|
239 \item[(3)] Write a function \texttt{get\_prices} that takes a |
|
240 portfolio (a list of stock symbols), a years range and gets all the |
|
241 first trading prices for each year in the range. You should organise |
|
242 this as a list of lists of \texttt{Option[Double]}'s. The inner |
|
243 lists are for all stock symbols from the portfolio and the outer |
|
244 list for the years. For example for Google and Apple in years 2010 |
|
245 (first line), 2011 (second line) and 2012 (third line) you obtain: |
|
246 |
|
247 \begin{verbatim} |
|
248 List(List(Some(312.204773), Some(26.782711)), |
|
249 List(Some(301.0466), Some(41.244694)), |
|
250 List(Some(331.462585), Some(51.464207)))) |
|
251 \end{verbatim}\hfill[1 Mark] |
|
252 |
|
253 |
|
254 %\end{itemize} |
|
255 |
|
256 %\subsection*{Advanced Part 3 (4 Marks, continue in file drumb.scala)} |
|
257 % |
|
258 %\noindent |
|
259 %\textbf{Tasks} |
|
260 |
|
261 %\begin{itemize} |
|
262 |
|
263 \item[(4)] Write a function that calculates the \emph{change factor} (delta) |
|
264 for how a stock price has changed from one year to the next. This is |
|
265 only well-defined, if the corresponding company has been traded in both |
|
266 years. In this case you can calculate |
|
267 |
|
268 \[ |
|
269 \frac{price_{new} - price_{old}}{price_{old}} |
|
270 \] |
|
271 |
|
272 If the change factor is defined, you should return it |
|
273 as \texttt{Some(change\_factor)}; if not, you should return |
|
274 \texttt{None}.\mbox{}\hfill\mbox{[1 Mark]} |
|
275 |
|
276 \item[(5)] Write a function that calculates all change factors |
|
277 (deltas) for the prices we obtained in Task (2). For the running |
|
278 example of Google and Apple for the years 2010 to 2012 you should |
|
279 obtain 4 change factors: |
|
280 |
|
281 \begin{verbatim} |
|
282 List(List(Some(-0.03573991804411003), Some(0.539974575389325)), |
|
283 List(Some(0.10103414222249969), Some(0.24777764141006836))) |
|
284 \end{verbatim} |
|
285 |
|
286 That means Google did a bit badly in 2010, while Apple did very well. |
|
287 Both did OK in 2011. Make sure you handle the cases where a company is |
|
288 not listed in a year. In such cases the change factor should be \texttt{None} |
|
289 (recall Task~(4)). |
|
290 \mbox{}\hfill\mbox{[1 Mark]} |
|
291 |
|
292 \item[(6)] Write a function that calculates the ``yield'', or |
|
293 balance, for one year for our portfolio. This function takes the |
|
294 change factors, the starting balance and the year as arguments. If |
|
295 no company from our portfolio existed in that year, the balance is |
|
296 unchanged. Otherwise we invest in each existing company an equal |
|
297 amount of our balance. Using the change factors computed under Task |
|
298 (2), calculate the new balance. Say we had \$100 in 2010, we would have |
|
299 received in our running example involving Google and Apple: |
|
300 |
|
301 \begin{verbatim} |
|
302 $50 * -0.03573991804411003 + $50 * 0.539974575389325 |
|
303 = $25.21173286726075 |
|
304 \end{verbatim} |
|
305 |
|
306 as profit for that year, and our new balance for 2011 is \$125 when |
|
307 converted to a \texttt{Long}.\mbox{}\hfill\mbox{[1 Mark]} |
|
308 |
|
309 \item[(7)] Write a function that calculates the overall balance |
|
310 for a range of years where each year the yearly profit is compounded to |
|
311 the new balances and then re-invested into our portfolio. |
|
312 For this use the function and results generated under (6).\\ |
|
313 \mbox{}\hfill\mbox{[1 Mark]} |
|
314 \end{itemize}\medskip |
|
315 |
|
316 |
|
317 |
|
318 \noindent |
|
319 \textbf{Test Data:} File \texttt{drumb.scala} contains two portfolios |
|
320 collected from the S\&P 500, one for blue-chip companies, including |
|
321 Facebook, Amazon and Baidu; and another for listed real-estate |
|
322 companies, whose names I have never heard of. Following the dumb |
|
323 investment strategy from 1978 until 2019 would have turned a starting |
|
324 balance of \$100 into roughly \$39,162 for real estate and a whopping |
|
325 \$462,199 for blue chips. Note when comparing these results with your |
|
326 own calculations: there might be some small rounding errors, which |
|
327 when compounded lead to moderately different values.\bigskip |
|
328 |
|
329 |
|
330 \noindent |
|
331 \textbf{Moral:} Reflecting on our assumptions, we are over-estimating |
|
332 our yield in many ways: first, who can know in 1978 about what will |
|
333 turn out to be a blue chip company. Also, since the portfolios are |
|
334 chosen from the current S\&P 500, they do not include the myriad |
|
335 of companies that went bust or were de-listed over the years. |
|
336 So where does this leave our fictional character Mr T.~Drumb? Well, given |
|
337 his inheritance, a really dumb investment strategy would have done |
|
338 equally well, if not much better.\medskip |
|
339 |
171 |
340 \end{document} |
172 \end{document} |
341 |
173 |
342 |
174 |
343 %%%%%%% Historical Stuff |
175 %%%%%%% Historical Stuff |