# Algorithms ## What's all the fuss about? --- layout: true .indexlink[[Index](index.html)] --- # What is an algorithm? What is a computer? Back when computers were human... * Instructions * (Small) working memory * As much notepaper as you wanted * Input → output ## Turing machines Simplified human computer. * (Instructions + memory) → Finite number of states * (States similar to places on a flowchart) * Notepaper → tape (with limited symbols) Algorithm is the instructions (See TU100 Block 2 Part 1, M269 Unit 2) --- # Sequence, selection, repetition Repetition == iteration or recursion --- # Growth rates ![left-aligned Growth rates ](big-o-chart-smaller.png) .float-right[![right-aligned Growth rates ](big-o-chart-2-smaller.png)] `\(f(n) \text{ is } O(g(n)) \quad\text{ if }\quad |f(n)| \le \; M |g(n)|\text{ for all }n \ge N\)` --- # Complexity classes we care about * Exponential or bigger (2
*n*
, *e*
*n*
, or *n*!) * Polynomial (*n*
*k*
) * Linear (*n*) * Sub-linear (log *n*) Generally: * polynomial or smaller is considered tractable * anything exponential or larger is intractable (Exceptions exist in practice.) --- # Anagrams version 1: checking off ``` Given word1, 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? ``` Nested loops: complexity is *O*(*n*₁ × *n*₂), or *O*(*n*²). -- Can anyone see the bug? -- word1 = "cat", word2 = "catty" --- # Anagrams version 1a: checking off (fixed) ``` Given word1, word2 anagram? = True for character in word1: for pointer in range(len(word2)): if character == word2[pointer]: word2[pointer] = None else: anagram? = False for pointer in range(len(word2)): if word2[pointer] != None: anagram? = False return anagram? ``` --- # Anagrams version 2: sort and comapre ``` Given word1, word2 return sorted(word1) == sorted(word2) ``` What's the complexity of `sorted`? What's the complexity of `==`? --- # Anagrams version 2a: sort and comapre ``` Given word1, word2 sorted_word1 = sorted(word1) sorted_word2 = sorted(word2) anagram? = True for i in range(len(sorted_word1)): if sorted_word1[i] != sorted_word2[i]: anagram? = False return anagram? ``` One `for` in the comparison, so its complexity is *O*(*n*). (`len` is also *O*(*n*)) What's the complexity of `sorted`? --- # Anagrams version 2a': sort and comapre, idiomatic ``` Given word1, word2 sorted_word1 = sorted(word1) sorted_word2 = sorted(word2) anagram? = True for l1, l2 in zip_longest(sorted_word1, sorted_word2): if l1 != l2: anagram? = False return anagram? ``` `zip_longest` is lazy, so still *O*(*n*). (Can't use `zip` as it truncates the longest iterable, giving the same bug as number 1) Still dominated by the *O*(*n* log *n*) of `sorted`. --- # Anagrams version 3: permutations ``` Given word1, word2 anagram? = False for w in permutations(word1): w == word2: anagram? = True return anagram? ``` (Code for `permutations` is complex.) How many permutations are there? --- # Anagrams version 4: counters ``` Given word1, word2 counts1 = [0] * 26 counts2 = [0] * 26 for c in word1: counts1[num_of(c)] += 1 for c in word2: counts2[num_of(c)] += 1 anagram? = True for i in range(26): if counts1[i] != counts2[1]: anagram = False return anagram? ``` Three `for`s, but they're not nested. Complexity is *O*(*n*₁ + *n*₂ + 26) or *O*(*n*). `dict`s seem a natural way of representing the count. What do you need to be careful of? (Alternative: maintain a single list of differences in letter counts. Initialise to all zero, should be all zero when you've finished.) Notice: trading space for time. --- # Finding all anagrams Given a `wordlist` and a `word`, find all anagrams of `word` in `wordlist`. * How does your answer change if you know you need to do this just once, or millions of times? # Anagrams of phrases 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) ## Divide and Conquer * Split a problem into smaller parts * Solve them * Combine the sub-solutions * Often leads to logarithmic growth "Guess the number" game * What if I don't tell you the upper limit? ## Dynamic programming Build a soluion bottom-up from subparts --- # Heuristics * Posh word for "guess" * Greedy algorithms * Backtracking --- # Making change 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) | (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, 2, 0) | (0, 0, 1) | (0, 0, 0) | (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) | (0, 0, 0) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ... --- # Algorithmic games ## Travelling Salesman Problem .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? ## Ticket to Ride boardgame Graph algorithms * Find shortest path --- # Turing and computability (Following [Craig Kaplan's description of the Halting Problem](http://www.cgl.uwaterloo.ca/~csk/halt/)) ## The Entscheidungsproblem (Decision problem) Given some axioms, rules of deduction, and a statement (input), can you prove whether the statement follows from the axioms? The rules could be described to a human computer. The computer would either answer "Yes," "No," or never stop working. This is the Halting problem. --- # Universal Turing machine .float-right[![A computer](human-computer-worksheet.png)] A Turing machine does one particular job But you can describe how to do that job to another person In other words, you can treat the instructions as the input to another machine A *universal* Turing machine can take the description of any Turing machine and produce the same output * Instruction = input * Program = data *This* shows that computing as we know it is possible.