## What's all the fuss about?
+
+
+---
+
+layout: true
+
+.indexlink[[Index](index.html)]
+
+---
+
+# What is an algorithm? What is a computer?
+
+Back when computers were human...
+
+* Instructions
+* (Small) working memory
+* As much notepaper as you wanted
+* Input → output
+
+.float-right[]
+## Turing machines
+
+Simplified human computer.
+
+* (Instructions + memory) → Finite number of states
+ * (States similar to places on a flowchart)
+* Notepaper → tape (with limited symbols)
+
+Algorithm is the instructions
+
+(See TU100 Block 2 Part 1, M269 Unit 2)
+
+---
+
+# Sequence, selection, repetition
+
+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
+
+ .float-right[]
+
+`\(f(n) \text{ is } O(g(n)) \quad\text{ if }\quad |f(n)| \le \; M |g(n)|\text{ for all }n \ge N\)`
+
+---
+# Complexity classes we care about
+
+* Exponential or bigger (2<sup>*n*</sup>, *e*<sup>*n*</sup>, or *n*!)
+* Polynomial (*n*<sup>*k*</sup>)
+* Linear (*n*)
+* Sub-linear (log *n*)
+
+Generally:
+
+* polynomial or smaller is considered tractable
+* anything exponential or larger is intractable
+
+(Exceptions exist in practice.)
+
+---
+
+# Anagrams version 1: checking off
+
+```
+Given word1, 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?
+```
+
+Nested loops: complexity is *O*(*n*₁ × *n*₂), or *O*(*n*²).
+
+--
+
+Can anyone see the bug?
+
+--
+
+word1 = "cat", word2 = "catty"
+
+---
+
+# Anagrams version 1a: checking off (fixed)
+
+<table width="100%">
+<tr>
+<td>
+```
+Given word1, word2
+
+anagram? = True
+for character in word1:
+ for pointer in range(len(word2)):
+ if character == word2[pointer]:
+ word2[pointer] = None
+ else:
+ anagram? = False
+for pointer in range(len(word2)):
+ if word2[pointer] != None:
+ anagram? = False
+return anagram?
+```
+</td>
+<td>
+```
+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
+```
+</td>
+</tr>
+</table>
+
+---
+
+# Anagrams version 2: sort and comapre
+
+```
+Given word1, word2
+
+return sorted(word1) == sorted(word2)
+```
+
+What's the complexity of `sorted`? What's the complexity of `==`?
+
+---
+
+# Anagrams version 2a: sort and comapre
+
+```
+Given word1, word2
+
+sorted_word1 = sorted(word1)
+sorted_word2 = sorted(word2)
+
+anagram? = True
+for i in range(len(sorted_word1)):
+ if sorted_word1[i] != sorted_word2[i]:
+ anagram? = False
+return anagram?
+```
+
+One `for` in the comparison, so its complexity is *O*(*n*).
+
+(`len` is also *O*(*n*))
+
+What's the complexity of `sorted`?
+
+---
+
+# Anagrams version 2a': sort and comapre, idiomatic
+
+```
+Given word1, word2
+
+sorted_word1 = sorted(word1)
+sorted_word2 = sorted(word2)
+
+anagram? = True
+for l1, l2 in zip_longest(sorted_word1, sorted_word2):
+ if l1 != l2:
+ anagram? = False
+return anagram?
+```
+
+`zip_longest` is lazy, so still *O*(*n*).
+
+(Can't use `zip` as it truncates the longest iterable, giving the same bug as number 1)
+
+Still dominated by the *O*(*n* log *n*) of `sorted`.
+
+---
+
+# Anagrams version 3: permutations
+
+```
+Given word1, word2
+
+anagram? = False
+for w in permutations(word1):
+ w == word2:
+ anagram? = True
+return anagram?
+```
+
+(Code for `permutations` is complex.)
+
+How many permutations are there?
+
+---
+
+# Anagrams version 4: counters
+
+```
+Given word1, word2
+
+counts1 = [0] * 26
+counts2 = [0] * 26
+
+for c in word1:
+ counts1[num_of(c)] += 1
+
+for c in word2:
+ counts2[num_of(c)] += 1
+
+anagram? = True
+for i in range(26):
+ if counts1[i] != counts2[1]:
+ anagram = False
+return anagram?
+```
+
+Three `for`s, but they're not nested. Complexity is *O*(*n*₁ + *n*₂ + 26) or *O*(*n*).
+
+`dict`s seem a natural way of representing the count. What do you need to be careful of?
+
+(Alternative: maintain a single list of differences in letter counts. Initialise to all zero, should be all zero when you've finished.)
+
+Notice: trading space for time.
+
+---
+
+# Finding all anagrams
+
+Given a `wordlist` and a `word`, find all anagrams of `word` in `wordlist`.
+
+* How does your answer change if you know you need to do this just once, or millions of times?
+
+# Anagrams of phrases
+
+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)
+
+## Divide and Conquer
+
+* Split a problem into smaller parts
+* Solve them
+* Combine the sub-solutions
+* Often leads to logarithmic growth
+
+"Guess the number" game
+
+* What if I don't tell you the upper limit?
+
+## Dynamic programming
+
+Build a soluion bottom-up from subparts
+
+---
+
+# 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
+
+---
+
+# Making change
+
+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[]
+
+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) | ...
+
+---
+
+# Algorithmic games
+
+## Travelling Salesman Problem
+
+.float-right[]
+
+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?
+
+## Ticket to Ride boardgame
+
+Graph algorithms
+
+* Find shortest path
+
+---
+
+# Turing and computability
+
+(Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/))
+
+## The Entscheidungsproblem (Decision problem)
+
+Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms?
+
+The rules could be described to a human computer.
+
+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
+
+.float-right[]
+
+A Turing machine does one particular job
+
+But you can describe how to do that job to another person
+
+In other words, you can treat the instructions as the input to another machine
+
+A *universal* Turing machine can take the description of any Turing machine and produce the same output
+
+* Instruction = input
+* Program = data
+
+*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
+
+<table width="100%">
+<tr>
+<td>
+```python
+def does_it_stop(program, input):
+ if very_clever_decision:
+ return True
+ else:
+ return False
+```
+</td>
+<td>
+```python
+def stops_on_self(program):
+ return does_it_stop(program, program)
+```
+</td>
+</tr>
+</table>
+
+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)
+```
+
+---
+
+<table width="100%">
+<tr>
+<td>
+```python
+def does_it_stop(program, input):
+ if very_clever_decision:
+ return True
+ else:
+ return False
+```
+</td>
+<td>
+```python
+def stops_on_self(program):
+ return does_it_stop(program, program)
+```
+</td>
+<td>
+```python
+def bobs_yer_uncle(program):
+ if stops_on_self(program):
+ while True:
+ pass
+ else:
+ return True
+```
+</td>
+</tr>
+</table>
+
+What does this do?
+```python
+bobs_yer_uncle(bobs_yer_uncle)
+```
+
+<table>
+<tr>
+<th>If it halts...</th>
+<th>If doesn't halt...</th>
+</td>
+<tr>
+<td>
+<ul>
+<li>`stops_on_self(bobs_yer_uncle)` returns `False`</li>
+<li>`does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `False`</li>
+<li>`bobs_yer_uncle(bobs_yer_uncle)` must loop forever</li>
+</ul>
+<b>Contradiction!</b>
+</td>
+<td>
+<ul>
+<li>`stops_on_self(bobs_yer_uncle)` returns `True`</li>
+<li>`does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `True`</li>
+<li>`bobs_yer_uncle(bobs_yer_uncle)` must halt</li>
+</ul>
+<b>Contradiction!</b>
+</td>
+</tr>
+</table>
+
+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.)
+
</textarea>
<script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
projects / cas-master-teacher-training.git / blobdiff