Hi everybody! Welcome to CS 215. My name is Micheal Littman, and I’m going to be your instructor. Let’s get off with a little magic trick. All right! Here is a collection of actors from movies. This is Bruce Willis, Danny Devito, Cloris Leachman, Stanley Tucci, Tom Hanks, Haley Joel Osment, and Robin Williams. I’m going to connect together actors who were in movies together with lines that represents those movies. So Bruce Willis and Tom Hanks were in a movie together called, “The Bonfire of the Vanities” that seemed like it was going to be very good but it was not. Bruce Willis and Cloris Leachman were in a movie together called “Beavis and Butt-Head Do America”–it was not a very popular movie. Tom Hanks and Stanley Tucci were in a movie called “The Terminal.” Haley Joel Osment and Bruce Willis were in “The Sixth Sense.” They were the stars of that movie. I will not tell you the ending, but Haley Joel Osment was also in “Forrest Gump” with Tom Hanks. Robin Williams and Stanley Tucci were in a movie called “Deconstructing Harry.” Cloris Leachman and Stanley Tucci were in a movie called “Gambit”. Danny Devito and Robin Williams were in “Death to Smoochy.” All right! Next I’m going to connect Bruce Willis and Danny Devito, who were in a movie together called “I’m Still Here.” And lastly, I’m going to connect Bruce Willis and Stanley Tucci, who were in a movie called “Billy Bathgate.” All right! Now that we have the diagram, I’m going to start off with one of the actors. Let’s say Bruce Willis and I’m going to move around on this structure visiting all the movies exactly once and so let’s see how that goes. So there’s lot of different choices to start off. Let’s say, I’m going to go from Bruce Willis to Tom Hanks, Tom Hanks to Stanley Tucci, Stanley Tucci back to Bruce Willis, Bruce Willis to Cloris Leachman to Stanley Tucci again, to Robin Williams to Danny Devito to Bruce Willis to Haley Joel Osment, and then to Tom Hanks, and now you can see that I’ve visited all of the movies exactly once and I ended up at Tom Hanks. All right! So let’s try this again with a different set of actors. Now we’ve got Susan Sarandon, Dustin Hoffman, Julia Roberts, Kevin Bacon, Robert De Niro, Anne Hathaway, and Meryl Streep. And then we’re going to put in some of the movies again. Robert De Niro and Dustin Hoffman who were in a movie together called “Wag the Dog.” Robert De Niro and Meryl Streep were in a movie together called “Marvin’s Room.” Dustin Hoffman and Susan Sarandon were in a movie together called “Moonlight Mile.” Dustin Hoffman and Julia Roberts were in a movie together called “Hook.” Dustin Hoffman and Kevin Bacon were in a movie together called “Sleepers.” Susan Sarandon and Julia Roberts were in a movie together called “Stepmom.” Kevin Bacon and Julia Roberts were in “Flatliners.” Nobody can tell from some of the movies and the actors that I’ve picked that I watched more movies in the 80s than I watch now. Meryl Streep and Kevin Bacon were in a movie together called “The River Wild.” Meryl Streep and Anne Hathaway were in “The Devil Wears Prada” together. And Anne Hathaway and Julia Roberts were in “Valentines Day.” We’re going to do this as a little bit of a quiz so I’m going to mark each of these edges as something that you need to visit. You need to visit all of them. I strongly suggest that you actually check them off as you go because it’s really easy to do one twice or forget one by accident. So this is what I want you to do, I want you to go through and start at Meryl Streep and move along the green lines here at the movies and each time you visit a movie, check it off as you go. So the right answer in this quiz is to have all the edges checked off and none of them checked off twice. It’s really easy to mess that up, so be very careful. And then when you’re done, I want you to mark the little bubble corresponding to which actor you end up with at the end of your path. You can follow any path that you want–you just have to make sure that you visit each of the movies once. All right! I’d like you to actually go and do this and check off the actor that you end up with.