WEBVTT 00:00:00.000 --> 00:00:03.000 Hi everybody! Welcome to CS 215. 00:00:03.000 --> 00:00:06.000 My name is Micheal Littman, and I'm going to be your instructor. 00:00:06.000 --> 00:00:08.000 Let's get off with a little magic trick. 00:00:08.000 --> 00:00:12.000 All right! Here is a collection of actors from movies. 00:00:12.000 --> 00:00:18.000 This is Bruce Willis, Danny Devito, Cloris Leachman, Stanley Tucci, 00:00:18.000 --> 00:00:23.000 Tom Hanks, Haley Joel Osment, and Robin Williams. 00:00:23.000 --> 00:00:27.000 I'm going to connect together actors who were in movies together 00:00:27.000 --> 00:00:29.000 with lines that represents those movies. 00:00:29.000 --> 00:00:33.000 So Bruce Willis and Tom Hanks were in a movie together called, 00:00:33.000 --> 00:00:37.000 "The Bonfire of the Vanities" that seemed like it was going to be very good but it was not. 00:00:37.000 --> 00:00:40.000 Bruce Willis and Cloris Leachman were in a movie together 00:00:40.000 --> 00:00:44.000 called "Beavis and Butt-Head Do America"--it was not a very popular movie. 00:00:44.000 --> 00:00:49.000 Tom Hanks and Stanley Tucci were in a movie called "The Terminal." 00:00:49.000 --> 00:00:55.000 Haley Joel Osment and Bruce Willis were in "The Sixth Sense." They were the stars of that movie. 00:00:55.000 --> 00:00:57.000 I will not tell you the ending, but Haley Joel Osment 00:00:57.000 --> 00:01:01.000 was also in "Forrest Gump" with Tom Hanks. 00:01:01.000 --> 00:01:05.000 Robin Williams and Stanley Tucci were in a movie called "Deconstructing Harry." 00:01:05.000 --> 00:01:08.000 Cloris Leachman and Stanley Tucci were in a movie called "Gambit". 00:01:08.000 --> 00:01:11.000 Danny Devito and Robin Williams were in "Death to Smoochy." All right! 00:01:11.000 --> 00:01:14.000 Next I'm going to connect Bruce Willis and Danny Devito, 00:01:14.000 --> 00:01:17.000 who were in a movie together called "I'm Still Here." 00:01:17.000 --> 00:01:21.000 And lastly, I'm going to connect Bruce Willis and Stanley Tucci, 00:01:21.000 --> 00:01:23.000 who were in a movie called "Billy Bathgate." 00:01:23.000 --> 00:01:25.000 All right! Now that we have the diagram, I'm going to start off with one of the actors. 00:01:25.000 --> 00:01:30.000 Let's say Bruce Willis and I'm going to move around on this structure 00:01:30.000 --> 00:01:34.000 visiting all the movies exactly once and so let's see how that goes. 00:01:34.000 --> 00:01:36.000 So there's lot of different choices to start off. 00:01:36.000 --> 00:01:43.000 Let's say, I'm going to go from Bruce Willis to Tom Hanks, Tom Hanks to Stanley Tucci, 00:01:43.000 --> 00:01:51.000 Stanley Tucci back to Bruce Willis, Bruce Willis to Cloris Leachman to Stanley Tucci again, 00:01:51.000 --> 00:01:57.000 to Robin Williams to Danny Devito to Bruce Willis to Haley Joel Osment, 00:01:57.000 --> 00:02:01.000 and then to Tom Hanks, and now you can see that I've visited 00:02:01.000 --> 00:02:05.000 all of the movies exactly once and I ended up at Tom Hanks. 00:02:05.000 --> 00:02:07.000 All right! So let's try this again with a different set of actors. 00:02:07.000 --> 00:02:11.000 Now we've got Susan Sarandon, Dustin Hoffman, Julia Roberts, 00:02:11.000 --> 00:02:15.000 Kevin Bacon, Robert De Niro, Anne Hathaway, and Meryl Streep. 00:02:15.000 --> 00:02:17.000 And then we're going to put in some of the movies again. 00:02:17.000 --> 00:02:23.000 Robert De Niro and Dustin Hoffman who were in a movie together called "Wag the Dog." 00:02:23.000 --> 00:02:27.000 Robert De Niro and Meryl Streep were in a movie together called "Marvin's Room." 00:02:27.000 --> 00:02:30.000 Dustin Hoffman and Susan Sarandon were in a movie together called "Moonlight Mile." 00:02:30.000 --> 00:02:34.000 Dustin Hoffman and Julia Roberts were in a movie together called "Hook." 00:02:34.000 --> 00:02:38.000 Dustin Hoffman and Kevin Bacon were in a movie together called "Sleepers." 00:02:38.000 --> 00:02:41.000 Susan Sarandon and Julia Roberts were in a movie together called "Stepmom." 00:02:41.000 --> 00:02:45.000 Kevin Bacon and Julia Roberts were in "Flatliners." 00:02:45.000 --> 00:02:47.000 Nobody can tell from some of the movies and the actors 00:02:47.000 --> 00:02:50.000 that I've picked that I watched more movies in the 80s than I watch now. 00:02:50.000 --> 00:02:53.000 Meryl Streep and Kevin Bacon were in a movie together called "The River Wild." 00:02:53.000 --> 00:02:57.000 Meryl Streep and Anne Hathaway were in "The Devil Wears Prada" together. 00:02:57.000 --> 00:03:02.000 And Anne Hathaway and Julia Roberts were in "Valentines Day." 00:03:02.000 --> 00:03:05.000 We're going to do this as a little bit of a quiz so I'm going to mark 00:03:05.000 --> 00:03:08.000 each of these edges as something that you need to visit. 00:03:08.000 --> 00:03:10.000 You need to visit all of them. 00:03:10.000 --> 00:03:13.000 I strongly suggest that you actually check them off as you go 00:03:13.000 --> 00:03:16.000 because it's really easy to do one twice or forget one by accident. 00:03:16.000 --> 00:03:18.000 So this is what I want you to do, I want you to go through 00:03:18.000 --> 00:03:23.000 and start at Meryl Streep and move along the green lines here at the movies 00:03:23.000 --> 00:03:26.000 and each time you visit a movie, check it off as you go. 00:03:26.000 --> 00:03:28.000 So the right answer in this quiz is to have all the edges 00:03:28.000 --> 00:03:30.000 checked off and none of them checked off twice. 00:03:30.000 --> 00:03:33.000 It's really easy to mess that up, so be very careful. 00:03:33.000 --> 00:03:36.000 And then when you're done, I want you to mark the little bubble 00:03:36.000 --> 00:03:40.000 corresponding to which actor you end up with at the end of your path. 00:03:40.000 --> 00:03:42.000 You can follow any path that you want--you just have to make sure 00:03:42.000 --> 00:03:45.000 that you visit each of the movies once. 00:03:45.000 --> 00: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.