Intro to Algorithms

Schedule

10:00 - 1PM     Introduction
                Defining an algorithm
                Data Structures
                Goal of algorithms
                Time/space complexity

1:00 - 2:00     Lunch

2:00 - 5:00     Searching - Linear & Binary
                Sorting
                Algorithms in Real Life
                Conclusion

Table of Contents

What will we be covering in this class?

• What is an algorithm?
• Intro to algorithmic complexity
  (how good is an algorithm)
• Demonstrate sort and search algorithms
  (the classics)

Expectations

• Participation and questions
• Keep coming up with more solutions
• Collaborate with positivity and energy

Not expecting:

• Syntax
• Knowing all the things

Algorithms

"A repeatable process for determining
the solution to a problem."

Algorithms in Daily Life

• Finding a fruit in the grocery store.
• Alphabetizing name tags.
• Re-organizing your kitchen to find things easier.
• Finding keys that you lost.
• Finding something good to watch on TV.

Picking something to watch on TV v1

Picking something to watch on TV v1

1. Turn on TV
2. Watch what is on

Picking something to watch on TV v2

Picking something to watch on TV v2

1. Turn on TV
2. Flip through every channel and rate what is on
3. Find the highest rated channel
4. Watch

Picking something to watch on TV v3

Picking something to watch on TV v3

1. Turn on TV
2. Check 5 favorite channels and rate what is on
3. Find the highest rated channel
4. Watch

Which version is best?

Goal of Algorithms

• Solve a problem
• in a repeatable way

Goal of Whiteboarding Interviews

• Show your thought process
• Solve the most obvious (to you!) solution first
• Talk about the tradeoffs and improve it

Exercise time!

What is an algorithm you use?

Write down steps for several versions of
an algorithm to solve an everyday problem

Data Structures

