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
  54
  55 ## What's all the fuss about?
  56
  57 ---
  58
  59 layout: true
  60
  61 .indexlink[[Index](index.html)]
  62
  63 ---
  64
  65 # What is an algorithm? What is a computer?
  66
  67 Back when computers were human...
  68
  69 * Instructions
  70 * (Small) working memory
  71 * As much notepaper as you wanted
  72 * Input → output
  73
  74 ## Turing machines
  75
  76 Simplified human computer.
  77
  78 * (Instructions + memory) → Finite number of states
  79     * (States similar to places on a flowchart)
  80 * Notepaper → tape (with limited symbols)
  81
  82 Algorithm is the instructions
  83
  84 (See TU100 Block 2 Part 1, M269 Unit 2)
  85
  86 ---
  87
  88 # Sequence, selection, repetition
  89
  90 Repetition == iteration or recursion
  91
  92 ---
  93
  94 # Growth rates
  95
  96 ![left-aligned Growth rates ](big-o-chart-smaller.png) .float-right[![right-aligned Growth rates ](big-o-chart-2-smaller.png)]
  97
  98 `\(f(n) \text{ is } O(g(n)) \quad\text{ if }\quad |f(n)| \le \; M |g(n)|\text{ for all }n \ge N\)`
  99
 100 ---
 101 # Complexity classes we care about
 102
 103 * Exponential or bigger (2<sup>*n*</sup>, *e*<sup>*n*</sup>, or *n*!)
 104 * Polynomial (*n*<sup>*k*</sup>)
 105 * Linear (*n*)
 106 * Sub-linear (log *n*)
 107
 108 Generally:
 109
 110 * polynomial or smaller is considered tractable
 111 * anything exponential or larger is intractable
 112
 113 (Exceptions exist in practice.)
 114
 115 ---
 116
 117 # Anagrams version 1: checking off
 118
 119 ```
 120 Given word1, word2
 121
 122 anagram? = True
 123 for character in word1:
 124     for pointer in range(len(word2)):
 125         if character == word2[pointer]:
 126             word2[pointer] = None
 127         else:
 128             anagram? = False
 129 return anagram?
 130 ```
 131
 132 Nested loops: complexity is *O*(*n*₁ × *n*₂), or *O*(*n*²).
 133
 134 --
 135
 136 Can anyone see the bug?
 137
 138 --
 139
 140 word1 = "cat", word2 = "catty"
 141
 142 ---
 143
 144 # Anagrams version 1a: checking off (fixed)
 145
 146 ```
 147 Given word1, word2
 148
 149 anagram? = True
 150 for character in word1:
 151     for pointer in range(len(word2)):
 152         if character == word2[pointer]:
 153             word2[pointer] = None
 154         else:
 155             anagram? = False
 156 for pointer in range(len(word2)):
 157     if word2[pointer] != None:
 158         anagram? = False
 159 return anagram?
 160 ```
 161
 162 ---
 163
 164 # Anagrams version 2: sort and comapre
 165
 166 ```
 167 Given word1, word2
 168
 169 return sorted(word1) == sorted(word2)
 170 ```
 171
 172 What's the complexity of `sorted`? What's the complexity of `==`?
 173
 174 ---
 175
 176 # Anagrams version 2a: sort and comapre
 177
 178 ```
 179 Given word1, word2
 180
 181 sorted_word1 = sorted(word1)
 182 sorted_word2 = sorted(word2)
 183
 184 anagram? = True
 185 for i in range(len(sorted_word1)):
 186     if sorted_word1[i] != sorted_word2[i]:
 187         anagram? = False
 188 return anagram?
 189 ```
 190
 191 One `for` in the comparison, so its complexity is *O*(*n*).
 192
 193 (`len` is also *O*(*n*))
 194
 195 What's the complexity of `sorted`?
 196
 197 ---
 198
 199 # Anagrams version 2a': sort and comapre, idiomatic
 200
 201 ```
 202 Given word1, word2
 203
 204 sorted_word1 = sorted(word1)
 205 sorted_word2 = sorted(word2)
 206
 207 anagram? = True
 208 for l1, l2 in zip_longest(sorted_word1, sorted_word2):
 209     if l1 != l2:
 210         anagram? = False
 211 return anagram?
 212 ```
 213
 214 `zip_longest` is lazy, so still *O*(*n*).
 215
 216 (Can't use `zip` as it truncates the longest iterable, giving the same bug as number 1)
 217
 218 Still dominated by the *O*(*n* log *n*) of `sorted`.
 219
 220 ---
 221
 222 # Anagrams version 3: permutations
 223
 224 ```
 225 Given word1, word2
 226
 227 anagram? = False
 228 for w in permutations(word1):
 229     w == word2:
 230         anagram? = True
 231 return anagram?
 232 ```
 233
 234 (Code for `permutations` is complex.)
 235
 236 How many permutations are there?
 237
 238 ---
 239
 240 # Anagrams version 4: counters
 241
 242 ```
 243 Given word1, word2
 244
 245 counts1 = [0] * 26
 246 counts2 = [0] * 26
 247
 248 for c in word1:
 249     counts1[num_of(c)] += 1
 250
 251 for c in word2:
 252     counts2[num_of(c)] += 1
 253
 254 anagram? = True
 255 for i in range(26):
 256     if counts1[i] != counts2[1]:
 257         anagram = False
 258 return anagram?
 259 ```
 260
 261 Three `for`s, but they're not nested. Complexity is *O*(*n*₁ + *n*₂ + 26) or *O*(*n*).
 262
 263 `dict`s seem a natural way of representing the count. What do you need to be careful of?
 264
 265 (Alternative: maintain a single list of differences in letter counts. Initialise to all zero, should be all zero when you've finished.)
 266
 267 Notice: trading space for time.
 268
 269 ---
 270
 271 # Finding all anagrams
 272
 273 Given a `wordlist` and a `word`, find all anagrams of `word` in `wordlist`.
 274
 275 * How does your answer change if you know you need to do this just once, or millions of times?
 276
 277 # Anagrams of phrases
 278
 279 Given a wordlist and a phrase, find another phrase that's an anagram.
 280
 281 ---
 282
 283 # Sorting with cards
 284
 285 Classroom activity?
 286
 287 Don't forget bogosort!
 288
 289 ---
 290
 291 # Dealing with complex problems: some terms to know
 292
 293 (M269 Unit 5)
 294
 295 ## Divide and Conquer
 296
 297 * Split a problem into smaller parts
 298 * Solve them
 299 * Combine the sub-solutions
 300 * Often leads to logarithmic growth
 301
 302 "Guess the number" game
 303     * What if I don't tell you the upper limit?
 304
 305 ## Dynamic programming
 306
 307 Build a soluion bottom-up from subparts
 308
 309 ---
 310
 311 # Heuristics
 312
 313 * Posh word for "guess"
 314 * Greedy algorithms
 315 * Backtracking
 316
 317 ---
 318
 319 # Making change
 320
 321 Given
 322
 323 * some money and a set of coin denominations,
 324
 325 find
 326
 327 * the smallest number of coins to make that total.
 328
 329 ## Approach 1: greedy
 330
 331 ```
 332 Repeat:
 333    Pick the biggest coin you can
 334 ```
 335
 336 Only works in some cases
 337
 338 (What the best way to make 7p if you have 1p, 3p, 4p, 5p coins?)
 339
 340 ---
 341
 342 # Making change 2: exhaustive search
 343
 344 .float-right[![Ticket to Ride](make-change.dot.png)]
 345
 346 Make a tree of change-making.
 347
 348 Pick the optimal.
 349
 350 ---
 351
 352 # Making change 3: dynamic programming
 353
 354 Bottom-up approach
 355
 356 Initial:
 357
 358 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 359 -|-|-|-|-|-|-|-|-|-|-|-
 360 (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) | ...
 361
 362 --
 363 ----
 364 0* | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 365 -|-|-|-|-|-|-|-|-|-|-|-
 366 (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) | ...
 367
 368 --
 369 ----
 370 0 | 1* | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 371 -|-|-|-|-|-|-|-|-|-|-|-
 372 (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) | ...
 373
 374 --
 375 ----
 376 0 | 1 | 2* | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 377 -|-|-|-|-|-|-|-|-|-|-|-
 378 (0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ...
 379
 380 --
 381 ----
 382 0 | 1 | 2 | 3* | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ...
 383 -|-|-|-|-|-|-|-|-|-|-|-
 384 (0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ...
 385
 386 ---
 387
 388 # Algorithmic games
 389
 390 ## Travelling Salesman Problem
 391
 392 .float-right[![Ticket to Ride](ticket-to-ride-small.jpg)]
 393
 394 Online:
 395
 396 http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
 397
 398 * But many implementations are Java applets, now a problem with security settings
 399
 400 Try Android/iOS apps?
 401
 402 ## Ticket to Ride boardgame
 403
 404 Graph algorithms
 405
 406 * Find shortest path
 407
 408 ---
 409
 410 # Turing and computability
 411
 412 (Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/))
 413
 414 ## The Entscheidungsproblem (Decision problem)
 415
 416 Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms?
 417
 418 The rules could be described to a human computer.
 419
 420 The computer would either answer "Yes," "No," or never stop working.
 421
 422 This is the Halting problem.
 423
 424 ---
 425
 426 # Universal Turing machine
 427
 428 .float-right[![A computer](human-computer-worksheet.png)]
 429
 430 A Turing machine does one particular job
 431
 432 But you can describe how to do that job to another person
 433
 434 In other words, you can treat the instructions as the input to another machine
 435
 436 A *universal* Turing machine can take the description of any Turing machine and produce the same output
 437
 438 * Instruction = input
 439 * Program = data
 440
 441 *This* shows that computing as we know it is possible.
 442
 443 * Programming
 444 * Abstraction
 445 * Virtual machines
 446 * ...
 447
 448
 449
 450
 451     </textarea>
 452     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 453     </script>
 454
 455     <script type="text/javascript"
 456       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 457
 458     <script type="text/javascript">
 459       var slideshow = remark.create({ ratio: "16:9" });
 460
 461       // Setup MathJax
 462       MathJax.Hub.Config({
 463         tex2jax: {
 464         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 465         }
 466       });
 467       MathJax.Hub.Queue(function() {
 468         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 469             return(elem.SourceElement());
 470         }).parent().addClass('has-jax');
 471       });
 472       MathJax.Hub.Configured();
 473     </script>
 474   </body>
 475 </html>