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
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
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 upYou need to sign up for Treehouse in order to set up Workspace
Sign up