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 # Dealing with complex problems: some terms to know
 284
 285 (M269 Unit 5)
 286
 287 ## Divide and Conquer
 288
 289 * Split a problem into smaller parts
 290 * Solve them
 291 * Combine the sub-solutions
 292 * Often leads to logarithmic growth
 293
 294 "Guess the number" game
 295     * What if I don't tell you the upper limit?
 296
 297 ## Dynamic programming
 298
 299 Build a soluion bottom-up from subparts
 300
 301 ## Heuristics
 302
 303 * Posh word for "guess"
 304 * Greedy algorithms
 305 * Backtracking
 306 ---
 307
 308 # Sorting with cards
 309
 310 Classroom activity?
 311
 312 ---
 313
 314 # Algorithmic games
 315
 316 ## Travelling Salesman Problem
 317
 318 Online: http://www.math.uwaterloo.ca/tsp/games/tspOnePlayer.html
 319
 320 * But many implementations are Java applets, now a problem with security settings
 321
 322 Try Android/iOS apps?
 323
 324 ## Change-finding problem
 325
 326 Same as the Knapsack problem: M269 Unit 5 Section 3.2, especially Activity 5.9
 327
 328 Dynamic programming to find solution
 329
 330 ## Ticket to Ride boardgame
 331
 332 ---
 333
 334 # Turing and computability
 335
 336 (Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/))
 337
 338 ## The Entscheidungsproblem (Decision problem)
 339
 340 Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms?
 341
 342 The rules could be described to a human computer.
 343
 344 The computer would either answer "Yes," "No," or never stop working.
 345
 346 This is the Halting problem.
 347
 348 ---
 349
 350 # Universal Turing machine
 351
 352 .float-right[![A computer](human-computer-worksheet.png)]
 353
 354 A Turing machine does one particular job
 355
 356 But you can describe how to do that job to another person
 357
 358 In other words, you can treat the instructions as the input to another machine
 359
 360 A *universal* Turing machine can take the description of any Turing machine and produce the same output
 361
 362 * Instruction = input
 363 * Program = data
 364
 365 *This* shows that computing as we know it is possible.
 366
 367 * Programming
 368 * Abstraction
 369 * Virtual machines
 370 * ...
 371
 372
 373
 374
 375     </textarea>
 376     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 377     </script>
 378
 379     <script type="text/javascript"
 380       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 381
 382     <script type="text/javascript">
 383       var slideshow = remark.create({ ratio: "16:9" });
 384
 385       // Setup MathJax
 386       MathJax.Hub.Config({
 387         tex2jax: {
 388         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 389         }
 390       });
 391       MathJax.Hub.Queue(function() {
 392         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 393             return(elem.SourceElement());
 394         }).parent().addClass('has-jax');
 395       });
 396       MathJax.Hub.Configured();
 397     </script>
 398   </body>
 399 </html>