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
In this video we're going to do something unusual - we're going to play a game where two of my friends try to guess a number. It's relevant, I promise!
This video doesn't have any notes.
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
Hey again.
0:00
In this video we're going
to do something unusual.
0:01
We're going to play a game, and by we,
I mean me and my two friends here,
0:03
Brittany and John.
0:07
This game is really simple, and
you may have played it before.
0:08
It goes something like this, I am going to
think of a number between 1 and 10, and
0:11
they have to guess what the number is.
0:15
Easy, right?
0:17
When they guess a number, I'll tell them
if their guess is too high or too low.
0:19
The winner is the one
with the fewest tries.
0:23
All right, John, let's start with you.
0:25
I'm thinking of a number between 1 and
10, what is it?
0:27
Between you and me, the answer is three.
0:30
JOHN: Quick question,
does the range include one and ten?
0:33
PASAN: That is a really good question, and so
0:36
what John did right there was to
establish the bounds of our problem.
0:38
No solution works on every problem, and an
important part of algorithmic thinking is
0:42
to clearly define what the problem set is
and clarify what values count as inputs.
0:46
Yeah, one and ten are both included.
0:51
JOHN: Is it one?
0:54
PASAN: Too low.
JOHN: Is it two?
0:55
PASAN: Too low.
0:56
JOHN: Is it three?
0:56
PASAN: Correct.
0:57
Okay, so that was an easy one.
0:58
It took John three tries
to get the answer.
1:00
Let's switch it over to Brittany and
1:03
play another round using
the same number as the answer.
1:04
Okay Brittany, I'm thinking of a number
between one and ten inclusive, so
1:07
both one and ten are in the range.
1:10
What number am I thinking of?
1:12
BRITTANY: Is it five?
1:13
PASAN: Too high.
1:14
BRITTANY: Two?
1:15
PASAN: Too low.
1:16
BRITTANY: Is it three?
1:16
PASAN: Correct.
1:17
All right, so
1:18
what we had there was two very different
ways of playing the same game.
1:19
Somehow, with even such a simple game,
1:24
we saw different approaches
to figuring out a solution.
1:26
To go back to algorithmic thinking for
1:29
a second, this means that with any given
problem, there's no one best solution.
1:31
Instead what we should try and figure
out is what solution works better for
1:36
the current problem.
1:40
In this first pass at the game they
both took the same amount of turns
1:42
to find the answer.
1:46
So it's not obvious who
has the better approach,
1:47
and that's mostly because
the game was easy.
1:49
Let's try this one more time,
now this time the answer is ten.
1:52
All right, John, you first.
1:56
JOHN: Is it one?
1:57
PASAN: Too low.
1:57
JOHN: Is it two?
1:58
PASAN: Still too low.
1:59
JOHN: Is it three?
2:00
PASAN: Too low.
2:00
JOHN: Is it four?
2:01
PASAN: Too low.
2:02
JOHN: Is it five?
2:02
PASAN: Still too low.
2:03
JOHN: Is it six?
2:04
PASAN: Too low.
2:04
JOHN: Is it seven?
2:05
PASAN: [LAUGH] Too low.
2:06
JOHN: Is it eight?
2:07
PASAN: [LAUGH] Too low.
2:07
JOHN: Is it nine?
2:08
PASAN: Too low.
2:09
JOHN: Is it ten?
2:10
PASAN: Correct, you got it.
2:10
Okay, so now same thing, but
with Brittany this time.
2:12
BRITTANY: Is it five?
2:15
PASAN: Too low.
2:17
BRITTANY: Eight?
PASAN: Too low.
2:18
BRITTANY: Is it nine?
2:19
PASAN: Still too low.
2:20
BRITTANY: It's ten.
2:21
PASAN: All right, so here we start to see
a difference between their strategies.
2:21
When the answer was three they both
took the same number of turns.
2:26
This is important.
2:29
When the number was larger, but
not that much larger, ten in this case,
2:31
we start to see that Brittany's
strategy did better.
2:35
She took four tries while John took 10.
2:38
We've played two rounds so far and
2:40
we've seen a different set of results
based on the number they were looking for.
2:42
If you look at John's way of doing things,
then the answer being ten,
2:46
the round we just played,
is his worst case scenario.
2:49
He will take the maximum number of turns,
ten, to guess it.
2:53
When we picked a random number like three,
it was hard to differentiate which
2:56
strategy was better, because they
both performed exactly the same, but
3:01
in John's worst case scenario a clear
winner in terms of strategy emerges.
3:06
In terms of algorithmic thinking, we're
starting to get a sense that the specific
3:10
value they're searching for
may not matter as much as where that value
3:15
lies in the range that
they have been given.
3:19
Identifying this helps us
understand our problem better.
3:22
Let's do this again for
a range of numbers from 1 to 100.
3:26
We'll start by picking five
as an answer to trick them.
3:29
Okay, so this time we're going to
run through the exercise again, but
3:32
this time from 1 to 100, and
both 1 and 100 are included.
3:35
JOHN: Is it one?
3:39
PASAN: At this point without even having to
run through it we can guess how many tries
3:40
John is going to take.
3:43
Since he starts at one and
3:44
keeps going he's going to take
five tries as we're about to see.
3:45
JOHN: Is it five?
3:48
PASAN: Cool, correct.
3:49
Okay, now for Brittany's turn.
3:49
BRITTANY: Is it 50?
3:51
PASAN: Too high.
3:53
BRITTANY: Is it 25?
3:54
PASAN: Still too high.
3:55
BRITTANY: Is it 13?
3:56
PASAN: Too high.
3:57
BRITTANY: Is it seven?
3:58
PASAN: Too high.
3:59
BRITTANY: Is it four?
4:00
PASAN: Too low.
4:01
BRITTANY: Is it six?
4:02
PASAN: Too high.
4:03
BRITTANY: Is it five?
4:04
PASAN: Correct.
4:06
Let's evaluate.
4:07
John took five tries, Brittany,
on the other hand, took seven tries.
4:08
So John wins this round, but again,
4:12
in determining whose strategy is preferred
there is no clear winner right now.
4:14
What this tells us is that it's
not particularly useful to look at
4:18
the easy answers where we arrive at
the number fairly quickly because it's at
4:22
the start of the range.
4:26
Instead, let's try one where we
know John is going to do poorly.
4:27
Let's look at his worse case
scenario where the answer is 100 and
4:31
see how Brittany performs
in such a scenario.
4:35
Okay, John, let's do this one more time,
1 through 100, again.
4:38
JOHN: Is it one?
4:41
PASAN: We can fast-forward this scene because,
well, we know what happens.
4:42
John takes 100 tries.
4:45
All right, Brittany, you're up.
4:47
BRITTANY: Is it 50?
4:49
PASAN: Too low.
4:50
BRITTANY: Is it 75?
4:51
PASAN: Too low.
4:52
BRITTANY: 88?
4:53
PASAN: Too low.
4:53
BRITTANY: 94?
4:54
PASAN: Too low.
4:55
BRITTANY: Is it 97?
4:56
PASAN: Too low.
4:57
BRITTANY: 99?
4:58
PASAN: Too low.
4:59
BRITTANY: 100.
5:00
PASAN: Okay, so
that took Brittany seven turns again, and
5:02
this time she is the clear winner.
5:05
If you compare their individual
performances for the same number set,
5:07
you'll see that Brittany's approach
leaves John's in the dust.
5:11
When the answer was five, so
5:14
right around the start of the range,
John took five turns, but
5:16
when the answer was 100, right at
the end of the range, he took 100 tries.
5:19
It took him 20 times the amount of tries
to get that answer compared to Brittany.
5:23
On the other hand,
if you compare Brittany's efforts,
5:28
when the number was five,
she took seven tries, but
5:31
when the number was one hundred,
she took the same amount of tries.
5:34
This is pretty impressive.
5:37
If we pretend that the number of tries is
the number of seconds it takes Brittany
5:38
and John to run through their attempts,
this is a good estimate for
5:43
how fast their solutions are.
5:46
Okay, we've done this a couple of times,
and Brittany and John are getting tired.
5:49
Let's take a break.
5:52
In the next video we'll talk
about the point of this exercise.
5:53
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