```
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 is an algorithm?
- intro to algorithmic complexity

(how good is an algorithm) - demonstrate sort and search algorithms

(the classics)

- Particpation
- Keep coming up with more solutions
- Postivity/Energy

- Syntax
- Knowing all the things

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

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

- Turn on TV
- Watch what is on

- Turn on TV
- Flip through every channel and rate what is on
- Find the highest rated channel
- Watch

- Turn on TV
- Check 5 favorite channels and rate what is on
- Find the highest rated channel
- Watch

Turn on the TV

Rate all channels

ORRate top channels

A way to store data

(so that it can be used as desired)

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?

Like a list but:

- Not ordered
- Unique Items

key : value

- Solve a problem
- in a repeatable way

- Show your thought process
- Solve the most obvious (to you!) solution first
- Improve it

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

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

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!

- Drive large car to grocery store
- Buy every thing you need

Saves time, but requires you to have a large car

Lower time complexity

Higher space complexity

- Walk to grocery store with tote bag
- Buy one item
- Walk home and drop off the item
- Repeat until done

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

Higher time complexity

Lower space complexity

How long does an algorithm take?

- Dump laundry on floor

```
laundry.drop()
```

How long does the algorithm take?

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,

it takes (N*0 + 2) => O(2) => O(1).

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

```
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()
```

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,

it takes (N*10 + N*30) => O(N).

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()
```

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,

it takes (N*10 + N*30 + N*N*2) => O(N^2)

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 |

N^{2} |
quadratic | double loop | check all pairs |

N^{3} |
cubic | triple loop | check all triples |

2^{N} |
exponential | exhaustive search | check all subsets |

skipping to the front of a line

O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

waiting in a line

O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

skipping half of a line

O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

sorting your books in alphabetical order

O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

looking up an element in an array

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

O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

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^2) - Quadratic

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^2) - Quadratic

- Drive car to grocery store
- Get cart
- Put everything in the cart
- 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)

- Walk to grocery store
- Buy first item on list
- Walk home and drop off the item
- 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 the time requirement of your algorithm?

What's the space requirement of your algorithm?

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.

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

Find an item by repeatedly halving the search space.

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.

- Pick the middle element of the array
- Repeat those steps on new subarray.

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

```
def BinarySearch(array, value):
"""returns bool if value is in array"""
low = 0
high = len(array) - 1
while low < high:
mid = (low + high) / 2
if array[mid] > value:
high = mid - 1
elif array[mid] < value:
low = mid + 1
else:
return True
```

python code
What factors determine time?

N = number of items in sequence.

Since algorithm splits array in half every time,
at most log_{2}N steps are performed.

Performance varies depending on sequence characteristics (distribution)

- Pick a search algorithm.
- Play the number guessing game (higher/lower).
- Try and guess the number in the smallest number of tries using the principles of binary search.
- Keep track of the number of guesses it takes you.
- If you have time, repeat for different ranges (0-500, 0-1000, etc).

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

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

- Iterate over the unsorted array, keeping track of the minimum value as you go
- When you get to the end of the array, you know which element is the minimum
- Swap the minimum element and the first element in the unsorted array
- The first element is now considered sorted
- Repeat until the rest of the array is sorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

- Find minimum
- Swap in front
- Repeat with unsorted

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

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)

Only requires 1 extra temporary variable. O(1)

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

Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization

- With a partner, take a deck of cards and pick one of the sort algorithms
- Get a feel for the algorithm by sort the deck of cards according to the algorithm.
- Try to match the algorithm to its ideal dataset

- You run a calendar app. People insert events into the app one at a time and you need to sort the events
- 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.
- You have a list of names that is mostly sorted, but you have to finish the sorting!
- Two companies are merging and they each have seniority lists based on hire dates. They need to combine these lists into one sorted list.

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

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.

When is it best?

- When you are in computer science class
- When the values are mostly sorted

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.

You have 6 stacks of mostly sorted papers. How would you sort them all together?

- Use bubble sort or selection sort to sort each pile
- Use merge sort to combine the sorted piles

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

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.

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

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

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.

- 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

What did you learn today?

What surprised you?

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