**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

Preview

Start a free Courses trial

to watch this video

Earlier we looked at a generic definition of an algorithm. Let's dig deeper in this video and come up with a list of steps we need to fulfill to call our code an algorithm

#### Resources

In the last video, we ran through an
exercise where I had some of my coworkers
0:00

guess what number I was thinking.
0:04

So what was the point of that exercise?
0:06

You might be thinking, hey, I thought
I was here to learn about algorithms.
0:07

The exercise we just did was an example
of a real life situation you'll
0:11

run into when building websites,
apps, and writing code.
0:16

Both approaches taken by John and
0:20

Britney to find the number I was thinking
of are examples of searching for a value.
0:22

It might be weird to think that
there's more than one way to search.
0:28

But as you saw in the game,
0:31

the speed at which the result was obtained
differed between John and Britney.
0:32

Think about this problem from the
perspective of a company like Facebook.
0:37

At the time of this recording,
Facebook has 2.19 billion active users.
0:41

Let's say you're travelling
in a different country and
0:46

meet someone you want to add on Facebook.
0:49

You go into the search bar and
type out this person's name.
0:51

If we simplify how the Facebook app works,
it has to search across these
0:54

2.19 billion records and
find the person you are looking for.
0:59

The speed at which you find
this person really matters.
1:04

Imagine what kind of experience it
would be if, when you search for
1:07

a friend, Facebook put up
a spinning activity indicator and
1:11

said come back in a couple of hours.
1:15

I don't think we'd use Facebook
as much if that was the case.
1:17

From the company's perspective, working on
1:20

making search as fast as possible using
different strategies really matters.
1:23

Now I said that the two strategies Britney
and John used were examples of search.
1:28

More specifically,
these are search algorithms.
1:33

The strategy John took, where he started
at the beginning of the range and
1:36

just counted one number after the other,
is a type of search called linear search.
1:41

It is also called sequential search, which
is a better description of how it works.
1:46

Or even simple search,
since it really is quite simple.
1:51

But what makes his approach an algorithm
as opposed to just looking for something?
1:55

Remember, we said that
an algorithm is a set of steps or
2:00

instructions to complete a task.
2:03

Linear search is a search algorithm,
and we can define it like this.
2:06

We start at the beginning of the list or
the range of values.
2:10

Then we compare the current
value to the target.
2:14

If the current value is the target value
that we're looking for, we're done.
2:17

If it's not, we'll move on sequentially
to the next value in the list and
2:21

then repeat step two.
2:26

If we reach the end of the list,
then the target value is not in the list.
2:28

This definition has nothing
to do with programming, and
2:32

in fact you can use it in the real world.
2:36

For example, I could tell you
to walk into a book store and
2:38

find me a particular book.
2:41

And one of the ways you could do it
is using the linear search algorithm.
2:43

You could start at the front of
the bookstore and read the cover or
2:47

the spine of every book to check that it
matches the book that you're looking for.
2:50

If it doesn't, you go to the next book,
and repeat until you find it or
2:55

run out of books.
2:59

What makes this an algorithm is
the specificity of how it is defined.
3:00

In contrast to just jumping into
a problem and solving it as we go along,
3:06

an algorithm follows
a certain set of guidelines,
3:10

and we use the same steps to solve
the problem each time we face it.
3:14

An important first step to defining the
algorithm isn't the algorithm itself, but
3:18

the problem we're trying to solve.
3:22

Our first guideline is that an algorithm
must have a clear problem statement.
3:24

It's pretty hard to define an instruction
set when you don't have a clear idea of
3:30

what problem you're trying to solve.
3:34

In defining the problem, we need to
specify how the input is defined, and
3:36

what the output looks like when
the algorithm has done its job.
3:41

For linear search, the input can be
generally described as a series of values
3:44

and the output is a value matching
the one we're looking for.
3:49

Right now, we're trying to stay
away from anything code-related, so
3:53

this problem statement
definition is pretty generic.
3:56

But once we get to code,
we can actually tighten this up.
3:59

Once we have a problem, an algorithm is
a set of steps that solves this problem.
4:02

