Algorithms

Intro

Our Goals

• Understanding Algorithms

• Algorithms Examples

• Some Common Algorithms

Understanding Algorithms

What’s an Algorithm?

A set of rules to be followed

Algorithms are Language-Independent

repeat until we reach end:
    can you move left?
        if yes, turn left

    can you move forward?
        if yes, move forward
    otherwise, turn right

// (in Javascript)

maze = new Maze('http://url-for-our-maze');

while (!maze.solved()) {
  if (maze.hasLeftPath()) {
    maze.turnLeft();
  }

  if (maze.hasForward()) {
    maze.goForward();
  } else {
    maze.turnRight();
  }
}

Algorithms Examples - Mazes

Solving This Maze

• How would you solve this maze?

• How would you tell a robot to solve this maze?

Optimal Solution?

If you know the layout of the maze, you can program the optimal solution:

Turn left, move forward 3 steps, turn right,
step forward, turn left move forward 2 steps,
turn left, 1 step forward, turn left,
2 steps forward, turn right...

Oh Noes!

• What if you don’t know structure of the maze?

• What if you can only see around you?

One Possibility

• Random Mouse Algorithm

  • Proceed in a straight line until junction, pick direction randomly

• Known as a Las Vegas Algorithm

Better Strategy

• Left Hand on Wall Algorithm

  • Walk around maze keeping your left hand on the wall

• May not be the most efficient, but guaranteed to get you out

Doesn’t work for all mazes

Note that this algorithm doesn’t work on all mazes, though – it always works only for those where the maze doesn’t cross over itself and where both the entrance and the exit are at an edge.

There are algorithms that work on all mazes – but these are more complex (and often more inefficient for the common case of no-crossovers, entrance-and-exit-at-edge). This situation, of more generalizable cases being more complex and less efficient for normal cases is a common one for algorithms.

Our First Algorithm

repeat until we reach end:
    can you move left?
        if yes, turn left

    can you move forward?
        if yes, move forward
    otherwise:
        turn right

Different Algorithms

Algorithm	Solutions	Guarantee?	Human Doable?	Memory Free?
Random Mouse	1	no	yes	yes
Wall Follower	1	no	yes	yes
Pledge Algorithm	1	no	yes	yes
Chain Algorithm	1	yes	no	no
Recursive Backtracker	1	yes	no	no
Trémaux’s Algorithm	1	yes	yes but hard	no
Dead End Filler	all	no	yes	yes
Cul-de-Sac Filler	all	no	yes	yes
Blind Alley Sealer	all	yes	no	no
Blind Alley Filler	all	yes	yes	yes
Collision Solver	all shortest	yes	no	no
Shortest Paths Finder	all shortest	yes	no	no
Shortest Path Finder	1 shortest	yes	no	no

• Solutions: Which solutions does this maze present?

• Guarantee: Is this guaranteed to find a solution (if possible) for every maze?

• Human doable: Is this algorithm straightforward enough for a human to do it?

• Memory Free: Can this algorithm be written without requiring additional memory?

Simplified and adapted from http://www.astrolog.org/labyrnth/algrithm.htm.

Guessing Numbers

Let’s Play a Game!

I’ll pick a number from 1 to 100.

You guess the number.

I’ll tell you if you guessed correctly, too low, or too high.

Keep guessing until you guess the number.

How Did You Solve This?

Most people have learned to guess 50 first, then, depending on whether it’s too-high or too-low, to move halfway to the other end. This is the most efficient way to solve this problem.

Binary Search

too_low = 0
too_high = 101

while not guessed:
    guess = midpoint between too_low and too_high

    if guess > secret_number:
        too_high = guess
    if guess < secret_number:
        too_low = guess

Finding Palindromes

Palindromes

Palindrome (n). Word which reads same backward or forward.

• “kayak”

• “radar”

• “deleveled”

• “deified”

Palindromes

Or, to pick a really silly and long phrase example: “A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal – Panama!”

For lots of fun examples, see Wikipedia on Palindromes.

Let’s Design an Algorithm!

racecar

• Is first letter same as last?

  • If so, move in both directions

  • Reached middle? It’s a palindrome!

• Reverse string

  • If it matches, it’s a palindrome!

Pseudocode

Pseudocode To Start An Algorithm

You might have noticed that our last example did not include any code. This is because algorithms are not language specific. Therefore, they should be desiigned in pseudocode. Pseudocode is the process of laying out your logic in an easy to read, easy to understand way. Notice, in the previous example we did not write:

if str[0] === str[str.length - 1]

Instead, we simply wrote Is first letter same as last?. From this pseudocode, we should be able to write an algorithm in any language.

More Algorithms

Sorting Items

• Bubble Sort

• Merge Sort

• Insertion Sort

• Heap Sort

• Quick Sort

and many more….

Tree Searching

• Binary Search

• Breadth First Search

• Depth First Search

Many Notable Algorithms

It is important to know that there are many algorithms out there for all sorts of different purposes. In most cases you do not need to create your own algorithm, however, you do need to look at the pro’s and con’s of different algorithms before choosing to use them.