Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Algorithms to live by and why should we care
Search
Elle Meredith
October 23, 2017
Programming
0
660
Algorithms to live by and why should we care
Presented at Full Stack Toronto Conference
Elle Meredith
October 23, 2017
Tweet
Share
More Decks by Elle Meredith
See All by Elle Meredith
Exploring anti-patterns in Rails
aemeredith
1
160
Strategies for saying no
aemeredith
1
150
Start your own apprenticeship program
aemeredith
0
230
Story-telling with Git rebase
aemeredith
1
1.4k
Feedback matters
aemeredith
0
360
Two heads are better than one
aemeredith
2
1.5k
Feedback Matters
aemeredith
0
370
How I Learn
aemeredith
0
470
Just in time RailsIsrael
aemeredith
1
200
Other Decks in Programming
See All in Programming
Flutterで備える!Accessibility Nutrition Labels完全ガイド
yuukiw00w
0
100
Google Agent Development Kit でLINE Botを作ってみた
ymd65536
2
210
すべてのコンテキストを、 ユーザー価値に変える
applism118
2
960
Goで作る、開発・CI環境
sin392
0
170
What Spring Developers Should Know About Jakarta EE
ivargrimstad
0
330
Deep Dive into ~/.claude/projects
hiragram
10
2k
第9回 情シス転職ミートアップ 株式会社IVRy(アイブリー)の紹介
ivry_presentationmaterials
1
250
PHPで始める振る舞い駆動開発(Behaviour-Driven Development)
ohmori_yusuke
2
230
なんとなくわかった気になるブロックテーマ入門/contents.nagoya 2025 6.28
chiilog
1
240
プロダクト志向なエンジニアがもう一歩先の価値を目指すために意識したこと
nealle
0
110
ruby.wasmで多人数リアルタイム通信ゲームを作ろう
lnit
2
300
技術同人誌をMCP Serverにしてみた
74th
1
450
Featured
See All Featured
How to train your dragon (web standard)
notwaldorf
94
6.1k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Become a Pro
speakerdeck
PRO
28
5.4k
Scaling GitHub
holman
459
140k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
800
Raft: Consensus for Rubyists
vanstee
140
7k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
710
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Unsuck your backbone
ammeep
671
58k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Transcript
Algorithms to live by Elle Meredith @aemeredith
Algorithms 1 2 3a 3b = Step by step instructions
https://www.instagram.com/p/BaesTAPFaEK2_n5QA06hO7w3Nwd1iaoCS0KIL40/
None
None
Algorithm Detailed
Algorithm Detailed Efficiency Perfection
https://imgur.com/Xz3Z2iL
In everyday life • Learnt • Figure out ourselves •
Require written instructions
A precise, systematic method for producing a specified result Definition
Why?
Suppose we want to search for a word in the
dictionary Binary Search
1 2 3 4 100 …
1 2 3 4 100 … X Too low
1 2 3 4 100 … XX Too low
1 2 3 4 100 … XXX Too low
1 2 3 4 100 … XXXX Too low
These are all too low 1 50 100 Too low
Eliminated 25 more 75 51 100 Too high
And we eliminated some more 51 63 74 Too low
7 STEPS 100 50 25 13 7 4 2 1
10 STEPS 1000 -> 500 -> 250 -> 125 ->
63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
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
22 = 4 23 = 8 24 = 16 25
= 32 26 = 64
22 = 4 23 = 8 24 = 16 25
= 32 26 = 64 log2 4 = 2 log2 8 = 3 log2 100 => 6.643 log2 100000 => 16.609
* Binary search only works when our list is sorted
Searching for a new place to live… Optimal stopping
or finding a significant other
The secretary problem
https://giphy.com/gifs/scooby-doo-wfOe7SdZ3XyHm
http://gph.is/15twRiZ
37%
* When we don’t know all the options, optimal stopping
tells us when to stop and make a decision
Digging at grandma’s attic Recursion
None
box box container box
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!
Go through each item in the box if you find
a box… if you find a diary, you’re done!
None
def factorial(x) if x == 1 1 else x *
factorial(x-1) end end
def factorial(x) if x == 1 1 else x *
factorial(x-1) end end
def factorial(x) if x == 1 1 else x *
factorial(x-1) end end
factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1) factorial(1) = 1
factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1) factorial(1) = 1 4 * 3 * 2 * 1 = 24
* Recursion can be applied whenever a problem can be
solved by dividing it into smaller problems
* … and needs a recursion case and a base
case
Sorting a book shelf Sorting
Bubble sort https://giphy.com/gifs/foxhomeent-book-books-3o7btW1Js39uJ23LAA
Insertion sort https://giphy.com/gifs/atcqQ5PuX41J6
https://imgur.com/Xz3Z2iL Merge sort
empty array array with one element No need to sort
these arrays 33 Quicksort
check if first element is small than the second one,
and if it isn’t => switch 4 2
pivot 5 2 4 1 3 3
3 2 1 5 4
3 2 1 5 4 qsort( ) qsort( )
3 2 1 5 4 + + 3 2 1
5 4
* Should we be sorting at all? https://people.ucsc.edu/~swhittak/papers/chi2011_refinding_email_camera_ready.pdf
Getting things done Single machine scheduling
There’s nothing so fatiguing as the eternal hanging on of
an uncompleted task William James
Make goals explicit
Strategy: earliest due date
https://giphy.com/gifs/nickelodeon-animation-nick-nicktoons-3o7TKTc8NHnZrVFlFm
Strategy: Moore’s algorithm
http://gifsgallery.com/watermelon+animated+gif?image=323981005
Strategy: shortest processing time
Client 1: 4 days task Client 2: 1 day task
= 5 days of work
Client 1: 4 days task = 4 days waiting Client
2: 1 day task = 5 days waiting = 9 days of waiting
Client 2: 1 day task = 1 days waiting Client
1: 4 days task = 5 days waiting = 6 days of waiting
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
Suppose we want to find a magician Breadth first search
Node Node Edge
Elle Hannah Caleb Lachlan Keith Schneem Michelle
Elle Hannah Caleb Lachlan Keith Schneem Michelle
https://vimeo.com/90177460
Elle Hannah Caleb Lachlan Keith Schneem Michelle
Elle Hannah Caleb Lachlan Keith Schneem Michelle
graph = { "elle"=>["hannah", "caleb", "lachlan"], "hannah"=>["michelle", "schneem"], "caleb"=>["schneem"], "lachlan"=>["keith"],
"michelle"=>[], "schneem"=>[], "keith"=>[] }
graph = { "elle"=>["hannah", "caleb", "lachlan"], "hannah"=>["michelle", "schneem"], "caleb"=>["schneem"], "lachlan"=>["keith"],
"michelle"=>[], "schneem"=>[], "keith"=>[] }
* Breadth first search works only we search in the
same order in which the people (nodes) were added
Travelling salesperson
Melbourne Geelong Ballarat Frankston Kew Eltham Epping
Melbourne Geelong Ballarat Frankston Kew Eltham Epping
Melbourne Geelong Ballarat Frankston Kew Eltham Epping
* Just relax! by relaxing the constraints, we make it
easier to find solutions
Building a recommendation system K nearest neighbours
A (2,1) B (1,3) C (5,5)
A (2,1) B (1,3) X Y (X1 -X2 )2 +
(Y1 -Y2 )2 Distance between A to B C (5,5)
(1-3)2 + (2- 1)2 A (2,1) C (5,5) B (1,3)
X Y Distance between A to B
(1-3)2 + (2- 1)2 A (2,1) C (5,5) B (1,3)
X Y 22 + 12 Distance between A to B
(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
(5-3)2 + (5- 1)2 A (2,1) C (5,5) B (1,3)
X Y Distance between C to B
A (2,1) C (5,5) B (1,3) X Y 22 +
42 Distance between C to B (5-3)2 + (5- 1)2
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
Comedy Action Drama Horror Romance 4 4 5 1 1
5 5 3 2 1 2 1 5 3 5
hannah => (4, 4, 5, 1, 1) caleb => (5,
5, 3, 2, 1) lachlan => (2, 1, 5, 3, 5)
(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)
1 + 1 + 4 + 1 + 0 7
K = 2.64
(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)
4 + 9 + 0 + 4 + 16 33
K = 5.74
* K-Nearest Neighbours uses feature extraction, which means converting an
item into a list of numbers that can be compared
Thinking less Overfitting
https://www.zmescience.com/other/charles-darwin-marry-or-not/ It being proved necessary to marry
The case against complexity
If you can’t explain it simply, you don’t understand it
well enough. Anonymous
Strategies • Regularisation
Strategies • Regularisation • Add weight to points
Strategies • Regularisation • Add weight to points • Early
stopping
Strategies • Regularisation • Add weight to points • Early
stopping • Stay clear from finer details
It is intolerable to think of spending one’s whole life
like a neuter bee, working, working, and nothing after all. Charles Darwin
When algorithms go wrong https://www.bloomberg.com/view/articles/2017-04-18/united-airlines-exposes-our-twisted-idea-of-dignity
https://en.wikipedia.org/wiki/United_Express_Flight_3411_incident
Every algorithm reflects the subjective choices of its human designer
Cathy O’Neil
Elle Meredith @aemeredith