What is an algorithm and why should you care?

0:00- [Voiceover] What is an algorithm? One definition might be a set of steps to accomplish a task. You might have an algorithm for getting from home to school, for making a grilled cheese sandwich, or for finding what you're looking for in a grocery store. In computer science, an algorithm is a set of steps for a computer program to accomplish a task.

0:24Algorithms put the science in computer science. And finding good algorithms and knowing when to apply them will allow you to write interesting and important programs. Let's talk about a few famous algorithms. How does Google Hangouts transmit live video across the Internet so quickly?

0:44They use audio and video compression algorithms. How does Google Maps figure out how to get from Dallas, Texas to Orlando, Florida so that you can get to Disney World? They use a route finding algorithm. How does Pixar color a 3D model of a character based on the lighting in a virtual room?

1:04They use a rendering algorithm. How does Nasa choose how to arrange the solar panels on the International Space Station and when to rearrange them? They use an optimization and a scheduling algorithm. Those algorithms are more complex than our everyday algorithms like making a grilled cheese sandwich.

1:25But they boil down to the same thing, a set of steps to accomplish a task. If you know something about existing algorithms, you can save yourself some effort and make your programs faster by applying the right one. For example, let's say that you're writing a game and you want the user to be able to play against the computer.

1:46Well, you could look at checkers games for inspiration. Computer scientists have figured out how to write checkers programs that never lose by using the minimax search algorithm to search through the huge tree of possible moves. If your game is similar to checkers, then you might be able to use algorithms based on these techniques.

2:08If not, then knowing the limitations of those algorithms might lead you to redesign your game if it requires having a skilled computer player. It's also important to know how to design new algorithms as well as how to analyze their correctness and efficiency. In the biological sciences, new algorithms are continually being designed with purposes like designing the molecular structures that are the core of disease fighting drugs.

2:36In physics, algorithms simulate climate and weather patterns. In other algorithms, search and analyze the vast data about stars in the universe that's collected by automated space telescopes. Across all the sciences, and even on websites like Khan Academy, efficient algorithms are needed to analyze huge data sets or to select intelligently from a vast number of possible decisions.

3:02In just about any area you might be interested, new algorithms will allow massive computational power to be harnessed to do things that people really need and care about. Now, not all algorithms are created equal. So what makes a good algorithm? The two most important criteria are that it solves a problem and that it does so efficiently.

3:26Most of the time, we want an algorithm to give us an answer that we know is always correct. Sometimes we can live with an algorithm that doesn't give us the correct answer or the best answer because the only perfect algorithms that we know for those problems take a really, really long time.

3:43For example, let's say we want a program that would determine the most efficient route for a truck that delivers packages, starting and ending the day at a depot. It would take weeks to run going through all the possibilities. But if we're okay with a program that would determine a route that's good but maybe not the best, then it could run in seconds.

4:06In some case, good is good enough. How do you measure the efficiency of an algorithm? We could time how long it takes to run the code, but that would only tell us about that particular implementation in a certain programming language on a particular computer and just for the input it was given.

4:25Instead, computer scientists use a technique called asymptotic analysis, which allows algorithms to be compared independently of a particular programming language or hardware so that we can conclusively say that yes, some algorithms are more efficient than others.

4:41Now you can learn about algorithms and asymptotic analysis on Khan Academy thanks to the contribution of two Dartmouth college professors. Tom Cormen is the first author of the most popular college algorithms textbook in the world, plus the author of Algorithms Unlocked.

4:59Devin Balkcom designed Dartmouth's intro CS course and researches robotics. He built the world's first origami folding robot. Tom and Devin will teach you many of the algorithms that you would learn in APCS or CS 101, like searching algorithms, sorting algorithms, recursive algorithms and my personal favorite, graph algorithms.

5:19There will be tons of interactive visualizations, quizzes and coding challenges to help you understand better along your learning journey.