Intro to Algorithms

Welcome!

Wifi Info

Network:Name

Password:Password

Thanks to our sponsor:

Welcome!

About your instructor

Lucas Willett

Thank you to our Teaching Assistants today

TA Name

TA Name

TA Name

Now it's all about you!

• Tell us who you are.
• What do you hope to get out of this class?
• Unlimited amount of money - where would you travel to?

What we'll be covering in this class

• what an algorithm is
• introduction to the idea of algorithmic complexity (big O notation)
• demonstrate sort and search algorithms (with a hands-on re-enactment)
• try to write the code for an algorithm ourselves
• finish with an overview of the many types of algorithms out there

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

What are the steps for doing it?

Example: Hanging up Laundry

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.

Laundry: Time Complexity

How long does the algorithm take?

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.

Laundry v2: Time Complexity

If N = # items of clothing and # items in section, it takes (N*10 + N*30 + N*N*2) => O(N^2)

Time Complexity

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 = NBest case: M = 1Average: 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

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.

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)

• Linear
• Interpolation search

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.

• Depth-limited
• Breadth-first-search
• A*
• Hill climbing
• Dijkstra

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.

The Traveling Salesman Problem

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