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
680
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
2
170
Strategies for saying no
aemeredith
1
150
Start your own apprenticeship program
aemeredith
0
240
Story-telling with Git rebase
aemeredith
1
1.5k
Feedback matters
aemeredith
0
370
Two heads are better than one
aemeredith
2
1.6k
Feedback Matters
aemeredith
0
380
How I Learn
aemeredith
0
490
Just in time RailsIsrael
aemeredith
1
200
Other Decks in Programming
See All in Programming
Cloudflare AgentsとAI SDKでAIエージェントを作ってみた
briete
0
120
「ちょっと古いから」って避けてた技術書、今だからこそ読もう
mottyzzz
1
160
Conquering Massive Traffic Spikes in Ruby Applications with Pitchfork
riseshia
0
150
LLMとPlaywright/reg-suitを活用した jQueryリファクタリングの実際
kinocoboy2
4
670
なぜあの開発者はDevRelに伴走し続けるのか / Why Does That Developer Keep Running Alongside DevRel?
nrslib
3
370
CSC509 Lecture 03
javiergs
PRO
0
330
ソフトウェア設計の実践的な考え方
masuda220
PRO
3
490
CSC509 Lecture 05
javiergs
PRO
0
300
Goで実践するドメイン駆動開発 AIと歩み始めた新規プロダクト開発の現在地
imkaoru
4
680
AIエージェント時代における TypeScriptスキーマ駆動開発の新たな役割
bicstone
4
1.5k
あなたの知らない「動画広告」の世界 - iOSDC Japan 2025
ukitaka
0
400
Swift Concurrency - 状態監視の罠
objectiveaudio
2
470
Featured
See All Featured
Making Projects Easy
brettharned
119
6.4k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
36
2.5k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
17k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
52
5.6k
The Power of CSS Pseudo Elements
geoffreycrofte
79
6k
Building Flexible Design Systems
yeseniaperezcruz
329
39k
How STYLIGHT went responsive
nonsquared
100
5.8k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
358
30k
Typedesign – Prime Four
hannesfritz
42
2.8k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Testing 201, or: Great Expectations
jmmastey
45
7.7k
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