Algorithms to live by and why should we care

Presented at Full Stack Toronto Conference

Transcript

1. Algorithms to live by Elle Meredith @aemeredith
2. Algorithms 1 2 3a 3b = Step by step instructions
3. https://www.instagram.com/p/BaesTAPFaEK2_n5QA06hO7w3Nwd1iaoCS0KIL40/
6. Algorithm Detailed
7. Algorithm Detailed Efficiency Perfection
8. https://imgur.com/Xz3Z2iL
9. In everyday life • Learnt • Figure out ourselves • Require written instructions
10. A precise, systematic method for producing a specified result Definition
11. Why?
12. Suppose we want to search for a word in the dictionary Binary Search
13. 1 2 3 4 100 …
14. 1 2 3 4 100 … X Too low
15. 1 2 3 4 100 … XX Too low
16. 1 2 3 4 100 … XXX Too low
17. 1 2 3 4 100 … XXXX Too low
18. These are all too low 1 50 100 Too low
19. Eliminated 25 more 75 51 100 Too high
20. And we eliminated some more 51 63 74 Too low
21. 7 STEPS 100 50 25 13 7 4 2 1
22. 10 STEPS 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
23. 17 STEPS 100,000 -> 50,000 -> 25,000 -> 12,500 -> 6,300 -> 3,150 -> 1,575 -> 788 -> 394 -> 197 -> 99 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1
24. 22 = 4 23 = 8 24 = 16 25 = 32 26 = 64
25. 22 = 4 23 = 8 24 = 16 25 = 32 26 = 64 log2 4 = 2 log2 8 = 3 log2 100 => 6.643 log2 100000 => 16.609
26. * Binary search only works when our list is sorted
27. Searching for a new place to live… Optimal stopping
28. or finding a significant other
29. The secretary problem
30. https://giphy.com/gifs/scooby-doo-wfOe7SdZ3XyHm
31. http://gph.is/15twRiZ
32. 37%
33. * When we don’t know all the options, optimal stopping tells us when to stop and make a decision
34. Digging at grandma’s attic Recursion
36. box box container box
37. Make a pile of boxes while the pile is not empty Grab a box if you find a box, add it to the pile of boxes Go back to the pile if you find a diary, you’re done!
38. Go through each item in the box if you find a box… if you find a diary, you’re done!
40. def factorial(x) if x == 1 1 else x * factorial(x-1) end end
41. def factorial(x) if x == 1 1 else x * factorial(x-1) end end
42. def factorial(x) if x == 1 1 else x * factorial(x-1) end end
43. factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1
44. factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 4 * 3 * 2 * 1 = 24
45. * Recursion can be applied whenever a problem can be solved by dividing it into smaller problems
46. * … and needs a recursion case and a base case
47. Sorting a book shelf Sorting
48. Bubble sort https://giphy.com/gifs/foxhomeent-book-books-3o7btW1Js39uJ23LAA
49. Insertion sort https://giphy.com/gifs/atcqQ5PuX41J6
50. https://imgur.com/Xz3Z2iL Merge sort
51. empty array array with one element No need to sort these arrays 33 Quicksort
52. check if first element is small than the second one, and if it isn’t => switch 4 2
53. pivot 5 2 4 1 3 3
54. 3 2 1 5 4
55. 3 2 1 5 4 qsort( ) qsort( )
56. 3 2 1 5 4 + + 3 2 1 5 4
57. * Should we be sorting at all? https://people.ucsc.edu/~swhittak/papers/chi2011_refinding_email_camera_ready.pdf
58. Getting things done Single machine scheduling
59. There’s nothing so fatiguing as the eternal hanging on of an uncompleted task William James
60. Make goals explicit
61. Strategy: earliest due date
62. https://giphy.com/gifs/nickelodeon-animation-nick-nicktoons-3o7TKTc8NHnZrVFlFm
63. Strategy: Moore’s algorithm
64. http://gifsgallery.com/watermelon+animated+gif?image=323981005
65. Strategy: shortest processing time
66. Client 1: 4 days task Client 2: 1 day task = 5 days of work
67. Client 1: 4 days task = 4 days waiting Client 2: 1 day task = 5 days waiting = 9 days of waiting
68. Client 2: 1 day task = 1 days waiting Client 1: 4 days task = 5 days waiting = 6 days of waiting
69. Shortest processing time Client 2: 1 day task = 1 days waiting Client 1: 4 days task = 5 days waiting = 6 days of waiting Metric: sum of completion times
70. Suppose we want to find a magician Breadth first search
71. Node Node Edge
72. Elle Hannah Caleb Lachlan Keith Schneem Michelle
73. Elle Hannah Caleb Lachlan Keith Schneem Michelle
74. https://vimeo.com/90177460
75. Elle Hannah Caleb Lachlan Keith Schneem Michelle
76. Elle Hannah Caleb Lachlan Keith Schneem Michelle
77. graph = { "elle"=>["hannah", "caleb", "lachlan"], "hannah"=>["michelle", "schneem"], "caleb"=>["schneem"], "lachlan"=>["keith"], "michelle"=>[], "schneem"=>[], "keith"=>[] }
78. graph = { "elle"=>["hannah", "caleb", "lachlan"], "hannah"=>["michelle", "schneem"], "caleb"=>["schneem"], "lachlan"=>["keith"], "michelle"=>[], "schneem"=>[], "keith"=>[] }
79. * Breadth first search works only we search in the same order in which the people (nodes) were added
80. Travelling salesperson
81. Melbourne Geelong Ballarat Frankston Kew Eltham Epping
82. Melbourne Geelong Ballarat Frankston Kew Eltham Epping
83. Melbourne Geelong Ballarat Frankston Kew Eltham Epping
84. * Just relax! by relaxing the constraints, we make it easier to find solutions
85. Building a recommendation system K nearest neighbours
86. A (2,1) B (1,3) C (5,5)
87. A (2,1) B (1,3) X Y (X1 -X2 )2 + (Y1 -Y2 )2 Distance between A to B C (5,5)
88. (1-3)2 + (2- 1)2 A (2,1) C (5,5) B (1,3) X Y Distance between A to B
89. (1-3)2 + (2- 1)2 A (2,1) C (5,5) B (1,3) X Y 22 + 12 Distance between A to B
90. (1-3)2 + (2- 1)2 A (2,1) C (5,5) B (1,3) X Y 22 + 12 4 + 1 K = 2.236 Distance between A to B
91. (5-3)2 + (5- 1)2 A (2,1) C (5,5) B (1,3) X Y Distance between C to B
92. A (2,1) C (5,5) B (1,3) X Y 22 + 42 Distance between C to B (5-3)2 + (5- 1)2
93. A (2,1) C (5,5) B (1,3) X Y 22 + 42 Distance between C to B (5-3)2 + (5- 1)2 4 + 16 K = 4. 472
94. Comedy Action Drama Horror Romance 4 4 5 1 1 5 5 3 2 1 2 1 5 3 5
95. hannah => (4, 4, 5, 1, 1) caleb => (5, 5, 3, 2, 1) lachlan => (2, 1, 5, 3, 5)
96. (4-5)2 + (4-5)2 + (5-3)2 + (1-2)2 + (1- 1)2 hannah => (4, 4, 5, 1, 1) caleb => (5, 5, 3, 2, 1)
97. 1 + 1 + 4 + 1 + 0 7 K = 2.64
98. (4-2)2 + (4- 1)2 + (5-5)2 + (1-3)2 + (1-5)2 hannah => (4, 4, 5, 1, 1) lachlan => (2, 1, 5, 3, 5)
99. 4 + 9 + 0 + 4 + 16 33 K = 5.74
100. * K-Nearest Neighbours uses feature extraction, which means converting an item into a list of numbers that can be compared
101. Thinking less Overfitting
102. https://www.zmescience.com/other/charles-darwin-marry-or-not/ It being proved necessary to marry
103. The case against complexity
104. If you can’t explain it simply, you don’t understand it well enough. Anonymous
105. Strategies • Regularisation
106. Strategies • Regularisation • Add weight to points
107. Strategies • Regularisation • Add weight to points • Early stopping
108. Strategies • Regularisation • Add weight to points • Early stopping • Stay clear from finer details
109. It is intolerable to think of spending one’s whole life like a neuter bee, working, working, and nothing after all. Charles Darwin
110. When algorithms go wrong https://www.bloomberg.com/view/articles/2017-04-18/united-airlines-exposes-our-twisted-idea-of-dignity
111. https://en.wikipedia.org/wiki/United_Express_Flight_3411_incident
112. Every algorithm reflects the subjective choices of its human designer Cathy O’Neil
113. Elle Meredith @aemeredith