This page is a work in progress.You can help improve it. →

theme: Huerta, 5

# [fit] Algorithms, not Al Gore's Rhythm # Algorithms

Like any good presentation, let us give the boring definition.

# Definition (1/3)

``Self-contained step-by-stepset of operations to beperformed.``

# Definition (2/3)

``Algorithms perform calculations,data processing, and/orautomated reasoning tasks.``

# Definition (3/3)

``An algorithm is an effectivemethod that can be expressedwithin a finite amount ofspace and time and in awell-defined formal languagefor calculating a function.`` ^ WHAAAAAT?

# [fit] Examples

^ Giving specific directions to someone on how to drive from place to place

^ Going to come back to directions later.

#### http://bit.ly/1tsqopI

^ Followed, created or modified a recipe for cooking

#### http://bit.ly/1Pp7bZY

^ "Place Tab A into Slot B"

^ Draw two circles

^ Draw the rest of the damn owl

# [fit] More formal

^ These are casual examples of algorithms we use or create all the time

^ Time to bring back that horror of high school math: Geometry

^ Formal construction for bisecting the angle

# [fit] Euclid's Algorithm for Computing the Greatest Common Divisor (GCD)

[.column]

``English: Given two numbers, A and B,what is the largest number thatevenly divides **both** numbers``

[.column]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 210, B = 45`

[.column]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 210, B = 45`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 210, B = 45`
`A > B (210 > 45)`

[.column]

[.code-highlight: 3]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

[.code-highlight: 4]

`A = 210, B = 45`
`A > B (210 > 45)`
`A = 210 - 45`
`A = 165`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 165, B = 45`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 165, B = 45`
`A > B (165 > 45)`

[.column]

[.code-highlight: 3]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 165, B = 45`
`A > B (165 > 45)`
`A = 165 - 45`
`A = 120`

[.column]

[.code-highlight: 4]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 120, B = 45`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 120, B = 45`
`A > B (120 > 45)`

[.column]

[.code-highlight: 3]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 120, B = 45`
`A > B (120 > 45)`
`A = 120 - 45`
`A = 75`

[.column]

[.code-highlight: 4]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 75, B = 45`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 75, B = 45`
`A > B (75 > 45)`

[.column]

[.code-highlight: 3]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 75, B = 45`
`A > B (75 > 45)`
`A = 75 - 45`
`A = 30`

[.column]

[.code-highlight: 4]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 45`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 45`
`else ... since it isn't true that (30 > 45)`
`B = 45 - 30`
`B = 15`

[.column]

[.code-highlight: 3, 5]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 45`
`else ... since it isn't true that (30 > 45)`
`B = 45 - 30`
`B = 15`

[.column]

[.code-highlight: 6]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 15`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 15`
`A > B (30 > 15)`

[.column]

[.code-highlight: 3]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 30, B = 15`
`A > B (30 > 15)`
`A = 30 - 15`
`A = 15`

[.column]

[.code-highlight: 4]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 15, B = 15`

[.column]

[.code-highlight: 1]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# Euclid's Algorithm for GCD

[.column]

`A = 15, B = 15`
`done with *while*`
`since A == B`
`GCD = 15`

[.column]

[.code-highlight: 10]

``while (A != B) { if (A > B)   A = A - B else   B = B - A}return A``

# [fit] "Make a PB&J Sandwich."

Example video of a family practicing this.

^ Give a couple of example tries

^ Show that nearly every step we think is precise could be more precise

^ Suggest people try at home

# [fit] This is the :key: to mastering programming

^ When starting with algorithms, the more detail we include, even to the point where it may seem silly, the better developers we will be.

``1. Read the problem completely twice.2. Solve the problem manually with several sets of sample data.3. Optimize the manual steps.4. Write the manual steps as comments or pseudo-code.5. Replace the comments or pseudo-code with real code.6. Optimize the real code.``

# Read the problem completely twice.

``- Most important!- Can you explain it (simply) to someone else?``

# Solve the problem manually

``- Programming is automation- Solve the problem manually- Maybe even on pen and paper- Or use physical objects- Practice!``

# Optimize the manual solution

``- Can you remove any steps?``

``- Open an editor and write the manual steps in English``

# Replace comments with real code

``- Replace each individual step with code``

# PEDAC

• Created by `Launch School`
• Generalized process for creating algorithms:
• P　 roblem
• E　 xamples
• D　 ata (structures)
• A　 lgorithm
• C　 ode

# Example

## [fit] Reverse a string (word)

^ Our goal is to be able to reverse any string (word) ^ How would we break this down into tiny steps

# `P`roblem

Given a word, which is just a sequence of letters, make a new word with the same sequence of letters in reverse order.

# `E`xamples

zebraarbez
worddrow
rotatorrotator

^ `File.read("/usr/share/dict/words").split("\n").filter { |word| word.reverse == word }.sort_by(&:length)`

# `D`ata (structures)

• `string`
• loops

# `A` lgorithm ...

Start by using a specific example...

