FHTW Berlin Fachbereich 4 Internationale Medieninformatik Info2: Informatik II Sommersemester 2006

 Finger exercises

1. Find an algorithm for determining the minimum path between two nodes in a directed graph. I strongly suggest visiting a library (that is one of these places that keeps ancient books around). There are Algorithm and Data Structure books available in many languages. There is also an example in the Wikipedia, but it is not really easy to understand.
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?
3. 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!

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. Bacon has played in upwards of 50 different films. 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. Do not spend hours trying to get a list of correct data or trying to access the International Movie Database (www.imdb.com) 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 a simple linked list class.
2. Implement either an adjacency list or an adjacency matrix. What sort of information is going to be stored in nodes? A String? An Object?
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. Test it with your file from the Pre-Lab.
4. Now compute Bacon Numbers (The bored can make their systems also calculate Hanks Numbers or Field 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) Make your program print out the path in a readable format. Are there multiple minimal paths? Print them all (this is *very* tricky!).
6. (For the Bored) Use your data structure to print out all of the persons with Bacon Number 1, then all with Bacon Number 2, etc.
7. (For the Curious) Doing singing and dancing GUIs for these exercises gets boring, doesn't it? So instead, note that there are a number of implementations for this algorithm on the Internet, and not all have to do with Kevin Bacon. There is a mathematician who wrote so many papers with so many colleagues, that people began bragging about having written a paper together with someone who wrote a paper together with..... whom? Find out who the mathematician was, and dig out some other interesting uses of this type of graph.

Happy Bacon Hunting! You can check out a solution from the University of Virginia at http://www.cs.virginia.edu/oracle/, but do not attempt to do this yourself, unless you are bored out of your skulls.