0:00:00.000,0:00:03.000
Hi everybody! Welcome to CS 215.

0:00:03.000,0:00:06.000
My name is Micheal Littman, and I'm going to be your instructor.

0:00:06.000,0:00:08.000
Let's get off with a little magic trick.

0:00:08.000,0:00:12.000
All right! Here is a collection of actors from movies.

0:00:12.000,0:00:18.000
This is Bruce Willis, Danny Devito, Cloris Leachman, Stanley Tucci,

0:00:18.000,0:00:23.000
Tom Hanks, Haley Joel Osment, and Robin Williams.

0:00:23.000,0:00:27.000
I'm going to connect together actors who were in movies together

0:00:27.000,0:00:29.000
with lines that represents those movies.

0:00:29.000,0:00:33.000
So Bruce Willis and Tom Hanks were in a movie together called,

0:00:33.000,0:00:37.000
"The Bonfire of the Vanities" that seemed like it was going to be very good but it was not.

0:00:37.000,0:00:40.000
Bruce Willis and Cloris Leachman were in a movie together

0:00:40.000,0:00:44.000
called "Beavis and Butt-Head Do America"--it was not a very popular movie.

0:00:44.000,0:00:49.000
Tom Hanks and Stanley Tucci were in a movie called "The Terminal."

0:00:49.000,0:00:55.000
Haley Joel Osment and Bruce Willis were in "The Sixth Sense." They were the stars of that movie.

0:00:55.000,0:00:57.000
I will not tell you the ending, but Haley Joel Osment

0:00:57.000,0:01:01.000
was also in "Forrest Gump" with Tom Hanks.

0:01:01.000,0:01:05.000
Robin Williams and Stanley Tucci were in a movie called "Deconstructing Harry."

0:01:05.000,0:01:08.000
Cloris Leachman and Stanley Tucci were in a movie called "Gambit".

0:01:08.000,0:01:11.000
Danny Devito and Robin Williams were in "Death to Smoochy." All right!

0:01:11.000,0:01:14.000
Next I'm going to connect Bruce Willis and Danny Devito,

0:01:14.000,0:01:17.000
who were in a movie together called "I'm Still Here."

0:01:17.000,0:01:21.000
And lastly, I'm going to connect Bruce Willis and Stanley Tucci,

0:01:21.000,0:01:23.000
who were in a movie called "Billy Bathgate."

0:01:23.000,0:01:25.000
All right! Now that we have the diagram, I'm going to start off with one of the actors.

0:01:25.000,0:01:30.000
Let's say Bruce Willis and I'm going to move around on this structure

0:01:30.000,0:01:34.000
visiting all the movies exactly once and so let's see how that goes.

0:01:34.000,0:01:36.000
So there's lot of different choices to start off.

0:01:36.000,0:01:43.000
Let's say, I'm going to go from Bruce Willis to Tom Hanks, Tom Hanks to Stanley Tucci,

0:01:43.000,0:01:51.000
Stanley Tucci back to Bruce Willis, Bruce Willis to Cloris Leachman to Stanley Tucci again,

0:01:51.000,0:01:57.000
to Robin Williams to Danny Devito to Bruce Willis to Haley Joel Osment,

0:01:57.000,0:02:01.000
and then to Tom Hanks, and now you can see that I've visited

0:02:01.000,0:02:05.000
all of the movies exactly once and I ended up at Tom Hanks.

0:02:05.000,0:02:07.000
All right! So let's try this again with a different set of actors.

0:02:07.000,0:02:11.000
Now we've got Susan Sarandon, Dustin Hoffman, Julia Roberts,

0:02:11.000,0:02:15.000
Kevin Bacon, Robert De Niro, Anne Hathaway, and Meryl Streep.

0:02:15.000,0:02:17.000
And then we're going to put in some of the movies again.

0:02:17.000,0:02:23.000
Robert De Niro and Dustin Hoffman who were in a movie together called "Wag the Dog."

0:02:23.000,0:02:27.000
Robert De Niro and Meryl Streep were in a movie together called "Marvin's Room."

0:02:27.000,0:02:30.000
Dustin Hoffman and Susan Sarandon were in a movie together called "Moonlight Mile."

0:02:30.000,0:02:34.000
Dustin Hoffman and Julia Roberts were in a movie together called "Hook."

0:02:34.000,0:02:38.000
Dustin Hoffman and Kevin Bacon were in a movie together called "Sleepers."

0:02:38.000,0:02:41.000
Susan Sarandon and Julia Roberts were in a movie together called "Stepmom."

0:02:41.000,0:02:45.000
Kevin Bacon and Julia Roberts were in "Flatliners."

0:02:45.000,0:02:47.000
Nobody can tell from some of the movies and the actors

0:02:47.000,0:02:50.000
that I've picked that I watched more movies in the 80s than I watch now.

0:02:50.000,0:02:53.000
Meryl Streep and Kevin Bacon were in a movie together called "The River Wild."

0:02:53.000,0:02:57.000
Meryl Streep and Anne Hathaway were in "The Devil Wears Prada" together.

0:02:57.000,0:03:02.000
And Anne Hathaway and Julia Roberts were in "Valentines Day."

0:03:02.000,0:03:05.000
We're going to do this as a little bit of a quiz so I'm going to mark

0:03:05.000,0:03:08.000
each of these edges as something that you need to visit.

0:03:08.000,0:03:10.000
You need to visit all of them.

0:03:10.000,0:03:13.000
I strongly suggest that you actually check them off as you go

0:03:13.000,0:03:16.000
because it's really easy to do one twice or forget one by accident.

0:03:16.000,0:03:18.000
So this is what I want you to do, I want you to go through

0:03:18.000,0:03:23.000
and start at Meryl Streep and move along the green lines here at the movies

0:03:23.000,0:03:26.000
and each time you visit a movie, check it off as you go.

0:03:26.000,0:03:28.000
So the right answer in this quiz is to have all the edges

0:03:28.000,0:03:30.000
checked off and none of them checked off twice.

0:03:30.000,0:03:33.000
It's really easy to mess that up, so be very careful.

0:03:33.000,0:03:36.000
And then when you're done, I want you to mark the little bubble

0:03:36.000,0:03:40.000
corresponding to which actor you end up with at the end of your path.

0:03:40.000,0:03:42.000
You can follow any path that you want--you just have to make sure

0:03:42.000,0:03:45.000
that you visit each of the movies once.

0:03:45.000,0:03:49.000
All right! I'd like you to actually go and do this and check off the actor that you end up with.