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
                Sorting
                Binary Search
                Algorithms in Real Life
                Conclusion

What we'll 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

• Particpation
• Keep coming up with more solutions
• Postivity/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 make finding stuff easier.
• Finding keys that you lost.
• Finding something good to watch on TV.
• Washing your car windows.

Finding something to watch on TV v1

1. Turn on TV
2. Watch what is on

Finding 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

Finding 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?

Data Structures

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, and how can they be used to your advantage?

Example: Arrays/List

Example: Dictionaries/ Objects/ Hash Maps/ Maps

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

Abstract Data Structures

Linked List

Tree

Graph

Queue

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
• Improve it

What is an algorithm you use?

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

Ideas:

• Organizing email
• Swiping left or right on tinder
• Deciding what restaurant to eat at
• Finding a paper on your desk

Optimizations

Designing algorithms is about making decisions. 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 the algorithm use

The less complex the better!

Time Efficient Grocery Shopping

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

Space Efficient Grocery Shopping

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 the complexity of an algorithm
• Approximation of how quickly space or time complexity grows relative to input size
• Usually talking about worst case scenario

Hanging up Laundry v1

1. Dump laundry on floor

laundry.drop()
            

How long does the algorithm take?

Laundry v1

How long does the algorithm take?

Dumping out my laundry takes 2 seconds

If N = items of clothing,
time it takes: (N*0 + 2)

Laundry v1 Big O Notation

→ O(2)

→ O(1)

Constant time

Laundry v2

1. Dump laundry on bed.
2. Pick up each piece of clothing, put in a pile for that type ("shirts", "underwear", "socks", etc.)
3. After all are in piles, go through each item in each pile, and hang up each one.

Laundry v2 Code

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

for clothing_item in laundry: 
  piles[clothing_item.type].append(clothing_item)

for pile in piles:
    for clothing_item in pile:
        clothing_item.hang_up()
                

Laundry v2

How long does the algorithm take?

Putting an item in a pile takes 10 seconds.
Hanging an item up takes 30 seconds.

If N = items of clothing,
time it takes: (N*10 + N*30)

Laundry v2 Big O Notation

→ O(40N)

→ O(N)

Linear time

Laundry v3

Addition: We sort our clothes as we hang them up in the closet.

piles = {'shirts': [], 'socks': []}
closet = {'sock_drawer': [], 'shirt_section': []}

for clothing_item in laundry: 
  piles[clothing_item.type].append(clothing_item)

for pile in piles:
    for clothing_item in pile:
        section = closet[clothing_item.closet_section]
        for hung_clothing in section:
            if clothing_item.color > hung_clothing.color:
                clothing_item.hang_up()

           

Laundry v3

Now we must loop through closet section items each time we hang up an item.
Each look at an item takes 2 seconds.

If N = # items of clothing and # items in section,
time it takes: (N*10 + N*30 + N*N*2)

Laundry v3 Big O Notation

→ O(40N + 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
                    
              

Quiz 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...

sorting your books in alphabetical order

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"]

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++) {
    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++) {
        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

Time Efficient Grocery Shopping

1. Drive car to grocery store
2. Get cart
3. Put everything in the cart
4. Buy items and drive home

The size of the cart grows as the number of items on the list grows.

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

The space complexity is O(N)

Space Efficient Grocery Shopping

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

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

The space complexity is O(1) or constant.

What's more important? Time or space?

Discuss!

What's the time requirement of your algorithm?

What's the space requirement of your algorithm?

Making Crepes

Write two algorithms for making crepes, one that is time efficient and one that is space efficient.

Pseudocode first then whiteboard code if you have time.

Searching Algorithms

Find an item with a particular value in a sorted sequence.

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

J is the 3rd element (index 2).

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 descending 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 e is greater than m, then e must be in left subarray. If m is greater 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

Binary Search:

Time/Space Complexity

What factors determine time?

N = number of items in sequence.

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

Other Searching Algorithms

Performance varies depending on sequence characteristics (distribution)

• Linear
• Interpolation search

Sorting

Sorting

Sorting

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. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

Selection Sort Simulation

• Line up randomly.
• Sort by [something secret] using selection sort.

Selection Sort:

Time Complexity

Selection Sort:

Space Complexity

Only requires 1 extra temporary variable. O(1)

More Sort Algorithms

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

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

Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization

Which sort is best?

A great resource to help visualize the different sorting algorithms:

Insertion Sort

When is it best?

• Good for incremental sorting.


• When you need elements sorted, but you only get them a few at a time


• You run a calendar app. People insert events into the app one at a time and you need to sort the events

Bucket Sort

When is it best?

• When there is a known range of values with a known distribution


• Birthdays


• GPAs


• You work at a 100k person company and what to create a list of birthdays so everyone can celebrate each month. Year doesn't matter, just date.

Bubble Sort

When is it best?

• When you are in computer science class


• When the values are mostly sorted

Merge Sort

When is it best?

• When you are combining already sorted arrays


• Two companies are merging and they each have seniority lists based on hire dates. They need to combine these lists into one sorted list.

Explore more!

I focused on which type of data is good or bad for each sorting example, but each sorting algorithm also has its own space trade offs as well.

• Quick Sort
• Quick3 Sort
• Heap Sort
• Shell Sort

Algorithms in Real Life

Finding Friends

Write a series of algorithms to suggest friends to facebook users. Remember to 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 for 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 neighborhoods, 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 found to be 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 takes
• Optimization: Making an algorithm 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
• Intro to Whiteboarding (Amelia Downs)
• Project Euler
• Practice!

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