CompSci 100e: Program Design & Analysis II(Spring 2008)
| Home | Assignments | Bacon | How To |
Compsci 100e, Spring 2008, Degrees of Kevin Bacon
From Kevin's Wayne Small World Phenomenon Assignment. See the Bacon howto for complete information on the assignment.
Background
Six Degrees of Kevin Bacon started as drinking game invented by three
students at Albright College: Craig Fass, Mike
Ginelli, and Brian Turtle. From their book Six
Degrees of Kevin Bacon published in 1996:
The three of us came up with this game late one night at college. An advertisement for Kevin Bacon's most recent movie, The Air Up There, was playing on TV. Somehow this occurred to us: Kevin Bacon had been in so many different types of movies, it was possible to connect a lot of unlikely people together through his work.A lengthy thread on the rec.art.movies newsgroup titled, "Kevin Bacon is the Center of the Universe" discussed the many ways that one could connect actors and actresses to Kevin Bacon. Thankfully, the Web came along, and Brett Tjaden and Glenn Wasson created a website at the University of Virginia, so users can query any actor or actress's relation to Kevin Bacon oracleofbacon.org. Patrick Reynolds, Duke CS PhD 2006, ran the site since 1999. The site uses the Internet Movie Database to keep track of what movies actors and actresses have appeared in.
|
|
Overview
In this exercise, you will investigate the six degrees of Kevin Bacon. Two actors or actresses are linked if they appeared in a movie together. The Kevin Bacon number of an actor is the shortest chain of links that leads to Kevin Bacon. For example, Robert De Niro has a Kevin Bacon number of 1 because he appeared in Sleepers with Kevin Bacon. Elvis Presley's number is 2: although Elvis did not appear in any movie with Kevin Bacon, he was in Change of Habit with Edward Asner, and Asner appeared in JFK with Kevin Bacon. Your task is to:
- Read in a file containing a list of movies and the actors that appeared in them and compute the Kevin Bacon numbers for each actor.
- Write a method that for a given actor, it will print the shortest chain of movies that leads each actor back to Kevin Bacon.
Input Format
The Internet Movie Database regularly makes available plain text versions of its massive list of movies and casts. We include some smaller data files that include only a specific subset of movies, e.g., all movies released in 2000. Each line in the data file consists of a movie title, followed by a list of actors and actresses that appeared in that movie, delimited by the character '/'. Here is an abbreviated example from input8.txt:Movie 0/Bacon, Kevin/A Movie 1/A/B/C Movie 2/D/E/A/B Movie 3/E/F/G Movie 4/F/G/H Movie 5/H/I/J/K Movie 6/J/L/M/N Movie 7/A/B/C/D
Output Format
As noted above, you need to calculate the Bacon number for every actor or actress in the file. YourprintTable method should print out a table of the distribution of Kevin Bacon numbers.
Bacon number Frequency ------------------------- 0 1 1 1494 2 127791 3 239671 4 36475 5 2965 6 275 7 39 8 47 9 99 10 15 11 2 infinity 9703
Then, for each actor and actress passed into printChain, print out their Kevin Bacon number
and a shortest chain of movies that connect them to Kevin Bacon. Here's an example.
Dane, Cynthia has a Bacon number of 3 Dane, Cynthia was in "Solstice (1994)" with Scott, Dennis Scott, Dennis was in "What About Bob? (1991)" with Murray, Bill Murray, Bill was in "Wild Things (1998)" with Bacon, Kevin
Grading
The program is worth 20 points.| description | points |
|---|---|
| printTable | 25% |
| printChain | 25% |
| program style (class design/implementation, program design, robustness) | 25% |
| README, testing, efficiency | 25% |
Your README file should include the names of all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment. In addition, you should describe your implementation, how long it takes to run on different size files, and comparisons with other methods.
Submit your README and all of your source code using Eclipse with assignment name bacon.