FHTW Berlin Fachbereich 4 Internationale Medieninformatik PROG2: Programmierung II Sommersemester 2003

 Finger exercises

1. Find an algorithm for determining the minimum path between two nodes in a directed graph. Check out algorithm books and the internet if you get stumped!
2. Your algorithm will probably need an adjacency matrix oder an adjacency list as its data structure. Think about how you would implement such a structure, if you only had linked lists available. What methods will you need for your data structure?

Lab exercises

Our goal is to write a program to determine an actor's Bacon number, which links a movie actor to Kevin Bacon via shared movie roles. (This is similar to the Erdös number for mathematicians). The minimum number of links is an actor's Bacon number. For instance, Tom Hanks has a Bacon number of 1, since he was in Apollo 13 with Kevin Bacon. Sally Field has a Bacon number of 2, because she was in Forrest Gump with Tom Hanks, but has not acted in a movie with Kevin Bacon (yet!).

Assume that you have a comprehensive list of actors with the movies they have played in. If you do not have such a list, make one up. You implementation of the algorithm does not care in which movies Kevin Bacon has played. It is only important to have a list of actors and a list of movies and some indication of which actors played in which movie.
 

1. Implement either an adjacency list or an adjacency matrix. What sort of information is going to be stored in nodes? A String? An Object?
2. Make up (or find on the net) a list of actors, movies, and actors who played in movies. Put this information in a file. What structure will you need for the file? Make up enough for it to be a good test of your algorithms!
3. Now write a class that will take a file name (or file names) as parameters to the constructor for the actor/movie information and construct a graph representing the information.
4. Now compute Bacon Numbers (or Hanks Numbers or Fields Numbers.... but they are not as much fun) for your graph and output the Bacon Numbers for all of your actors.
5. (for the bored) Find the movie actors database, and see if you can use that data for computing the Bacon number of, for example, Leonardo DiCaprio or Madonna!

Happy Bacon Hunting!