``1. Write “Zebra” down.2. Create a new empty word.2. Start at the last letter in the word (the "a" from Zebra)3. Put the current letter at the end of the new word4. If there is a previous letter,   make the previous letter the current letter   and start back at 3.5. When there are no more letters in the word, our   new word is the answer.``

# Pseudo code

``1. NewWord = ""2. Loop backwards through word to reverse3.   NewWord += CurrentLetter4. Return NewWord``

# Code (Ruby)

``word = "Zebra"new_word = ""word.chars.reverse_each do |letter|  new_word += letterendnew_word # => "arbeZ"``

# Bubble sort

Exchange them if out of order

Repeat until the array is sorted.

# Break it down

``1. Assume the array is sorted2. Go through each pair of elements   - If the first of the pair is larger than the second of the pair     - Swap the two elements     - Remember that the array isn't sorted3. When done with all the elements, if we   still believe the array is sorted, STOP4. Otherwise, go back to step 1``

^ explain ... in range

^ explain each_cons

``array = [7,1,2,9,4,5]def bubble_sort(array)  loop do    # Assume the list is sorted    sorted = true    # Go through the indexes of the array in pairs    (0...array.length).each_cons(2) do |first, second|      # if the first is larger      if array[first] > array[second]        # Swap        array[first], array[second] = array[second], array[first]        # Remember array isn't sorted        sorted = false      end    end    # If array is sorted, stop    break if sorted    # end of loop/do go back to the first step  endend`` ^ Moment of zen

# [fit] Algorithm Complexity

^ How do we know how "good" our algorithm is?

# [fit] Measuring Time and Space # Measure

timethe number of operations required
spacethe amount of memory required

Best caseIf the data is perfect for this algorithm, how fast are we?
Worst caseIf the data is terrible for this algorithm, how slow are we?
Average caseConsidering all possible inputs, what is the average speed of the algorithm

# What are we measuring?

When we speak of algorithm complexity, what are we measuring?

• Operations
• Comparisons
• Increments

^ TODO: Maybe mention Turing Machine here?

# Example: Searching ^ Binary search: we half the amount of comparisons we need to do each time we make a decision. This is worst case log(n)

^ The linear search has to compare every element until it finds it. Worst case is O(n)

# [fit] Big O notation

`O(1)`

`O(log n)`

`O(n)`

`O(n log n)`

`O(n^2)`

`O(2^n)`

• These grow at a different rate based on how `n` changes

`O(1)`

``Takes a constant amount of time regardless of input sizeExample: looking up an index in an array         looking up a key in a hash/dictionary (most cases)``

`O(n)`

``If n doubles, the algorithm takes twice as longExample: linear search animation``

`O(n^2)`

``If n doubles, the algorithm takes FOUR times as longExample: bubble sort!``

`O(2^n)`

``If n doubles, the algorithm takes many times as longe.g., if n grows from 20 to 40, O(2^n) grows by over a MILLION timesExample: Tower of Hanoi``

# Tower of Hanoi

``The Tower of Hanoi is a mathematical game or puzzle.It consists of three rods and several disksof different sizes, which can slide onto any rod.The puzzle starts with the disks in a neat stackin ascending order of size on one rod, the smallestat the top, thus making a conical shape.``

# Tower of Hanoi

``The objective of the puzzle is to move the entirestack to another rod, obeying simple rules``

# Tower of Hanoi

``1. Only one disk can be moved at a time.2. Each move consists of taking the upper disk   from one of the stacks and placing it on top   of another stack i.e. a disk can only be   moved if it is the uppermost disk on a stack.3. No disk may be placed on top of a smaller disk.``

# [fit] Tower of Hanoi Recursively

``Move all but the bottom disk to the"spare" peg (using this exact algorithm)Move the bottom disk to the "destination"peg (this is a simple move)Move all the disks from the "spare" peg tothe "destination" peg (using this exactalgorithm)``

# If we could move a disk per second how long would this take?

DisksTime
1a second
84 minutes
171 day and a half

DisksTime

DisksTime

DisksTime

DisksTime
35... over 1,089 yearsAbout a millennium

DisksTime
5035.7 million years:scream:

DisksTime
59More than 13 billion yearsEstimated age of the universe

# [fit] Complexity

## Salesperson

^ Imagine you are a traveling salesperson.

^ What is the best route for the salesperson to visit each city only once, returning to the starting city at the end?

# 1 Billion Computations per second

CitiesTime
2less than a minute
3less than a minute
4less than a minute
141 minute

# 1 Billion Computations per second

CitiesTime
182 months
19almost 4 years ^ Upwards of 400,000 iterations for about 50 cities

# The TSP has several applications

``planninglogisticsmanufacturing of microchipsDNA sequencing``

# [fit] Wrap It Up ^ Let's wrap this up

# Being a Developer

``1. Understanding the problem2. Break it down into small steps3. Break it into even smaller steps4. Translate this to code5. Appreciate the complexity``

# How to practice?

``exercism.iocodewars.comCoderNight meetup(http://meetup.com/CoderNight)``

# [fit] Questions?

© 2017 - 2021; Built with ♥ in St. Petersburg, Florida.