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

Turn on the TV

Rate all channels

OR

Rate top channels

# 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: Dictionaries/ Objects/ Hash Maps/ Maps

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

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

Saves time, but requires you to have a large car

Lower time complexity

Higher space complexity

### 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

Takes a long time, but doesn't require a car

Higher time complexity

Lower space complexity

## 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

#items #seconds
4 2
8 2
16 2

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

(N*0 + 2)

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

#items #seconds
4 (4*10 + 4*30) = 160
8 (8*10 + 8*30) = 320
16 (16*10 + 16*30) = 640

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

(N*10 + N*30)

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

items section items seconds
4 4 (4*10 + 4*30 + 4*4*2) 192
8 8 (8*10 + 8*30 + 8*8*2) 448
1024 1024 (1024*10 + 1024*30 + 1024*1024*2) 2138112

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

### Laundry v3 Big O Notation

(N*10 + N*30 + N*N*2)

→ O(40N + 2N2)

→ O(2N2)

→ O(N2)

## 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

### What is the time complexity of...

waiting in a line

O(1) - Constant

O(n) - Linear

### What is the time complexity of...

skipping half of a line

O(1) - Constant

O(n) - Linear

### What is the time complexity of...

sorting your books in alphabetical order

O(1) - Constant

O(n) - Linear

### 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

### 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

### 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

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

## 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: 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.

## 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 log2N steps are performed.

## Other Searching Algorithms

Performance varies depending on sequence characteristics (distribution)

## 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

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 post-its 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 diswasher one at a time

There are lots of different types of data 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. 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.

### Time Complexity

What is the best case?

What is the worst case?

They are the same! No matter what, selection sort has a time complexity of O(N^2)

### Space Complexity

Only requires 1 extra temporary variable. O(1)

## More Sort Algorithms

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

## Which sort is best?

A great resource to help visualize the different sorting algorithms:

Visualgo.net

### 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

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

# 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