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: Arrays/List

Example: Sets

Like a list but:

  • Not ordered
  • Unique Items

Example: Dictionaries/ Objects/ Hash Maps/ Maps

key : value

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?

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,
it takes (N*0 + 2) => O(2) => O(1).

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,
it takes (N*10 + N*30) => O(N).

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,
it takes (N*10 + N*30 + N*N*2) => O(N^2)

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

What is the time complexity of...


waiting in a line


O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

What is the time complexity of...


skipping half of a line


O(1) - Constant

O(n) - Linear

O(n^2) - Quadratic

What is the time complexity of...


sorting your books in alphabetical order


O(1) - Constant

O(n) - Linear

O(n^2) - 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^2) - 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^2) - 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^2) - 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: 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:

Pseudocode



            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

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.

Binary Search:

Visualized

Other Searching Algorithms


Performance varies depending on sequence characteristics (distribution)


Exercise Time!


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

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

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)

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.




Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization

Which sort is best?


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

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.

What if...

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


  1. Use bubble sort or selection sort to sort each pile

  2. Use merge sort to combine the sorted piles

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?

Resources

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