# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1478456927 0
# Node ID 417869f65585d08b9cc3c2282f2a5d6f2ed70b00
# Parent  e7eeeb5b41dc14821fe93c1201103ff4e4e8807a
updated

diff -r e7eeeb5b41dc -r 417869f65585 cws/cw01.pdf
Binary file cws/cw01.pdf has changed
diff -r e7eeeb5b41dc -r 417869f65585 cws/cw01.tex
--- a/cws/cw01.tex	Sat Nov 05 18:15:38 2016 +0000
+++ b/cws/cw01.tex	Sun Nov 06 18:28:47 2016 +0000
@@ -1,15 +1,15 @@
 \documentclass{article}
-\usepackage{style}
+\usepackage{../style}
 %%\usepackage{../langs}
 
 \begin{document}
 
 \section*{Coursework 6 (Scala)}
 
-This coursework is about Scala and is worth 10\%. The first part is
-due on 16 November at 11:00, and the second part on 23 November. You
-are asked to implement a three programs about list manipulations and
-recursion.
+This coursework is about Scala and is worth 10\%. The first and second
+part is due on 16 November at 11:00, and the second part on 23
+November at 11:00. You are asked to implement three programs about
+list processing and recursion.
 
 \subsubsection*{Disclaimer}
 
@@ -21,9 +21,135 @@
 
 \subsubsection*{Part 1 (3 Marks)}
 
-\subsubsection*{Part 2 (3 Marks)}
+This part is about recursion. You are asked to implement a Scala
+program that tests examples of the \emph{$3n + 1$-conjecture}. This
+conjecture can be described as follows: Start with any positive number
+$n$ greater than $0$. If $n$ is even, divide it by $2$ to obtain $n /
+2$. If $n$ is odd, multiply it by $3$ and add $1$ to obtain $3n +
+1$. Repeat this process and you will always end up with $1$.  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$.  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 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 \$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.\medskip
+
+\noindent
+\textbf{Tasks:} (1) You are asked to implement a recursive function that
+calculates the number of steps needed number 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 $10$ million.
+
+(2) Then write a second function that takes an upper bound as argument
+and calculates the steps for all numbers in the range from 1 upto this
+bound, and returns the maximum of steps needed by a number in that
+range. This function should produce for ranges
+
+\begin{itemize}
+\item $1 - 10$ where $9$ takes 20 steps
+\item $1 - 100$ where $97$ takes 119 steps,
+\item $1 - 1,000$ where $871$ takes 179 steps,
+\item $1 - 10,000$ where $6,171$ takes 262 steps,
+\item $1 - 100,000$ where $77,031$ takes 351 steps,
+\item $1 - 1$ million where $837,799$ takes 525 steps, and
+\item $1 - 10$ million where $8,400,511$ takes 686 steps
+\end{itemize}  
+
+
+\subsubsection*{Part 2 (4 Marks)}
+
+This part is about list processing---it's a variant of
+Buy-low-sell-high in Scala. (1) Given a list of prices for a commodity,
+for example
+
+\[
+\texttt{List(28.0, 18.0, 20.0, 26.0, 24.0)}
+\]
 
