X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=algorithms.html;h=bbe92f16b0480599da0df4e0230dec35e79a6ad0;hb=101323e82469479265f98255369ba0c1eca416cb;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.)