
Title:
1122 Smart Search Tree

Description:

We started out with a brute force algorithm,

and the brute force algorithm basically considered 2 to the power of N assignments.

Now let's look at our smart search tree or intelligent search tree

and see how that is structured.

We're going to do a worst case analysis here.

We start out with a graph where we don't have any assignments,

and then we branch into 3 different possibilities.

Up here we don't know anything, so we have 0 vertices assigned.

Now, since we know that we can construct it

so that in the next level we will have at least 2 more vertices assigned,

here we know that we have at least 2 vertices assigned.

We can go 1 level deeper and again we will branch into 3 possibilities all of the time.

Because we're doing a worst case analysis, of course we could already be done.

Or let's say we just continue.

In the next level we have again at least 2 more,

so we have at least 4 vertices assigned and so on.

So let's say we continue the search tree in this manner,

so we will always get wider and wider and wider.

Then we know 2 things.

One is that the number of levels that we have can be, at most, N/2

because every time we assign at least 2 vertices.

So N and a half levels is the maximum number of levels that we can have

because after that, all vertices have been assigned.

And another thing that we know is that while we start out with 1 possibility

and each time we go 1 level deeper, again doing a worse case analysis here,

the number of possibilities that we consider triples.

The tree basically gets wider by a factor of 3.

The width is times 3 at each level.

My question for you is if you look at the lowest level of the search tree,

each of these ones down here is an assignment of 0 and 1 to the vertices.

What I would like you to think about is how many different assignments

do we have at this level down here, level N/2?

You can assume for simplicity that N is an even number, so N/2 will be some integer.

I'll give you a number of choices.

Is it 2 to the power of N assignments that we have down here?

Is it 3 to the power of N/2 assignments that we have down here?

Is it 3 to the power of N? Is it 2 to the power of 3 times N?

Or is it 2 to the power of N/2 times 3?

You might have to think about this for a little bit,

but just keep in mind the facts.

The number of assignments that we are considering triples at each level,

and we have N and a half levels.