Algorithms to live by and why should we care

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/

4. None
5. None

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

35. None

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!
39. None

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