Merge branch 'master' of git.njae.me.uk:cas-master-teacher-training

diff --combined algorithms.html
index 57fdbae668b0cc1a78a09b1ce7c5e43ff7b6ce60,b7a7b61c7aea6af1128c18b6b0a91e96bf75b04a..a42dee94c1742806850ab981db20f2124d1035d2
--- 1/algorithms.html
--- 2/algorithms.html
+++ b/algorithms.html
@@@ -280,14 -280,6 +280,14 @@@ Given a wordlist and a phrase, find ano
  
  ---
  
 +# Sorting with cards
 +
 +Classroom activity?
 +
 +Don't forget bogosort!
 +
 +---
 +
  # Dealing with complex problems: some terms to know
  
  (M269 Unit 5)
@@@ -306,82 -298,16 +306,82 @@@
  
  Build a soluion bottom-up from subparts
  
 -## Heuristics
 +---
 +
 +# Heuristics
  
  * Posh word for "guess"
  * Greedy algorithms
  * Backtracking
 +
  ---
  
 -# Sorting with cards
 +# Making change
  
 -Classroom activity?
 +Given
 +
 +* some money and a set of coin denominations,
 +
 +find
 +
 +* the smallest number of coins to make that total.
 +
 +## Approach 1: greedy
 +
 +```
 +Repeat:
 +   Pick the biggest coin you can
 +```
 +
 +Only works in some cases
 +
 +(What the best way to make 7p if you have 1p, 3p, 4p, 5p coins?)
 +
 +---
 +
 +# Making change 2: exhaustive search
 +
 +.float-right[![Ticket to Ride](make-change.dot.png)]
 +
 +Make a tree of change-making.
 +
 +Pick the optimal.
 +
 +---
 +
 +# Making change 3: dynamic programming
 +
 +Bottom-up approach
 +
 +Initial:
 +
 +0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 +-|-|-|-|-|-|-|-|-|-|-|-
 +(0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ...
 +
 +--
 +----
 +0* | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 +-|-|-|-|-|-|-|-|-|-|-|-
 +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ...
 +
 +--
 +----
 +0 | 1* | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 +-|-|-|-|-|-|-|-|-|-|-|-
 +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ...
 +
 +--
 +----
 +0 | 1 | 2* | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 +-|-|-|-|-|-|-|-|-|-|-|-
 +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ...
 +
 +--
 +----
 +0 | 1 | 2 | 3* | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 +-|-|-|-|-|-|-|-|-|-|-|-
 +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ...
  
  ---
  
@@@ -389,21 -315,19 +389,21 @@@
  
  ## Travelling Salesman Problem
  
 -Online: http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
 +.float-right[![Ticket to Ride](ticket-to-ride-small.jpg)]
 +
 +Online: 
 +
 +http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
  
  * But many implementations are Java applets, now a problem with security settings
  
  Try Android/iOS apps?
  
 -## Change-finding problem
 -
 -Same as the Knapsack problem: M269 Unit 5 Section 3.2, especially Activity 5.9
 +## Ticket to Ride boardgame
  
 -Dynamic programming to find solution
 +Graph algorithms
  
 -## Ticket to Ride boardgame
 +* Find shortest path
  
  ---
  
@@@ -440,6 -364,11 +440,11 @@@ A *universal* Turing machine can take t
  
  *This* shows that computing as we know it is possible.
  
+ * Programming
+ * Abstraction
+ * Virtual machines
+ * ...
+