Intro to Algorithms



teaching-materials.org/algorithms/

"Algorithm"


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

What are the steps for doing it?

Example: Hanging up Laundry

  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.

Hanging Up Laundry: 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: Time Complexity

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 v2

Addition: We hang up our items in sorted order 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 v2: Time Complexity

Now we must loop through closet section items each time we hang up an item.
Each look at an item takes 2 seconds.

itemssection itemsseconds
44(4*10 + 4*30 + 4*4*2)192
88(8*10 + 8*30 + 8*8*2)448
10241024(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

Laundry: Space Complexity


How much space does our algorithm require?

What are our factors that determine space?

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.

Goal of Algorithms

Solve a problem
in shortest time
with minimum space requirements

...depending on your particular constraints.

Discuss!


What's the time requirement of your algorithm?

What's the space requirement of your algorithm?

Algorithms in Programming

Sequence Algorithms


Many items operate on sequences (lists/arrays)


What sort of algorithms do you do on a deck of cards?
[4, Q, 5, A, J, 10, K]


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]

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

Bubble Sort

A simple but not very efficient sorting algorithm.

From here.

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

Already sorted array
N comparisons.
O(N)


What is the worst case?

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.


  • Insertion sort
  • Selection sort
  • Merge sort
  • Bucket sort


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
  • 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 index of element e with 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 yourselves by height again.
  • Now let's find someone with a particular height 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.

Other Searching Algorithms


Performance varies depending on sequence characteristics (distribution)


Exercise Time!


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

Graph Algorithms


Much data is actually connected node and vertices, which makes it much harder to find algorithms that compute solutions quickly.


A lot of research goes into solving graph problems.


Graph Traversal Algorithms


Find a route in a graph.

Find a particular node in a connected graph.

Depth First Search (DFS)


DFS: Steps

  • DFS progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children.
  • Then the search backtracks, returning to the most recent node it hasn’t finished exploring.

DFS: Pseudocode



procedure depth_first_search(graph, vertex):
    label vertex as discovered
    let S be a stack
    S.push(v)
    while S is not empty        
          t ← S.top 
          if there is an edge u adjacent to t that is undiscovered and unexplored
             S.push(u)
          else
             mark t as explored
             S.pop()
  

DFS: Time/Space Complexity


Time: If b is the "branching factor" and d is the deepest depth: O(bd)


Space: O(bd)

More Graph Search Algorithms


Many of these use "heuristics" to make a better guess as to what path to go down, to avoid searching the whole space.


Graph Traversal in Real Life


  • Word search
  • Maze solving
  • Calculating an optimal route
  • Grocery store shopping
  • Calculating chess strategies
  • Making a guest list
  • Finding a new book to read on Amazon

The Traveling Salesman Problem

A special variant of the graph search problem.

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Considered "NP-hard" (all solutions are exponential)

Many different approaches, like "Ant Colony":

☞ Demo: USC Fountain Map, ☞ Wikipedia: TSP

Exercise Time!


  • Solve a maze using a depth first algorithm.
  • Calculate the degrees of separation between Kevin Bacon and Bruce Willis. Try it first with breadth first search, and then depth first. Draw a graph of the nodes you visit.
  • Take the map of SF and find a route between Citizen Space and the Caltrain, using depth first search. Draw a graph of the nodes (intersections) that you visit.

More Algorithms!



☞ Wikipedia: List of algorithms

Geometry: Detecting Collision


☞ Demo: Shape-Based Hit Detection, ☞ Box2d JS, ☞ Tutorial: Collision Detection with Circles, ☞ Wikipedia: Collision Detection

Math: Primality Tests


☞ Khan Academy: Prime Numbers ☞ Wikipedia: Primality Tests

Statistics: k-means clustering


☞ Demo: Map symbol clustering: k-means vs noverlap, ☞ Wikipedia: K-means clustering

Machine learning: decision trees


Wikipedia: Decision tree learning

Compression: Run-length encoding


☞ Image Processing, ☞ fileformat: Run-length Encoding, Wikipedia: Run-length Encoding

Image processing: Edge detection


☞ Demo: Doggy Video, ☞ Demo: Canvas Pixel Manipulation, ☞ Demo: Tron Video, Wikipedia: Edge detection

Algorithms:
Wrapping Up