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

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

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

Exercise time!

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

Data Structures

(Just a good to know, will not 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, 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

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)

Laundry v1 Big O Notation


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

Laundry v2 Big O Notation


(N*10 + N*30)

→ O(40N)

→ O(N)


Linear time

Making Outfits

Making all possible outfit combinations.

For simplicity's sake, assume there are an equal amount of pants and shirts.


pants_pile = ['blue-jeans', 'black-jeans', 'dress-pants', ..., 'white-pants'] // (n items)
shirts_pile = ['white-shirt', 'blue-blouse', ..., 'stripe-shirt'] // (n items)
outfits = []

for shirt in shirts_pile:
    for pants in pants_pile:
        outfits.append([shirt, pants])

           

Making Outfits

We must match each shirt with each pair of pants.

Looking at each item takes 2 seconds.

pants shirts calculation seconds
4 4 (4*2*4*2) 64
8 8 (8*2*8*2) 256
1024 1024 (1024*2*1024*2) 4194304

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)


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(n2) - Quadratic

What is the time complexity of...


waiting in a line


O(1) - Constant

O(n) - Linear

O(n2) - Quadratic

What is the time complexity of...


skipping half of a line


O(1) - Constant

O(n) - Linear

O(n2) - Quadratic

What is the time complexity of...


sorting your books in alphabetical order


O(1) - Constant

O(n) - Linear

O(n2) - 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(n2) - 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(n2) - 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(n2) - 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!

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


Search algorithm is an algorithm which solves the problem of retrieving store information.

Wikipedia - Search Algorithms

Discuss

How to solve the problem of searching billions pieces of data?


Linear Search

One of the simplest searches.


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

Linear Search

Exercise

Writing Linear Search


Click here!

Algorithm Solving Strategies

  • Use iteration to move over a data structure
  • Use comparison of values
  • Use a large, diverse enough data set

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


Click here!

Algorithm Solving Strategies

  • Use variables as a pointers to 'track' data during an algorithm
  • 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 log2N steps are performed.

Other Searching Algorithms


Performance varies depending on sequence characteristics (distribution)


Sorting

Wikipedia list of sorting algorithsm

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 Code


function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

function selectionSort(array) {
  for(var i = 0; i < array.length; i++) {
    var min = i;
    for(var j = i + 1; j < array.length; j++) {
      if(array[j] < array[min]) {
        min = j;
      }
    }
    if(i !== min) {
      swap(array, i, min);
    }
  }
  return array;
}
            
Source

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?

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.

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

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