Hypercube - Intro to Algorithms Udacity English (auto-generated) English

Hypercube - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 13.8K views 86 likes 5 dislikes 29 Jun 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

the next kind of graph we're going to look at is called a hypercube and the

The next kind of graph we're going to look at is called a hypercube,

graph is almost but not quite as cool as

and the graph is almost but not quite as cool as the name.

the name so we're going to define a hypercube for any number of nodes as

We're going to define a hypercube for any number of nodes as long as

long as that number of nodes is a power

that number of nodes is a power of 2.

of two so here we have four nodes that's a power of two two squared and what

Here we have four nodes. That's a power of 2--2Â˛.

we're going to do is we're going to connect edges up in a particular way and

What we're going to do is we're going to connect edges up in a particular way.

this is how we're going to do it we're going to imagine that every node has a

This is how we're going to do it. We're going to imagine that every node has a label.

label and that label is a bit pattern in

That label is a bit pattern.

particular and we imagine that we're

In particular, we're going to imagine that we're going to number each of the nodes,

going to number each of the nodes basically from 0 up to n minus 1 and

basically, from 0 up to n - 1.

we're going to connect two nodes if their bit patterns differ in exactly one

We're going to connect two nodes if their bit patters differ in exactly one place.

place so we see this example here if we

We see this example here.

label the nodes these are now binary numbers 0 1 2 3 we connect these two nodes because they differ just in the first bit 1 1 0 1 we connect these two

If we label the nodes--these are now binary numbers 0, 1, 2, 3-- we connect these two nodes because they differ just in the first bit--11, 01.

because they differ in the second bit 1

We connect these two because they differ in the second bit--10, 11.

0 1 1 we connect these two because they differ in the second place 0 0 0 1 and

We connect these two because they differ in the second place--00, 01.

we connect these two because they differ in the first place 0 0 1 0 we can

And we connect these two because they differ in the first place--00, 10.

generalize this to larger graphs so

We can generalize this to larger graphs.

here's a hypercube on 8 nodes can we

Here's a hypercube on eight nodes.

number the nodes from 0 to 7 in their

We number the nodes from 0 to 7 in their binary bit patterns.

binary bit patterns and then we connect to nodes if they differ in exactly one

Then we connect two nodes if they differ in exactly one bit place.

bit place now we perhaps you can see why these are called hyper cubes this is a

Now, perhaps you can see why these are called hypercubes. This is a cube.

cube previous one was a square what's

The previous one was a square. What's the next one going to be?

the next one going to be so to generate the hypercube for n equals 16 and do this with a very very interesting little

To generate the hypercube for n = 16, we can do this with a very interesting little trick.

trick we're going to do is we're going to take two hyper cubes of size 8 and 8

What we're going to do is we're going to take two hypercubes of size 8 and 8.

now 8 and 8 is going to be 16 let's look

Now 8 and 8 is going to be 16. Let's look at what we can do.

what we can do we can leave these bit

We can leave these bit patterns the way that they are,

patterns the way that they are and then

and then we can extend them.

we can extend them everybody in this hypercube is going to

Everybody in this hypercube is going to get a 0 in front.

get a 0 out in front remember what that means in terms of the binary numbers is

Remember what that means in terms of the binary numbers is that they say the same.

they stay the same a leading 0 doesn't

A leading 0 doesn't change anything,

change anything but this second hypercube everyone's going to get a 1

but this second hypercube everyone is going to get a one out in front.

out in front again thinking about your

Again, thinking about your binary numbers, what is that doing?

binary numbers what is that doing it's adding 8 to all of the numbers of these

It's adding 8 to all of the number of these nodes,

nodes giving unique bit patterns that we

giving unique bit patterns that we haven't seen before.

haven't seen before and now if we connect the corresponding corners of

Now if we connect the corresponding corners of these two cubes,

these two cubes which is going to be a little bit messy and I can draw them

which is going to be a little bit messy, and I can draw them deeper,

deeper but it start to make the picture

but it'll start to make the picture a little distracting.

a little distracting that is a 4 dimensional cube also known as a

That is a 4-dimensional cube, also known as a hypercube.

hypercube we can keep extending this over and over again 5 bit pattern 6 bit pattern 7 2 patterns

We can keep extending this over and over again--5-bit patterns, 6-bit patterns, 7-bit patterns.

and each time what we're doing is connecting two hyper cubes of the

Each time what we're doing is connecting two hypercubes of the previous size,

previous size standing them and then connecting the corresponding vertices

extending them and then connecting the corresponding vertices.

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Eulerian Path - Intro to Algorithms
Udacity
55.8K views 144 likes 30 dislikes 27 Jun 2012100% match

DIY Como UNIR malla ROMBO ( metal desplegado ) #herreriasinsecretos
Leo Besson
7K views 357 likes 8 dislikes 26 Sep 202057% match