-\subsubsection*{Part 3 (4 Marks)}
+\noindent
+you need to write a function that returns a pair for when to buy and
+when to sell this commodity. In the example above it should return
+$\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{Float}s.
+
+(2) Write a function that requests a comma-separated value list from a
+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 comma-separated value list of the daily stock
+prices since Google was floated. You can also try this with other
+strock 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 comma-separated value list
+(representing one days 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.
+
+(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 float. So the result of this function is a list of pairs where the
+first components are strings (the dates) and the second are floats
+(the adjusted close prices).
+
+(4) Write a function that takes a stock market symbol as argument (you
+can assume it is a valid one, like GOOG, AAPL, MSFT, IBM, FB, YHOO,
+AMZN, BIDU). The function calculates the dates when you should have
+bought Google shares (lowest price) and when you should have sold them
+(highest price).\medskip
+
+\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...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
+for Goole was on 2004-09-03 with \$49.95513 per share and the
+highest on 2016-10-24 with \$813.109985 per share.
+
+
+
+\subsubsection*{Part 3 (3 Marks)}
 
 \end{document}
 
diff -r e7eeeb5b41dc -r 417869f65585 progs/collatz.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/collatz.scala	Sun Nov 06 18:28:47 2016 +0000
@@ -0,0 +1,29 @@
+// Part 1
+
+
+//(1)
+def collatz(n: Long): List[Long] =
+  if (n == 1) List(1) else
+    if (n % 2 == 0) (n::collatz(n / 2)) else 
+      (n::collatz(3 * n + 1))
+
+// an alternative that calculates the steps directly
+def collatz1(n: Long): Int =
+  if (n == 1) 1 else
+    if (n % 2 == 0) (1 + collatz1(n / 2)) else 
+      (1 + collatz1(3 * n + 1))
+
+
+//(2)
+def collatz_max(bnd: Int): Int = {
+  (for (i <- 1 to bnd) yield collatz(i).length).max
+}
+
+
+val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000)
+
+for (bnd <- bnds) {
+  val max = collatz_max(bnd)
+  println(s"In the range of 1 - ${bnd} the maximum steps are ${max}")
+}
+
diff -r e7eeeb5b41dc -r 417869f65585 progs/live.scala
--- a/progs/live.scala	Sat Nov 05 18:15:38 2016 +0000
+++ b/progs/live.scala	Sun Nov 06 18:28:47 2016 +0000
@@ -1,12 +1,12 @@
 import scala.annotation.tailrec   
 
 
-def collatz(n: Int): List[Int] =
+def collatz(n: Long): List[Long] =
   if (n == 1) List(1) else
     if (n % 2 == 0) (n::collatz(n / 2)) else 
       (n::collatz(3 * n + 1))
 
-def collatz1(n: Int): Int =
+def collatz1(n: Long): Int =
   if (n == 1) 1 else
     if (n % 2 == 0) (1 + collatz1(n / 2)) else 
       (1 + collatz1(3 * n + 1))
@@ -17,24 +17,18 @@
     if (n % 2 == 0) collatz2(n / 2, acc + 1) else 
       collatz2(3 * n + 1, acc + 1)
 
-@tailrec
-def collatz3(n: BigInt, acc: Int): Int =
-  if (n == 1) acc else
-    if (n % 2 == 0) collatz3(n / 2, acc + 1) else 
-      collatz3(3 * n + 1, acc + 1)
-
 collatz(1)
 collatz(2)
 collatz(3)
 collatz(4)
 collatz(5)
-collatz(6)
+collatz(6).length
 collatz(7)
 collatz(8)
-collatz(9)
+collatz(9).length
 collatz(100000)
-println((for (i <- 1 to 100000) yield collatz(i).length).max)
-println((for (i <- 1 to 100000) yield collatz1(i)).max)
-println((for (i <- 1 to 1000000) yield collatz2(i, 1)).max)
+println((for (i <- 1 to 10000000) yield collatz(i).length).max)
+println((for (i <- 1 to 10000000) yield collatz1(i)).max)
+println((for (i <- 1 to 10000000) yield collatz2(i, 1)).max)
 println((for (i <- (1 to 10000000).par) yield collatz2(i, 1)).max)
-println((for (i <- (1 to 100000000).par) yield collatz3(i, 1)).max)
+
diff -r e7eeeb5b41dc -r 417869f65585 progs/trade.scala
--- a/progs/trade.scala	Sat Nov 05 18:15:38 2016 +0000
+++ b/progs/trade.scala	Sun Nov 06 18:28:47 2016 +0000
@@ -1,7 +1,7 @@
-
+// Part 2
 
-val trades = List(28.0, 18.0, 20.0, 26.0, 24.0)
-
+// (1) the function that calculuates the indices
+// for when to buy the commodity and when to sell
 def trade_times(xs: List[Double]): (Int, Int) = {
   val low = xs.min
   val low_index = xs.indexOf(low)
@@ -12,46 +12,47 @@
 }
 
 
-trade_times(trades)
+val prices = List(28.0, 18.0, 20.0, 26.0, 24.0)
 
-assert(trade_times(List(10.0, 8.0, 7.0, 6.0)) == (3, 3), "the first test fails")
-
+trade_times(prices)
+assert(trade_times(prices) == (1, 3), "the first test fails")
 
 
 import io.Source
 import scala.util._
 
+// (2) the function that queries the Yahoo financial data
+// servive and returns a comma-separated-value list
 def get_page(url: String): List[String] = {
   Try(Source.fromURL(url)("ISO-8859-1").getLines.toList).
     getOrElse { println(s"  Problem with: $url"); List() }
 }
 
+// (3) the function that processes the comma-separated-value list
+// extracting the dates and anjusted close prices
 def process_page(url: String): List[(String, Double)] = {
   get_page(url).drop(1).map(_.split(",").toList).map((xs) => (xs(0), xs(6).toDouble))
 }
 
-def query_comp(name: String): (Int, Int) = {
-  val list = process_page("""http://ichart.yahoo.com/table.csv?s=""" + name)
-  trade_times(list.reverse.map(_._2))
+// (4) the function that generates the query for a stock
+// market symbol and returns the dates for when to buy and
+// sell
+def query_comp(name: String): (String, String) = {
+  val list = process_page("""http://ichart.yahoo.com/table.csv?s=""" + name).reverse
+  val (tbuy, tsell) = trade_times(list.map(_._2))
+  (list(tbuy)._1, list(tsell)._1)
 }
 
+//query_comp("GOOG")
+
 
 val indices = List("GOOG", "AAPL", "MSFT", "IBM", "FB", "YHOO", "AMZN", "BIDU")
 
-indices.map(query_comp(_))
-
-val appl_page = get_page("""http://ichart.yahoo.com/table.csv?s=GOOG""")
-val goog_page = get_page("""http://ichart.yahoo.com/table.csv?s=GOOG""")
-goog_page.length
+for (name <- indices) {
+  val times = query_comp(name)
+  println(s"Buy ${name} on ${times._1} and sell on ${times._2}")
+}
 
-val pairs = goog_page.drop(1).map(_.split(",").toList).map((xs:List[String]) => (xs(0), xs(6).toDouble))
-
-pairs.map(_._2)
-
-trade_times(pairs.reverse.map(_._2))
-
-pairs(3067)
-pairs(11)
 
 
 /*