Main content

### Course: Computer science theory > Unit 1

Lesson 1: Intro to algorithms# What is an algorithm and why should you care?

## Want to join the conversation?

- Certainly, many algorithms are built complex and efficient by combining many algorithms into one (as one step may also be considered an algorithm, isn't it?..). But what I would like to ask - what are the algorithms considered to implement the biggest amount of advanced techniques in computational and/or natural sciences? Is it just based on the length of code? Is there a way to measure the complexity of an algorithm (despite the length of code it takes to describe)?(174 votes)
- All of your questions falls into what is called the computational complexity theory. There are two branches that are relevant to your questions: Parameterized complexity and complexity class. Essentially, they both classify algorithms. You can write volumes of books about these things, but I think it's better to read the Wikipedia articles about these:

https://en.wikipedia.org/wiki/Complexity_class, https://en.wikipedia.org/wiki/Computational_complexity_theory,

https://en.wikipedia.org/wiki/Parameterized_complexity.(110 votes)

- could you explain min-max algorithm and how to implement in a tic-tac-toe game ?(14 votes)
- It's a bit complicated. Here's an explanation:

http://web.stanford.edu/~msirota/soco/minimax.html(5 votes)

- Okay, just wanted to say this! I see a lot of people complaining about the speaker's voice, whether it is too fast or not understandable. But I don't have any problem! She speaks clearly in a normal North-American Accent and the speed is slow. It's perfect. And if it was they shouldn't be complaining about being too fast but being slow! Anyways, this is a great video, not the greatest, but a great one.(27 votes)
- click settings and choose a speed 0.25 0.5 0.75 1 1.25 1.5 1.75 2(16 votes)

- Hello.

Is it possible to practice Python somewhere at Khan Academy?

Thank you.

Have a nice day.(21 votes)- Unfortunately not. You can try Python Tutor: http://pythontutor.com/visualize.html#mode=edit(14 votes)

- "We hold these truths to be self evident that not all algorithms are equal "(21 votes)
- In a given problem, some algorithms are good, others are fine...

...and then we have Bogosort.(6 votes)

- Is it possible for amateurs to create complex algorithms to use in programs, or is it something that only professionals can accomplish after sitting and working on them for a really long time?(1 vote)
- Yes, codification is something you can learn with experience, like math. There are people who can simply un derstand code and algorithms without needing to be professional.(6 votes)

- What is Asymptotic analysis??

is it an software to analysis algorithm or procedure ??(9 votes)- Asymptotic analysis is a method we use to study and compare the performance of an algorithm (among other things).

It provides a way to talk about the performance of an algorith that doesn't depend on a particular problem, algorithm implementation or machine where it runs. It helps you to answer questions like:

- Is this a good algorithm?

- Is this the best possible algorithm?

- Which of these two algorithms is best?(8 votes)

- What would life be like without algorithms?(4 votes)
- I believe there exists an algorithm in order to find out. :)(10 votes)

- should i learn computer science first before starting to study computer programming?(3 votes)
- It depends. Some colleges have a computer programming degree and other colleges have only Computer Science degrees. I would recommend going into Computer Science because it gives a broader picture of this great industry. Computer science degrees do have computer programming and it is one of the major aspects in this degree (from the local colleges I know about) Also, many employers in this industry want a Computer Science degree instead of a computer programming degree. By doing the computer programming degree, in my opinion, you are limiting yourself from the wide variety of jobs that a Computer Science degree could bring.(8 votes)

- How do you know if you've written an incorrect algorithm?(4 votes)
- If it doesnt do the task you want it to do(5 votes)

## Video transcript

- [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. Algorithms 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? They 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? They 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. But 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. Well, 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. If 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. In 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. In 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. Most 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. For 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. In 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. Instead, 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. Now 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. Devin 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. There will be tons of
interactive visualizations, quizzes and coding challenges to help you understand better along your learning journey.