Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic 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

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

0:04
guess what number I was thinking.

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

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

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

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

0:20
Both approaches taken by John and

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

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

0:31
But as you saw in the game,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1:33
More specifically, these are search algorithms.

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

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

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

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

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

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

2:03
instructions to complete a task.

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

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

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

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

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

2:26
then repeat step two.

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

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

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

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

2:41
find me a particular book.

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

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

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

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

2:59
run out of books.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3:56
this problem statement definition is pretty generic.

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

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

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

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

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

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

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

4:30
comparison step.

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

4:36
moved to the second value before comparing.

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

4:42
kind of common sense.

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

4:48
So a specific order is really important.

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

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

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

5:02
the steps into further into additional subtasks.

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

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

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

5:17
It's not clear.

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

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

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

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

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

5:40
But that's perfectly fine.

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

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

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

5:54
cannot take an infinite amount of time.

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

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

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

6:07
Okay, so quick recap,

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

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

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

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

6:27
to speak.

6:28
If you think about her strategy,

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

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

6:37
to solve the problem,

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

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

6:47
clearly defined output.

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

6:54
The steps also need to be distinct,

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

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

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

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

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

7:17
Executing the steps in an algorithm for

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

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

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

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

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

7:42
Consistent results for

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

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

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

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

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

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

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

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

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

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

8:23
where each problem can be clearly defined in terms of an input and an output.
You need to sign up for Treehouse in order to download course files.
Sign up