X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;ds=inline;f=algorithms.html;h=bbe92f16b0480599da0df4e0230dec35e79a6ad0;hb=b3934d614b144fccdb085ebae9158f91b475b63d;hp=f5dbe1fe9cfe75b183bc357d5cc3ae45d1e91c4b;hpb=864a130f1e84240718ed43f5898c19e1e4c1fd31;p=cas-master-teacher-training.git
diff --git a/algorithms.html b/algorithms.html
index f5dbe1f..bbe92f1 100644
--- a/algorithms.html
+++ b/algorithms.html
@@ -54,6 +54,8 @@
## What's all the fuss about?
+![Alan Turing](alan-turing.jpg)
+
---
layout: true
@@ -71,6 +73,7 @@ Back when computers were human...
* As much notepaper as you wanted
* Input â output
+.float-right[![right-aligned Growth rates ](turing-machine.jpg)]
## Turing machines
Simplified human computer.
@@ -89,6 +92,14 @@ Algorithm is the instructions
Repetition == iteration or recursion
+What questions can we ask about algorithms?
+
+* Is it correct?
+* Does it terminate?
+* How long does it take?
+
+Different hardware works at different rates, so ask about how the run time changes with input size.
+
---
# Growth rates
@@ -143,6 +154,9 @@ word1 = "cat", word2 = "catty"
# Anagrams version 1a: checking off (fixed)
+
+
+
```
Given word1, word2
@@ -158,6 +172,26 @@ for pointer in range(len(word2)):
anagram? = False
return anagram?
```
+ |
+
+```
+Given word1, word2
+
+if len(word1) == len(word2):
+ anagram? = True
+ for character in word1:
+ for pointer in range(len(word2)):
+ if character == word2[pointer]:
+ word2[pointer] = None
+ else:
+ anagram? = False
+ return anagram?
+else:
+ return False
+```
+ |
+
+
---
@@ -280,6 +314,14 @@ Given a wordlist and a phrase, find another phrase that's an anagram.
---
+# Sorting with cards
+
+Classroom activity?
+
+Don't forget bogosort!
+
+---
+
# Dealing with complex problems: some terms to know
(M269 Unit 5)
@@ -292,22 +334,96 @@ Given a wordlist and a phrase, find another phrase that's an anagram.
* Often leads to logarithmic growth
"Guess the number" game
- * What if I don't tell you the upper limit?
+
+* What if I don't tell you the upper limit?
## Dynamic programming
Build a soluion bottom-up from subparts
-## Heuristics
+---
+
+# Heuristics
* Posh word for "guess"
* Greedy algorithms
* Backtracking
+
+# Parallelism vs concurrency
+
+* Parallelism is implementation
+ * spread the load
+* Concurrency is domain
+ * new task arrives before you've finished this one
+
---
-# 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) | (1, 1, 0) | (0, 0, 0) | (0, 0, 1) | (1, 0, 1) | (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) | (1, 0, 1) | (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) | (1, 0, 1) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ...
---
@@ -315,19 +431,21 @@ Classroom activity?
## 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
---
@@ -345,6 +463,14 @@ The computer would either answer "Yes," "No," or never stop working.
This is the Halting problem.
+```python
+while i != 0:
+ print(i)
+ i -= 1
+```
+
+Will this halt? When will it not?
+
---
# Universal Turing machine
@@ -364,7 +490,146 @@ A *universal* Turing machine can take the description of any Turing machine and
*This* shows that computing as we know it is possible.
+* Programming
+* Abstraction
+* Virtual machines
+* ...
+
+---
+
+# Back to halting
+
+* Universal Turing machine can do any possible computation
+* Has the same halting behaviour of the emulated machine
+
+Can we build another machine that detects if a machine halts when given some input?
+
+Assume we can...
+
+```python
+def does_it_stop(program, input):
+ if very_clever_decision:
+ return True
+ else:
+ return False
+```
+
+But I can use the program listing as an input:
+
+```python
+def stops_on_self(program):
+ return does_it_stop(program, program)
+```
+
+---
+
+# Halting: the clever bit
+
+
+
+
+```python
+def does_it_stop(program, input):
+ if very_clever_decision:
+ return True
+ else:
+ return False
+```
+ |
+
+```python
+def stops_on_self(program):
+ return does_it_stop(program, program)
+```
+ |
+
+
+
+Let's put an infinite loop in a program that detects infinite loops!
+
+```python
+def bobs_yer_uncle(program):
+ if stops_on_self(program):
+ while True:
+ pass
+ else:
+ return True
+```
+
+If a `program` halts on on itself, `bobs_yer_uncle` doesn't halt. If `program` doesn't halt, `bobs_yer_uncle` returns `True`.
+
+--
+
+What does this do?
+```python
+bobs_yer_uncle(bobs_yer_uncle)
+```
+
+---
+
+
+
+
+```python
+def does_it_stop(program, input):
+ if very_clever_decision:
+ return True
+ else:
+ return False
+```
+ |
+
+```python
+def stops_on_self(program):
+ return does_it_stop(program, program)
+```
+ |
+
+```python
+def bobs_yer_uncle(program):
+ if stops_on_self(program):
+ while True:
+ pass
+ else:
+ return True
+```
+ |
+
+
+
+What does this do?
+```python
+bobs_yer_uncle(bobs_yer_uncle)
+```
+
+
+If it halts... |
+If doesn't halt... |
+
+
+
+
+- `stops_on_self(bobs_yer_uncle)` returns `False`
+- `does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `False`
+- `bobs_yer_uncle(bobs_yer_uncle)` must loop forever
+
+Contradiction!
+ |
+
+
+- `stops_on_self(bobs_yer_uncle)` returns `True`
+- `does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `True`
+- `bobs_yer_uncle(bobs_yer_uncle)` must halt
+
+Contradiction!
+ |
+
+
+
+No flaw in the logic. The only place there could be a mistake is our assumption that `does_it_stop` is possible.
+
+(M269 has a different proof based on different sizes of infinity, and showing that there are infinitely more problems than there are Turing machines to solve them.)