"CSS Basics (2014)" was retired on July 12, 2021. You are now viewing the recommended replacement.
Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Algorithms!
You have completed Introduction to Algorithms!
Preview
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