ORGANIZADOR DE CAJONES FACILISIMO. Organizer of drawers easy.
LOS TRUCOS DE JULIETA.
726.7K views 0 likes 0 dislikes 15 Nov 201357% match

SewaTT COVID-19 Release 6 - Up The Frequency - A film by Inspire (Original Film)
A Film by Sudarshan Motilal
3.2K views 180 likes 3 dislikes 29 Apr 202056% match

¿MURI0 en su CAMA? CASA ABANDONADA con Todo en Su Interior - Lugares Abandonados
Jaso Urbex
1.2M views 11.7K likes 1.6K dislikes 01 Dec 201756% match

Salsa Verde Taquera | Una salsa para disfrutar con tacos 🔥🌮
Zelecisne Recetas
2.4M views 46.5K likes -1 dislikes 12 Aug 202056% match

I Used FaZe JARVIS Settings for Fortnite SEASON 3 To See If I Get BANNED... (FreeJarvis!)
Hoop Baller
104.3K views 2.4K likes 56 dislikes 30 Jun 202056% match

a mysterious package has arrived
FinnyCardinal
1.2K views 13 likes 1 dislikes 08 Mar 202055% match

小倪趕海手拿一瓶鹽，吸引一窩又一窩的竹節蟶，都著急的往上鑽【小倪趕海】
Xiao Ni Ganhai
2.2K views 39 likes 1 dislikes 11 Nov 202055% match

How to make a homemade disc sander
Papa Manitas
828 views 79 likes 3 dislikes 28 Jul 202055% match

RECICLAR LOS ENVASES DE TUBO. Recycle the packaging of tube.
LOS TRUCOS DE JULIETA.
437.4K views 0 likes 0 dislikes 12 Dec 201355% match

常州88元碳火烤肉自助餐，牛肉五花肉都挺正宗，造就完了！【胖三疯】
Fat Three Mad
1.1K views 26 likes 3 dislikes 06 Nov 202055% match

Fall Harvest & Cook - Acorn and Mesquite
Chad Zuber
1.1M views 15.9K likes -1 dislikes 07 Dec 201955% match

What do we do when we have no water pressure - Michael, how do I ?
YouTube Michael
1.9K views 16 likes 3 dislikes 20 Jun 202055% match

Proyecto KARTING a motor 100% casero ( Parte 2 )
Leo Besson
3.9K views 214 likes 5 dislikes 21 Nov 202055% match

시간을 멈출 수 없나요??｜Can you stop time??｜ENG sub｜AMWF｜Korea Vlog
비카남편_vicashusband
4.8K views 353 likes 3 dislikes 28 Oct 202055% match

Example: 2-digit times 2-digit | Multiplication and division | Arithmetic | Khan Academy
Khan Academy
353.5K views 319 likes 44 dislikes 01 Aug 201054% match

0 views 0 likes -1 dislikes 04 Jun 202654% match

DIY Como Hacer una ESTUFA rusa de ACEITE quemado ( Waste oil stove)#estufasdebajocosto
Leo Besson
517.3K views 7.8K likes 351 dislikes 12 May 201854% match

Not My Legs Challenge - Gay Boyfriend Edition!
Dan Brai
908 views 41 likes 1 dislikes 05 Apr 201954% match

Now United & R3HAB - One Love (Official Music Video) | Reaction

45.8K views 4.4K likes 23 dislikes 13 Dec 202054% match

GTA V Como tener el Respirador Amarillo [RAPIDO] [PS4/XBOX ONE/PC]
Eduard Navarro
2.7K views 111 likes 3 dislikes 19 Oct 202054% match

70.3K views 0 likes 0 dislikes 04 Jun 202654% match

MY PET HAS A NAME! | We Are The Davises
We Are The Davises
120.9K views 1.5K likes 59 dislikes 04 May 201654% match

This is the most enjoyable way to eat carp. Add four eggs and steam it.
amazing dishes
14.8K views 55 likes 13 dislikes 02 Jan 202054% match

FOGONERO o Asador !! , súper completo !! #locosxelasado
Leo Besson
15.1K views 336 likes 5 dislikes 23 Dec 202054% match

تجربة غسل اليدين في المختبر
عش بصحة
900.5K views 131 likes -1 dislikes 13 Mar 202054% match

Nahidə Babaşlı Ses Analizi (Huzur Veren Ses)
Emre Yücelen Vocal Coach Istanbul (Online Education)
495.8K views 7.6K likes 366 dislikes 05 Dec 201854% match

This Miracle Herb Will Help Restore Your Back and Knees
Natural Cures
92K views 2.9K likes 75 dislikes 04 Apr 201954% match

Settings Privacy About Contact Donate