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.

What's an algorithm that you use?

What are the steps for doing it?

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

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

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

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 |

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.

Solve a problem

in shortest time

with minimum space requirements

...depending on your particular constraints.

What's the time requirement of your algorithm?

What's the space requirement of your algorithm?

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.

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]

A simple but not very efficient sorting algorithm.

From here.

- Compare adjacent elements. If the first is greater than the second, swap them.
- 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.
- Repeat the steps for all elements except the last one.
- Continue for one less element each time, until there are no more pairs to compare.

- Line up randomly.
- Sort by height using bubble sort.

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

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(N^{2})

Only requires 1 extra temporary variable.

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

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

- Pancake sort
- Spaghetti sort
- BogoSort
- Quantum Bogo Sort

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

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

- Sort yourselves by height again.
- Now let's find someone with a particular height using binary search.

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 }

Time/Space Complexity

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)

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

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.

Find a route in a graph.

Find a particular node in a connected graph.

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

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

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

^{d})

Space: `O(bd)`

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

- 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

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

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

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

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

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

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

Wrapping Up