Intro to algorithms

Let's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. The computer is going to randomly select an integer from 1 to 15. You'll keep guessing numbers until you find the computer's number, and the computer will tell you each time if your guess was too high or too low:

[[☃ cs-program 1]]

Once you've found the number, reflect on what technique you used when deciding what number to guess next.

Maybe you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number. We call this approach linear search, because you guess all the numbers as if they were lined up in a row. It would work. But what is the highest number of guesses you could need? If the computer selects 15, you would need 15 guesses. Then again, you could be really lucky, which would be when the computer selects 1 and you get the number on your first guess. How about on average? If the computer is equally likely to select any number from 1 to 15, then on average you'll need 8 guesses.

But you could do something more efficient than just guessing 1, 2, 3, 4, …, right? Since the computer tells you whether a guess is too low, too high, or correct, you can start off by guessing 8. If the number that the computer selected is less than 8, then because you know that 8 is too high, you can eliminate all the numbers from 8 to 15 from further consideration. If the number selected by the computer is greater than 8, then you can eliminate 1 through 8. Either way, you can eliminate half the numbers. On your next guess, eliminate half of the remaining numbers. Keep going, always eliminating half of the remaining numbers.

We call this halving approach binary search, and no matter which number from 1 to 15 the computer has selected, you should be able to find the number in at most 4 guesses with this technique.

Here, try it for a number from 1 to 300. You should need no more than 9 guesses.

[[☃ cs-program 1]]

How many guesses did it take you to find the number this time? Why should you never need more than 9 guesses? (Can you think of a mathematical explanation)?

We'll return to binary search, and we'll see how you can use it to efficiently search for an item in a JavaScript array. But first, let's look at an algorithm for a trickier problem.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

Sometimes, very different-sounding problems turn out to be similar when you think about how to solve them. What do Pac-Man, the royal family of Britain, and driving to Orlando have in common? They all involve route-finding or path-search problems:

• How is the current Prince William related to King William III, who endowed the College of William and Mary in 1693?
• What path should a ghost follow to get to Pac-Man as quickly as possible?
• What's the best way to drive from Dallas, Texas to Orlando, Florida?

We have to be given some information to answer any of these questions.

For example, a family tree of the royal family of Britain would show connections between people who were directly related. Prince William is the son of Charles Philip Arthur Windsor. Charles is the son of Queen Elizabeth II. The problem is to find a short chain on the family tree connecting Prince William and William III, using these direct connections. As you can see from the tree below, it might take quite a few connections.

[[☃ image 2]]

For Pac-Man, we need a map of the maze. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.

[[☃ image 2]]

In order to find a driving route from Dallas to Orlando, we might use a map of the United States, showing connections, roads, between nearby cities. No single road directly connects Dallas to Orlando, but several sequences of roads do.

[[☃ image 2]]

Exploring a maze

Maze games are fun, so let's delve deeper into one. In our game, the main character can navigate to destinations in a maze.
As the human player, you control the main character by clicking on the next destination in the maze, and the computer figures out how to move the character there. The destination is marked with a red rectangle labeled "GOAL", and the character starts off on their first destination, the start square. Try playing it below:

[[☃ cs-program 1]]

Notice how the character moved to the goal? To make that happen, the program needs to determine the precise set of movements that the character should follow to get to where the user clicked and then animate those movements. There may be multiple paths for the character to follow, and the program needs to choose the best of those paths.

Before deciding on an algorithm, the movement rules first need to be established: walls are made of gray squares and legal locations to travel are empty. In each step, the character can move from one square to an adjacent square. This character, like a chess rook, cannot move diagonally.

Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. But what does "closer to the goal" mean? Traveling in a straight line toward the goal will often cause the character to smack into a wall. The algorithm needs to determine which of the surrounding squares are indeed "closer to the goal", and we can do that by assigning a "cost" to each square that represents the minimum number of steps the character would have to take to get from that vertex to the goal. Here's an algorithm for assigning a cost to each square:

1. Start on the goal square. How far is the goal from the goal? Zero steps, mark the goal with the number 0.
2. Find all squares in the maze that are exactly one step away from the goal. Mark them with the number 1. In this maze, if the goal is the exit square, then there is only one square that is exactly one step away.
3. Now find all squares in the maze that are exactly two steps away from the goal. These squares are one step away from those marked 1 and have not yet been marked. Mark these squares with the number 2.
4. Mark all squares in the maze that are exactly three steps away from the goal. These squares are one step away from those marked 2 and have not yet been marked. Mark these squares with the number 3.
5. Keep marking squares in the maze in order of increasing distance from the goal. After marking squares with the number $ k $, mark with the number $ k+1 $ all squares that are one step away from those marked $ k $ and have not yet been marked.

Eventually, the algorithm marks the square where the character starts. The program can then find a path to the goal by choosing a sequence of squares from the start such that the numbers on the squares always decrease along the path. If you view the number as the height of the square, it would be like going downhill.

What if the user were trying to get from the start square to the goal? Using the square-marking algorithm, the start square is 13 steps away from the goal. Here's a picture showing the connections between possible locations for the character, the start, the goal, and the shortest distance of each location from the goal:

[[☃ image 2]]

There's a square immediately to the south of the start that is only 12 steps from the goal. So the first move is "south". South of that square is an 11. South again. South again to a 10. Then east twice to an 8. North to a 7, east to a 6, then north five times to a 2. Finish up by going west once, to a 1, and finally north once, to the goal.

We won't discuss exactly how to implement this maze search algorithm right now, but you might find it fun to think about how you might represent the maze and the character using JavaScript and how you might implement the algorithm.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

We've given you a little intro to algorithms, and a few examples. Now before we go further, we want to see what algorithms you can think of.

* What algorithms do you use in everyday life? Do you think you could write a program to make them more efficient? * What algorithms do you think are used by your favorite games and apps? * Have you ever made an algorithm for a program? What did it do? Was it correct and efficient?