Intro to Algorithms

Schedule


10:00 - 1PM     Introduction
                Defining an algorithm
                Time/space complexity
                Goal of algorithms
                Sorting

1:00 - 2:00     Lunch

2:00 - 5:00     Searching
                Data Structures
                Primes
                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)

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.

Discuss!

What's an algorithm that you used today?

Write out the steps for doing it?

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


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

            for (var i = 0; i < clothing.length; i++) {
              piles[clothing[i].type].push(clothing[i]);
            }

            for (var pile in piles) {
              for (var i = 0; i < pile.length; i++) {
                pile[i].hangUp();
              } 
            }

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.


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

            for (var i = 0; i < clothing.length; i++) {
              piles[clothing[i].type].push(clothing[i]);
            }

            for (var type in piles) {
              for (var i = 0; i < piles[type].length; i++) {
                var section = closetSections[type];
                for (var j = 0; j < section.length; j++) {
                  if (pile[i].color > section[j].color) {
                    pile[i].hangUp();
                  }
                }
              } 
            }

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

Laundry: Space Complexity

How much space does sorting items of clothing into piles take?

Assume: piles of clothing can be infinitely high.

N = number of pieces of clothing,
M = number of piles.

Worst case: M = N
Best case: M = 1
Average: N/2

Time Efficient Grocery Shopping


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

What is the space complexity?

Grocery Shopping v1

How much space does the algorithm take?

Each item takes 10cm^3 in the car


#items #cm^3
4 (4*10) = 40
8 (8*10) = 80
16 (16*100) = 160

If N = number of grocery items,
it takes (N*10) => O(N).

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

Grocery Shopping v2

How much space does the algorithm take?

Each item takes 10cm^3 in the tote bag


#items #cm^3
4 (10) = 10
8 (10) = 10
16 (10) = 10

If N = number of grocery items,
it takes (10) => O(1).

What's more important? Time or space?

Goal of Algorithms


  • Solve a problem
  • in a repeatable way

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

Goal of Whiteboarding Interviews

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

Discuss!

What's the time requirement of your algorithm?

What's the space requirement of your algorithm?

Algorithms in Programming

Sequence Algorithms

Many algorithms operate on lists of things

In programming, basic lists are called arrays


[4, Q, 5, A, J, 10, K]

What sort of algorithms can you do on a deck of cards?


Sort, search, shuffle, etc.

Sorting Algorithms


Rearrange items in a sequence by some property about each item.
(like numerical or alphabetical order)


[4, Q, 5, A, J, 10, K]

->

[4, 5, 10, J, Q, K, A]

Bubble Sort

A simple but not very efficient sorting algorithm.

An interactive example

Bubble Sort: Steps


  1. Compare adjacent elements. If the first is greater than the second, swap them.
  2. Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest.
  3. Repeat the steps for all elements except the last one.
  4. Continue for one less element each time, until there are no more pairs to compare.

Exercise: Bubble Sort Simulation


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

Bubble Sort:

Pseudo-code



            For I = 0 to N - 2
               For J = 0 to N - 2
                 If (A(J) > A(J + 1)
                   Temp = A(J)
                   A(J) = A(J + 1)
                   A(J + 1) = Temp
                 End-If
               End-For
             End-For
              

Bubble Sort:

Time Complexity


What factors determine time?

N = number of items in sequence.


What is the best case? What is the worst case?
Already sorted array
N comparisons.
O(N)
Reverse sorted array
N*N comparisons.
O(N2)

Bubble Sort:

Space Complexity


Only requires 1 extra temporary variable.

More Sort Algorithms


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




Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization

Fun Sort Algorithms


(Who says programmers don't know how to let loose?)


  • Pancake sort
  • Spaghetti sort
  • BogoSort
  • "A particularly ineffective sorting algorithm"

  • Quantum Bogo Sort

Exercise Time!


  • With a partner, take a deck of cards and pick one of the sort algorithms.
  • Sort the deck of cards according to the algorithm.
  • Keep track of the number of operations you have to do.
  • If you have time, try another algorithm.

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



            BinarySearch(array, value) {
                low = 0
                high = array.length - 1
                while (low <= high) {
                    mid = (low + high) / 2
                    if (A[mid] > value)
                        high = mid - 1
                    else if (A[mid] < value)
                        low = mid + 1
                    else
                        return mid
                }
                return not_found
            }

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

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

Example: Sets

Example: Dictionaries/Objects

Example: Binary Trees

Try an algorithm!

Finding Primes


Prime number: a number that is only divisible by 1 and itself.


Why should computer scientists care?

Encryption!


Easy: 3 * 11 * 127 * 113327 = 474953457

Hard: 474953457 = 3 * 11 * 127 * 113327

Finding Primes

How would you find the first 1000 primes?

How would you find all primes under 1000?


Challenge

What are the tradeoffs?

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

Resources

Thank you!