4 <title>Algorithms
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
51 <textarea id=
"source">
53 # Algorithms ![Open University logo](oulogo_hor.png)
55 ## What's all the fuss about?
57 ![Alan Turing](alan-turing.jpg)
63 .indexlink[![Open University logo](oulogo_hor.png) [Index](index.html)]
67 # What is an algorithm? What is a computer?
69 Back when computers were human...
72 * (Small) working memory
73 * As much notepaper as you wanted
76 .float-right[![right-aligned Growth rates ](turing-machine.jpg)]
79 Simplified human computer.
81 * (Instructions + memory) → Finite number of states
82 * (States similar to places on a flowchart)
83 * Notepaper → tape (with limited symbols)
85 Algorithm is the instructions
87 (See TU100 Block
2 Part
1, M269 Unit
2)
91 # Sequence, selection, repetition
93 Repetition == iteration or recursion
95 What questions can we ask about algorithms?
99 * How long does it take?
101 Different hardware works at different rates, so ask about how the run time changes with input size.
107 ![left-aligned Growth rates ](big-o-chart-smaller.png) .float-right[![right-aligned Growth rates ](big-o-chart-
2-smaller.png)]
109 `\(f(n) \text{ is } O(g(n)) \quad\text{ if }\quad |f(n)| \le \; M |g(n)|\text{ for all }n \ge N\)`
112 # Complexity classes we care about
114 * Exponential or bigger (
2<sup>*n*
</sup>, *e*
<sup>*n*
</sup>, or *n*!)
115 * Polynomial (*n*
<sup>*k*
</sup>)
117 * Sub-linear (log *n*)
121 * polynomial or smaller is considered tractable
122 * anything exponential or larger is intractable
124 (Exceptions exist in practice.)
128 # Anagrams version
1: checking off
134 for character in word1:
135 for pointer in range(len(word2)):
136 if character == word2[pointer]:
137 word2[pointer] = None
143 Nested loops: complexity is *O*(*n*₁ × *n*₂), or *O*(*n*²).
147 Can anyone see the bug?
151 word1 =
"cat", word2 =
"catty"
155 # Anagrams version
1a: checking off (fixed)
164 for character in word1:
165 for pointer in range(len(word2)):
166 if character == word2[pointer]:
167 word2[pointer] = None
170 for pointer in range(len(word2)):
171 if word2[pointer] != None:
180 if len(word1) == len(word2):
182 for character in word1:
183 for pointer in range(len(word2)):
184 if character == word2[pointer]:
185 word2[pointer] = None
198 # Anagrams version
2: sort and comapre
203 return sorted(word1) == sorted(word2)
206 What's the complexity of `sorted`? What's the complexity of `==`?
210 # Anagrams version
2a: sort and comapre
215 sorted_word1 = sorted(word1)
216 sorted_word2 = sorted(word2)
219 for i in range(len(sorted_word1)):
220 if sorted_word1[i] != sorted_word2[i]:
225 One `for` in the comparison, so its complexity is *O*(*n*).
227 (`len` is also *O*(*n*))
229 What's the complexity of `sorted`?
233 # Anagrams version
2a': sort and comapre, idiomatic
238 sorted_word1 = sorted(word1)
239 sorted_word2 = sorted(word2)
242 for l1, l2 in zip_longest(sorted_word1, sorted_word2):
248 `zip_longest` is lazy, so still *O*(*n*).
250 (Can't use `zip` as it truncates the longest iterable, giving the same bug as number
1)
252 Still dominated by the *O*(*n* log *n*) of `sorted`.
256 # Anagrams version
3: permutations
262 for w in permutations(word1):
268 (Code for `permutations` is complex.)
270 How many permutations are there?
274 # Anagrams version
4: counters
283 counts1[num_of(c)] +=
1
286 counts2[num_of(c)] +=
1
290 if counts1[i] != counts2[
1]:
295 Three `for`s, but they're not nested. Complexity is *O*(*n*₁ + *n*₂ +
26) or *O*(*n*).
297 `dict`s seem a natural way of representing the count. What do you need to be careful of?
299 (Alternative: maintain a single list of differences in letter counts. Initialise to all zero, should be all zero when you've finished.)
301 Notice: trading space for time.
305 # Finding all anagrams
307 Given a `wordlist` and a `word`, find all anagrams of `word` in `wordlist`.
309 * How does your answer change if you know you need to do this just once, or millions of times?
311 # Anagrams of phrases
313 Given a wordlist and a phrase, find another phrase that's an anagram.
321 Don't forget bogosort!
325 # Dealing with complex problems: some terms to know
329 ## Divide and Conquer
331 * Split a problem into smaller parts
333 * Combine the sub-solutions
334 * Often leads to logarithmic growth
336 "Guess the number" game
338 * What if I don't tell you the upper limit?
340 ## Dynamic programming
342 Build a soluion bottom-up from subparts
348 * Posh word for
"guess"
352 # Parallelism vs concurrency
354 * Parallelism is implementation
356 * Concurrency is domain
357 * new task arrives before you've finished this one
365 * some money and a set of coin denominations,
369 * the smallest number of coins to make that total.
371 ## Approach
1: greedy
375 Pick the biggest coin you can
378 Only works in some cases
380 (What the best way to make
7p if you have
1p,
3p,
4p,
5p coins?)
384 # Making change
2: exhaustive search
386 .float-right[![Ticket to Ride](make-change.dot.png)]
388 Make a tree of change-making.
394 # Making change
3: dynamic programming
400 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | ...
401 -|-|-|-|-|-|-|-|-|-|-|-
402 (
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) | ...
406 0* |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | ...
407 -|-|-|-|-|-|-|-|-|-|-|-
408 (
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) | ...
412 0 |
1* |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | ...
413 -|-|-|-|-|-|-|-|-|-|-|-
414 (
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) | ...
418 0 |
1 |
2* |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 | ...
419 -|-|-|-|-|-|-|-|-|-|-|-
420 (
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) | ...
424 0 |
1 |
2 |
3* |
4 |
5 |
6 |
7 |
8 |
9 |
10 | ...
425 -|-|-|-|-|-|-|-|-|-|-|-
426 (
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) | ...
432 ## Travelling Salesman Problem
434 .float-right[![Ticket to Ride](ticket-to-ride-small.jpg)]
438 http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
440 * But many implementations are Java applets, now a problem with security settings
442 Try Android/iOS apps?
444 ## Ticket to Ride boardgame
452 # Turing and computability
454 (Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/))
456 ## The Entscheidungsproblem (Decision problem)
458 Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms?
460 The rules could be described to a human computer.
462 The computer would either answer
"Yes," "No," or never stop working.
464 This is the Halting problem.
472 Will this halt? When will it not?
476 # Universal Turing machine
478 .float-right[![A computer](human-computer-worksheet.png)]
480 A Turing machine does one particular job
482 But you can describe how to do that job to another person
484 In other words, you can treat the instructions as the input to another machine
486 A *universal* Turing machine can take the description of any Turing machine and produce the same output
488 * Instruction = input
491 *This* shows that computing as we know it is possible.
502 * Universal Turing machine can do any possible computation
503 * Has the same halting behaviour of the emulated machine
505 Can we build another machine that detects if a machine halts when given some input?
510 def does_it_stop(program, input):
511 if very_clever_decision:
517 But I can use the program listing as an input:
520 def stops_on_self(program):
521 return does_it_stop(program, program)
526 # Halting: the clever bit
532 def does_it_stop(program, input):
533 if very_clever_decision:
541 def stops_on_self(program):
542 return does_it_stop(program, program)
548 Let's put an infinite loop in a program that detects infinite loops!
551 def bobs_yer_uncle(program):
552 if stops_on_self(program):
559 If a `program` halts on on itself, `bobs_yer_uncle` doesn't halt. If `program` doesn't halt, `bobs_yer_uncle` returns `True`.
565 bobs_yer_uncle(bobs_yer_uncle)
574 def does_it_stop(program, input):
575 if very_clever_decision:
583 def stops_on_self(program):
584 return does_it_stop(program, program)
589 def bobs_yer_uncle(program):
590 if stops_on_self(program):
602 bobs_yer_uncle(bobs_yer_uncle)
607 <th>If it halts...
</th>
608 <th>If doesn't halt...
</th>
613 <li>`stops_on_self(bobs_yer_uncle)` returns `False`
</li>
614 <li>`does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `False`
</li>
615 <li>`bobs_yer_uncle(bobs_yer_uncle)` must loop forever
</li>
617 <b>Contradiction!
</b>
621 <li>`stops_on_self(bobs_yer_uncle)` returns `True`
</li>
622 <li>`does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `True`
</li>
623 <li>`bobs_yer_uncle(bobs_yer_uncle)` must halt
</li>
625 <b>Contradiction!
</b>
630 No flaw in the logic. The only place there could be a mistake is our assumption that `does_it_stop` is possible.
632 (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.)
636 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
639 <script type=
"text/javascript"
640 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
642 <script type=
"text/javascript">
643 var slideshow = remark.create({ ratio:
"16:9" });
648 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
651 MathJax.Hub.Queue(function() {
652 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
653 return(elem.SourceElement());
654 }).parent().addClass('has-jax');
656 MathJax.Hub.Configured();