Given that, the next guideline is
that an algorithm definition must
4:07

contain a specific set of
instructions in a particular order.
4:12

We really need to be clear about the order
in which these instructions are executed.
4:16

Taking our simple definition of linear
search, if I switched up the order and
4:21

as I had moved sequentially to the next
value before specifying that first
4:26

comparison step.
4:30

If the first value were the target one,
our algorithm wouldn't find it because we
4:32

moved to the second
value before comparing.
4:36

Now you might think, okay,
that's just an avoidable mistake, and
4:38

kind of common sense.
4:42

The thing is, computers don't know any of
that and just do exactly as we tell them.
4:43

So a specific order is really important.
4:48

The third guideline is that each step
in our algorithm definition must not be
4:51

a complex one and
needs to be explicitly clear.
4:55

What I mean by that is that you
shouldn't be able to break down any of
4:58

the steps into further
into additional subtasks.
5:02

Each step needs to be a distinct one.
5:05

We can't define linear search as search
until you find this value because that can
5:08

be interpreted in many ways and
further broken down into many more steps.
5:12

It's not clear.
5:17

Next, and this one might seem obvious,
but algorithms should produce a result.
5:18

If it didn't, how would we know
whether the algorithm works or not?
5:24

To be able to verify that our algorithm
works correctly, we need a result.
5:28

Now, when using a search algorithm,
the end result can actually be nothing,
5:34

which indicates that
the value wasn't found.
5:37

But that's perfectly fine.
5:40

There are several ways to
represent nothing in code, and
5:42

as long as the algorithm can produce some
results, we can understand its behavior.
5:45

The last guideline is that the algorithm
should actually complete and
5:50

cannot take an infinite amount of time.
5:54

If we let John loose in
the world's largest library and
5:56

asked him to find a novel, we have no
way of knowing whether he succeeded or
6:00

not unless he came back
to us with a result.
6:04

Okay, so quick recap,
6:07

what makes an algorithm an algorithm and
not just something you do?
6:08

One, it needs to have a clearly defined
problem statement, input, and output.
6:13

When using linear search, the input
needs to be just a series of values.
6:18

But to actually use Britney's strategy,
there's one additional precondition, so
6:22

to speak.
6:27

If you think about her strategy,
6:28

it required that the numbers
be sorted in ascending order.
6:30

This means that where the input for
John is just a series of values,
6:33

to solve the problem,
6:37

the input to Britney's algorithm needs
to be a sorted series of values.
6:38

So clearly defined problem statement,
clearly defined input, and
6:42

clearly defined output.
6:47

Second, the steps in the algorithm
need to be in a very specific order.
6:49

The steps also need to be distinct,
6:54

you should not be able to break
it down into further subtasks.
6:56

Next, the algorithm
should produce a result.
7:00

And finally, the algorithm should
complete in a finite amount of time.
7:04

These guidelines not only help us
define what an algorithm is, but
7:09

also helps us verify that
the algorithm is correct.
7:13

Executing the steps in an algorithm for
7:17

a given input must result in
the same output every time.
7:20

If, in the game I played,
the answer was 50 every time,
7:24

then every single time John must take 50
turns to find out that the answer is 50.
7:28

If somehow he takes 50 turns
in one round then 30 the next,
7:34

then we technically don't
have a correct algorithm.
7:38

Consistent results for
7:42

the same set of values is how we
know that the algorithm is correct.
7:43

I should stress that we're not going to be
designing any algorithms on our own, and
7:48

we'll start off and spend most of
our time learning the tried and
7:52

true algorithms that are known
to efficiently solve problems.
7:56

The reason for talking about what
makes for a good algorithm, though,
7:59

is that these same set of guidelines
makes for good algorithmic thinking,
8:03

which is one of the most important
skills we want to cultivate.
8:07

When we encounter a problem, before
rushing in and thinking about solutions,
8:10

what we want to do is work
through the guidelines.
8:15

First we break down the problem into any
possible number of smaller problems,
8:18

where each problem can be clearly defined
in terms of an input and an output.
8:23

You need to sign up for Treehouse in order to download course files.

Sign up