(Just good to know; we won't be covering extensively!)

A way to store data
so that it can be used as desired

Data Structures + Algorithms

A good way to approach an algorithm is to
think about the data structures that you know.

What are their properties?
How can these be used to your advantage?

Example:

Arrays/List

Example:

Dictionaries/ Objects/ Hash Maps/ Maps

myObject = {
  key : value,
  key : value,
  key : value
}
                
                

Example:

Abstract Data Structures

Linked List

Tree

Graph

Queue

Optimizations

Designing algorithms is about making decisions.

All decisions have tradeoffs.

You may want to optimize to complete the task:

• in the shortest time
• using the least amount of space

Complexity

How do you know if your algorithm is good?

How do you compare algorithms?

• Time Complexity: How long does the algorithm take?
• Space Complexity: How much space does it use?

The less complex the better!

Grocery Shopping

Time Efficient

1. Drive large car to grocery store
2. Buy everything you need

Grocery Shopping

Space Efficient

1. Walk to grocery store with tote bag
2. Buy one item
3. Walk home and drop off the item
4. Repeat until done

Time Complexity

How long does an algorithm take?

Big O Notation

• Language we use to describe an algorithm's complexity
• Approximation of how quickly space or time complexity grows relative to input size
• Usually talking about worst case scenario

Put Away Laundry - v1

Algorithm

1. Dump laundry on floor

Code

laundry.drop()
            

Laundry v1

Runtime

How long does the algorithm take?

Dumping out laundry takes 2 seconds.

N = items of clothing
Time it takes: (N*0 + 2)

Laundry v1

Big O Notation

→ O(2)

→ O(1)

Constant time

Hang Up Laundry - v2

Algorithm

1. Dump laundry on bed.
2. Put each item of clothing into a pile for that type
   ("shirts", "underwear", "socks", etc).
3. Go through each pile and hang up each piece of clothing.

Laundry v2

Code

const piles = { 'shirts': [], 'socks': [], 'pants': [] }

laundry.drop()

for (item in laundry) {
  piles[item.type].push(item)
}

for (pile in piles) {
    for (item in pile) {
        item.hang_up()
    }
}
              

Laundry v2

Runtime

How long does the algorithm take?

Dumping out laundry takes 2 seconds.
Putting an item in a pile takes 10 seconds.
Hanging an item up takes 30 seconds.

N = items of clothing
Time it takes: 2 + (N*10 + N*30)

Laundry v2

Big O Notation

→ O(2 + 40N)

→ O(40N)

→ O(N)

Linear time

Match Clean Outfits - v3

Algorithm

1. Dump laundry on bed.
2. Sort the shirts and pants into two different piles.
3. Make all possible outfit combinations. Let's assume there are an equal amount of pants and shirts.

Laundry v3

Code

pants_pile = ['jeans', 'overalls', 'leggings', ..., 'cutoffs']    // N items
shirts_pile = ['t-shirt', 'blouse', 'crop-top', ..., 'tank']      // N items
outfits = []

laundry.drop()
laundry.sort()

for (shirt in shirts_pile) {
    for (pants in pants_pile) {
        outfits.push([shirt, pants])
    }
}
              

Laundry v3

Runtime

We must match each shirt with each pair of pants.
Dumping out laundry takes 2 seconds.
Putting an item in a pile takes 10 seconds.
Looking at each item takes 2 seconds.

N = # items of clothing
Time it takes: 2 + (N*10) + (N*2)*N

Laundry v3

Big O Notation

→ O(2 + 10N + 2N²)

→ O(10N + 2N²)

→ O(2N²)

→ O(N²)

Quadratic time

Time Complexity

                

                    

                        
Order of growth
                        
Name
                        
Description
                        
Example
                    
                
                

                    

                        
1
                        
constant
                        
statement
                        
add two numbers
                    
                    

                        
logN
                        
logarithmic
                        
divide in half
                        
binary search
                    
                    

                        
N
                        
linear
                        
loop
                        
find the maximum
                    
                    

                        
NlogN
                        
linearithmic
                        
divide + conquer
                        
merge sort
                    
                    

                        
N2
                        
quadratic
                        
double loop
                        
check all pairs
                    
                    

                        
N3
                        
cubic
                        
triple loop
                        
check all triples
                    
                    

                        
2N
                        
exponential
                        
exhaustive search
                        
check all subsets
                    
              

Question Time!

What is the time complexity of...

skipping to the front of a line

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

What is the time complexity of...

waiting in a line

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

What is the time complexity of...

skipping half of a line

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

What is the time complexity of...

looking up an element in an array

var things = ["raindrops", "roses", "whiskers", "kittens"]

console.log(things[2])

                

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

What is the time complexity of...

iterating over an array

var things = ["raindrops", "roses", "whiskers", "kittens"]

for (var i = 0; i < things.length; i++) {
    console.log(things[i])
}
                

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

What is the time complexity of...

making every pair combination of items in array

var things = ["raindrops", "roses", "whiskers", "kittens"]

for (var i = 0; i < things.length; i++) {
    for (var j = i + 1; j < things.length; j++) {
        console.log(things[i] + things[j])
    }
}

// raindrops + roses
// raindrops + whiskers
// raindrops + kittens
// roses + whiskers
// roses + kittens
// whiskers + kittens
                

O(1) - Constant

O(n) - Linear

O(n²) - Quadratic

Space Complexity

Grocery Shopping

Time Efficient

1. Walk to grocery store
2. Put everything in the cart
3. Buy items and walk home

The more items on the list,
the bigger the bag needed.

If N is the number of items on the list, then the bag array needs to be size N.

The space complexity is:

O(N) => linear space

Grocery Shopping

Space Efficient

1. Walk to grocery store
2. Buy first item on list
3. Walk home and drop off the item
4. Repeat until done

So what's more important? Time or space?

Discuss!

Refer back to your algorithm from your exercise

What's the time requirement of your algorithm?

What's the space requirement of your algorithm?

Exercise time!

Making Pancakes

Write two algorithms to make N servings of pancakes,
one that is time efficient and one that is space efficient.

Pseudocode each step first,
then code it if you have time.

Searching Algorithms

A search algorithm is an algorithm which solves the problem of retrieving stored information.

Discuss

How do you solve the problem of
searching data numbering in the billions?

Linear Search

One of the simplest searches.

Find an item with a particular value in a sequence.

Find 'J' in the following sequence:
[4, 5, J, 10, Q, K, A]

J is the 3rd element (index 2).

Linear Search

Exercise

Writing Linear Search

Algorithm Solving Strategies

What did we do to create our linear search algorithm?

• Use iteration to move over a data structure
• Use comparison of values

Binary Search

Find an item by repeatedly halving the search space.

Binary Search:

Visualized

Binary Search: Steps

To find the index of element e with a certain value:

• Start with an array sorted in ascending order.
  
  
• In each step:
  • Pick the middle element of the array m and compare it to e.
  • If element values are equal, then return index of m.
  • If m is greater than e, then e must be in left subarray.
    If m is less than e, then e must be in the right subarray.
  
  
• Repeat those steps on new subarray.

Exercise:

Binary Search Simulation

• Sort your cards by number.
• Now let's find a card with a particular number
  using binary search.

Exercise:

Writing Binary Search

Algorithm Solving Strategies

What did we do to create our binary search algorithm?

• Use variables as 'pointers' to track data in our data structure


• Inside the algorithm, try to make your data set smaller, such that you are comparing smaller sets of data to each other - called the 'base case'

Time/Space Complexity

Binary Search vs Linear Search:

What factors determine time?

N = number of items in sequence.

Since binary search algorithm splits array in half
every time, at most log₂N steps are performed.

Sorting

Sorting

Why so important?

You do it all the time in real life!

• The way your clothes are organized
• Where your dishes are in the kitchen
• Your books on your bookshelf

They're not in perfect order, but in a way
that makes it easier for you to search for things.

Sorting

Many sorting algorithms for many types of data

• I sort my dishes by size and shape, not alphabetically
• I sort my books alphabetically, not by color
• I sort mail in reverse chronological order


• When I sort my yarn, I dump them all over the ground
• When I sort my dishes, I pull them out of the dishwasher one at a time

There are lots of different types of data that
computers need to sort, just like in the real world

Selection Sort

1. Iterate over the unsorted array, keeping track of the minimum value as you go


2. When you get to the end of the array, you know which element is the minimum


3. Swap the minimum element and the first element in the unsorted array


4. The first element is now considered sorted


5. Repeat until the rest of the array is sorted

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

1. Go sequentially through array to find minimum
2. Swap with the first card of the unsorted array
3. Repeat steps 1&2 with remaining unsorted array

Selection Sort Simulation

• Line up randomly.
• Sort by last letter of first name using selection sort.

Selection Sort Code

Selection Sort:

Time Complexity

Selection Sort:

Space Complexity

More Sort Algorithms

All differ in performance, and performance often depends on data characteristics.

• Insertion sort
• Selection sort
• Merge sort
• Bucket sort
• Bubble sort

Wikipedia: Comparison of algorithm performance

Which sort is best?

Great resources to help visualize
the different sorting algorithms:

Insertion Sort

When is it best?

Bucket Sort

When is it best?

Bubble Sort

When is it best?

Merge Sort

When is it best?

• When the characteristics of the dataset are unknown
• When you want to implement a multithreaded solution

Example: Two companies are merging and they each had different ways to calculate their hierarchies. They want to create a new seniority list based on hire dates.

Bogo Sort

When is it best?

• Probably never, but it's fun to learn!


• From Wikipedia: "In computer science, bogosort (also known as permutation sort, stupid sort, slowsort, shotgun sort or monkey sort) is a highly ineffective sorting function based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted."


• Example on Youtube

Algorithms in Real Life

Finding Friends

Write a series of algorithms to suggest friends to Facebook users. Write an MVP algorithm first.

Don't feel like you have to copy what Facebook does; just write an algorithm that gets the job done.

How Does Facebook Recommend Friends?

Not just one algorithm, but many.

• Same workplace or school
• Tagged in a photo together
• People you search for
• People who have searched you
• Number of connections

• Iterate over all of your friends and make a list of all of their friends
• Count which people show up the most that you are not already friends with

How does Amazon recommend stuff?

If you buy something in category A,
recommend EVERYTHING ELSE in category A.

Algorithms are NOT perfect

They reflect the biases of the people who build them and of the society of where they were built

• Amazon decides where to provide same day delivery based on which neighbohoods have the most Prime users. Excludes many predominently black areas, even
  if surrounded by other serviced neighborhoods.


• Harvard found that when people Google for a typically African-American name, an ad for a criminal records company was more likely to turn up.


• Men were 6 times more likely to be shown an ad for high-paying executive coaching services than women.

Try an algorithm!

Vocabulary Review

• Algorithm: A repeatable process for determining
  the solution to a problem


• Time Complexity: How long the algorithm takes
• Space Complexity: How much space the algorithm uses
• Optimization: Redesigning it to take less time or space
• Data Structure: A way to organize data

Algorithms...

not as scary!

What did you learn today?

What surprised you?

Resources

• Khan Academy
• Code Wars
• Bubble Sort Dance
• Project Euler
• Intro to Whiteboarding (Amelia Downs)

Thank you!

Even more if there is time...

You are google. You have lots of street view images and you want to correlate them with addresses.

How do you 'read' all of the house numers?

Remember:

Computers are terrible at reading distorted text in images.

That's why captchas (Completely Automated Public Turing test to tell Computers and Humans Apart) work.

Mechanical Turk: The use of human intelligence to perform tasks that computers are currently unable to do.

Sometimes humans are the solution

• Transcribing receipts or business cards


• Parsing satellite images of an ocean looking for a missing vessel


• You have the audio for every Planet Money podcast, but you want to know who hosts each episode, which they say in the first 20 seconds