algorithms.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>Algorithms</title>
   5     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
   6     <style type="text/css">
   7       /* Slideshow styles */
   8       body {
   9         font-size: 20px;
  10       }
  11       h1, h2, h3 {
  12         font-weight: 400;
  13         margin-bottom: 0;
  14       }
  15       h1 { font-size: 3em; }
  16       h2 { font-size: 2em; }
  17       h3 { font-size: 1.6em; }
  18       a, a > code {
  19         text-decoration: none;
  20       }
  21       code {
  22         -moz-border-radius: 5px;
  23         -web-border-radius: 5px;
  24         background: #e7e8e2;
  25         border-radius: 5px;
  26         font-size: 16px;
  27       }
  28       .plaintext {
  29         background: #272822;
  30         color: #80ff80;
  31         text-shadow: 0 0 20px #333;
  32         padding: 2px 5px;
  33       }
  34       .ciphertext {
  35         background: #272822;
  36         color: #ff6666;
  37         text-shadow: 0 0 20px #333;
  38         padding: 2px 5px;
  39       }
  40       .indexlink {
  41         position: absolute;
  42         bottom: 1em;
  43         left: 1em;
  44       }
  45        .float-right {
  46         float: right;
  47       }
  48     </style>
  49   </head>
  50   <body>
  51     <textarea id="source">
  52
  53 # Algorithms ![Open University logo](oulogo_hor.png)
  54
  55 ## What's all the fuss about?
  56
  57 ![Alan Turing](alan-turing.jpg)
  58
  59 ---
  60
  61 layout: true
  62
  63 .indexlink[![Open University logo](oulogo_hor.png) [Index](index.html)]
  64
  65 ---
  66
  67 # What is an algorithm? What is a computer?
  68
  69 Back when computers were human...
  70
  71 * Instructions
  72 * (Small) working memory
  73 * As much notepaper as you wanted
  74 * Input → output
  75
  76 .float-right[![right-aligned Growth rates ](turing-machine.jpg)]
  77 ## Turing machines
  78
  79 Simplified human computer.
  80
  81 * (Instructions + memory) → Finite number of states
  82     * (States similar to places on a flowchart)
  83 * Notepaper → tape (with limited symbols)
  84
  85 Algorithm is the instructions
  86
  87 (See TU100 Block 2 Part 1, M269 Unit 2)
  88
  89 ---
  90
  91 # Sequence, selection, repetition
  92
  93 Repetition == iteration or recursion
  94
  95 What questions can we ask about algorithms?
  96
  97 * Is it correct?
  98 * Does it terminate?
  99 * How long does it take?
 100
 101 Different hardware works at different rates, so ask about how the run time changes with input size.
 102
 103 ---
 104
 105 # Growth rates
 106
 107 ![left-aligned Growth rates ](big-o-chart-smaller.png) .float-right[![right-aligned Growth rates ](big-o-chart-2-smaller.png)]
 108
 109 `\(f(n) \text{ is } O(g(n)) \quad\text{ if }\quad |f(n)| \le \; M |g(n)|\text{ for all }n \ge N\)`
 110
 111 ---
 112 # Complexity classes we care about
 113
 114 * Exponential or bigger (2<sup>*n*</sup>, *e*<sup>*n*</sup>, or *n*!)
 115 * Polynomial (*n*<sup>*k*</sup>)
 116 * Linear (*n*)
 117 * Sub-linear (log *n*)
 118
 119 Generally:
 120
 121 * polynomial or smaller is considered tractable
 122 * anything exponential or larger is intractable
 123
 124 (Exceptions exist in practice.)
 125
 126 ---
 127
 128 # Anagrams version 1: checking off
 129
 130 ```
 131 Given word1, word2
 132
 133 anagram? = True
 134 for character in word1:
 135     for pointer in range(len(word2)):
 136         if character == word2[pointer]:
 137             word2[pointer] = None
 138         else:
 139             anagram? = False
 140 return anagram?
 141 ```
 142
 143 Nested loops: complexity is *O*(*n*₁ × *n*₂), or *O*(*n*²).
 144
 145 --
 146
 147 Can anyone see the bug?
 148
 149 --
 150
 151 word1 = "cat", word2 = "catty"
 152
 153 ---
 154
 155 # Anagrams version 1a: checking off (fixed)
 156
 157 <table width="100%">
 158 <tr>
 159 <td>
 160 ```
 161 Given word1, word2
 162
 163 anagram? = True
 164 for character in word1:
 165     for pointer in range(len(word2)):
 166         if character == word2[pointer]:
 167             word2[pointer] = None
 168         else:
 169             anagram? = False
 170 for pointer in range(len(word2)):
 171     if word2[pointer] != None:
 172         anagram? = False
 173 return anagram?
 174 ```
 175 </td>
 176 <td>
 177 ```
 178 Given word1, word2
 179
 180 if len(word1) == len(word2):
 181     anagram? = True
 182     for character in word1:
 183         for pointer in range(len(word2)):
 184             if character == word2[pointer]:
 185                 word2[pointer] = None
 186             else:
 187                 anagram? = False
 188     return anagram?
 189 else:
 190     return False
 191 ```
 192 </td>
 193 </tr>
 194 </table>
 195
 196 ---
 197
 198 # Anagrams version 2: sort and comapre
 199
 200 ```
 201 Given word1, word2
 202
 203 return sorted(word1) == sorted(word2)
 204 ```
 205
 206 What's the complexity of `sorted`? What's the complexity of `==`?
 207
 208 ---
 209
 210 # Anagrams version 2a: sort and comapre
 211
 212 ```
 213 Given word1, word2
 214
 215 sorted_word1 = sorted(word1)
 216 sorted_word2 = sorted(word2)
 217
 218 anagram? = True
 219 for i in range(len(sorted_word1)):
 220     if sorted_word1[i] != sorted_word2[i]:
 221         anagram? = False
 222 return anagram?
 223 ```
 224
 225 One `for` in the comparison, so its complexity is *O*(*n*).
 226
 227 (`len` is also *O*(*n*))
 228
 229 What's the complexity of `sorted`?
 230
 231 ---
 232
 233 # Anagrams version 2a': sort and comapre, idiomatic
 234
 235 ```
 236 Given word1, word2
 237
 238 sorted_word1 = sorted(word1)
 239 sorted_word2 = sorted(word2)
 240
 241 anagram? = True
 242 for l1, l2 in zip_longest(sorted_word1, sorted_word2):
 243     if l1 != l2:
 244         anagram? = False
 245 return anagram?
 246 ```
 247
 248 `zip_longest` is lazy, so still *O*(*n*).
 249
 250 (Can't use `zip` as it truncates the longest iterable, giving the same bug as number 1)
 251
 252 Still dominated by the *O*(*n* log *n*) of `sorted`.
 253
 254 ---
 255
 256 # Anagrams version 3: permutations
 257
 258 ```
 259 Given word1, word2
 260
 261 anagram? = False
 262 for w in permutations(word1):
 263     w == word2:
 264         anagram? = True
 265 return anagram?
 266 ```
 267
 268 (Code for `permutations` is complex.)
 269
 270 How many permutations are there?
 271
 272 ---
 273
 274 # Anagrams version 4: counters
 275
 276 ```
 277 Given word1, word2
 278
 279 counts1 = [0] * 26
 280 counts2 = [0] * 26
 281
 282 for c in word1:
 283     counts1[num_of(c)] += 1
 284
 285 for c in word2:
 286     counts2[num_of(c)] += 1
 287
 288 anagram? = True
 289 for i in range(26):
 290     if counts1[i] != counts2[1]:
 291         anagram = False
 292 return anagram?
 293 ```
 294
 295 Three `for`s, but they're not nested. Complexity is *O*(*n*₁ + *n*₂ + 26) or *O*(*n*).
 296
 297 `dict`s seem a natural way of representing the count. What do you need to be careful of?
 298
 299 (Alternative: maintain a single list of differences in letter counts. Initialise to all zero, should be all zero when you've finished.)
 300
 301 Notice: trading space for time.
 302
 303 ---
 304
 305 # Finding all anagrams
 306
 307 Given a `wordlist` and a `word`, find all anagrams of `word` in `wordlist`.
 308
 309 * How does your answer change if you know you need to do this just once, or millions of times?
 310
 311 # Anagrams of phrases
 312
 313 Given a wordlist and a phrase, find another phrase that's an anagram.
 314
 315 ---
 316
 317 # Sorting with cards
 318
 319 Classroom activity?
 320
 321 Don't forget bogosort!
 322
 323 ---
 324
 325 # Dealing with complex problems: some terms to know
 326
 327 (M269 Unit 5)
 328
 329 ## Divide and Conquer
 330
 331 * Split a problem into smaller parts
 332 * Solve them
 333 * Combine the sub-solutions
 334 * Often leads to logarithmic growth
 335
 336 "Guess the number" game
 337
 338 * What if I don't tell you the upper limit?
 339
 340 ## Dynamic programming
 341
 342 Build a soluion bottom-up from subparts
 343
 344 ---
 345
 346 # Heuristics
 347
 348 * Posh word for "guess"
 349 * Greedy algorithms
 350 * Backtracking
 351
 352 # Parallelism vs concurrency
 353
 354 * Parallelism is implementation
 355     * spread the load
 356 * Concurrency is domain
 357     * new task arrives before you've finished this one
 358
 359 ---
 360
 361 # Making change
 362
 363 Given
 364
 365 * some money and a set of coin denominations,
 366
 367 find
 368
 369 * the smallest number of coins to make that total.
 370
 371 ## Approach 1: greedy
 372
 373 ```
 374 Repeat:
 375    Pick the biggest coin you can
 376 ```
 377
 378 Only works in some cases
 379
 380 (What the best way to make 7p if you have 1p, 3p, 4p, 5p coins?)
 381
 382 ---
 383
 384 # Making change 2: exhaustive search
 385
 386 .float-right[![Ticket to Ride](make-change.dot.png)]
 387
 388 Make a tree of change-making.
 389
 390 Pick the optimal.
 391
 392 ---
 393
 394 # Making change 3: dynamic programming
 395
 396 Bottom-up approach
 397
 398 Initial:
 399
 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) | ...
 403
 404 --
 405 ----
 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) | ...
 409
 410 --
 411 ----
 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) | ...
 415
 416 --
 417 ----
 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) | ...
 421
 422 --
 423 ----
 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) | ...
 427
 428 ---
 429
 430 # Algorithmic games
 431
 432 ## Travelling Salesman Problem
 433
 434 .float-right[![Ticket to Ride](ticket-to-ride-small.jpg)]
 435
 436 Online:
 437
 438 http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
 439
 440 * But many implementations are Java applets, now a problem with security settings
 441
 442 Try Android/iOS apps?
 443
 444 ## Ticket to Ride boardgame
 445
 446 Graph algorithms
 447
 448 * Find shortest path
 449
 450 ---
 451
 452 # Turing and computability
 453
 454 (Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/))
 455
 456 ## The Entscheidungsproblem (Decision problem)
 457
 458 Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms?
 459
 460 The rules could be described to a human computer.
 461
 462 The computer would either answer "Yes," "No," or never stop working.
 463
 464 This is the Halting problem.
 465
 466 ```python
 467 while i != 0:
 468     print(i)
 469     i -= 1
 470 ```
 471
 472 Will this halt? When will it not?
 473
 474 ---
 475
 476 # Universal Turing machine
 477
 478 .float-right[![A computer](human-computer-worksheet.png)]
 479
 480 A Turing machine does one particular job
 481
 482 But you can describe how to do that job to another person
 483
 484 In other words, you can treat the instructions as the input to another machine
 485
 486 A *universal* Turing machine can take the description of any Turing machine and produce the same output
 487
 488 * Instruction = input
 489 * Program = data
 490
 491 *This* shows that computing as we know it is possible.
 492
 493 * Programming
 494 * Abstraction
 495 * Virtual machines
 496 * ...
 497
 498 ---
 499
 500 # Back to halting
 501
 502 * Universal Turing machine can do any possible computation
 503 * Has the same halting behaviour of the emulated machine
 504
 505 Can we build another machine that detects if a machine halts when given some input?
 506
 507 Assume we can...
 508
 509 ```python
 510 def does_it_stop(program, input):
 511     if very_clever_decision:
 512         return True
 513     else:
 514         return False
 515 ```
 516
 517 But I can use the program listing as an input:
 518
 519 ```python
 520 def stops_on_self(program):
 521     return does_it_stop(program, program)
 522 ```
 523
 524 ---
 525
 526 # Halting: the clever bit
 527
 528 <table width="100%">
 529 <tr>
 530 <td>
 531 ```python
 532 def does_it_stop(program, input):
 533     if very_clever_decision:
 534         return True
 535     else:
 536         return False
 537 ```
 538 </td>
 539 <td>
 540 ```python
 541 def stops_on_self(program):
 542     return does_it_stop(program, program)
 543 ```
 544 </td>
 545 </tr>
 546 </table>
 547
 548 Let's put an infinite loop in a program that detects infinite loops!
 549
 550 ```python
 551 def bobs_yer_uncle(program):
 552     if stops_on_self(program):
 553         while True:
 554             pass
 555     else:
 556         return True
 557 ```
 558
 559 If a `program` halts on on itself, `bobs_yer_uncle` doesn't halt. If `program` doesn't halt, `bobs_yer_uncle` returns `True`.
 560
 561 --
 562
 563 What does this do?
 564 ```python
 565 bobs_yer_uncle(bobs_yer_uncle)
 566 ```
 567
 568 ---
 569
 570 <table width="100%">
 571 <tr>
 572 <td>
 573 ```python
 574 def does_it_stop(program, input):
 575     if very_clever_decision:
 576         return True
 577     else:
 578         return False
 579 ```
 580 </td>
 581 <td>
 582 ```python
 583 def stops_on_self(program):
 584     return does_it_stop(program, program)
 585 ```
 586 </td>
 587 <td>
 588 ```python
 589 def bobs_yer_uncle(program):
 590     if stops_on_self(program):
 591         while True:
 592             pass
 593     else:
 594         return True
 595 ```
 596 </td>
 597 </tr>
 598 </table>
 599
 600 What does this do?
 601 ```python
 602 bobs_yer_uncle(bobs_yer_uncle)
 603 ```
 604
 605 <table>
 606 <tr>
 607 <th>If it halts...</th>
 608 <th>If doesn't halt...</th>
 609 </td>
 610 <tr>
 611 <td>
 612 <ul>
 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>
 616 </ul>
 617 <b>Contradiction!</b>
 618 </td>
 619 <td>
 620 <ul>
 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>
 624 </ul>
 625 <b>Contradiction!</b>
 626 </td>
 627 </tr>
 628 </table>
 629
 630 No flaw in the logic. The only place there could be a mistake is our assumption that `does_it_stop` is possible.
 631
 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.)
 633
 634
 635     </textarea>
 636     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 637     </script>
 638
 639     <script type="text/javascript"
 640       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 641
 642     <script type="text/javascript">
 643       var slideshow = remark.create({ ratio: "16:9" });
 644
 645       // Setup MathJax
 646       MathJax.Hub.Config({
 647         tex2jax: {
 648         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 649         }
 650       });
 651       MathJax.Hub.Queue(function() {
 652         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 653             return(elem.SourceElement());
 654         }).parent().addClass('has-jax');
 655       });
 656       MathJax.Hub.Configured();
 657     </script>
 658   </body>
 659 </html>