Reference no: EM132184351

Reading:

For this last assignment you can work alone or in pairs. If you work with someone else put both names in comments on the top of any files that you submit. Each of the two parts counts the same as a regular assignment. In addition, the solution to part 2 with the best running time will receive a bonus equal to the maximum score on a regular assignment, if the author(s) can clearly explain their solution to the class.

For many years people have been interested in the question of how connected social networks are. A famous experiment was carried out by Stanley Milgram in 1967. The experiment went something like this: Randomly chosen people in Omaha were given packets that included a letter addressed to a randomly chosen person in Boston. In the unlikely event that the resident of Omaha new the recipient, he was to send it directly. Otherwise, he was asked to select someone he knew who was more likely to know the recipient and send it on to them. The question: On average, how many intermediaries before the letter reached its final destination?

We can perform this type of experiment more easily nowadays using publicly available data, for example using the IMDB actor data. Let's say that if two actors worked on the same film, they are distance 1 apart. If actor 1 worked on a film with actor 2, and actor 2 worked on a film with actor 3, who worked on a film with actor 4, then we would say that the distance between actor 1 and actor 4 is 3 if there is no shorter path connecting them.

In this exercise we will work with the files actresses.list and actors.list, which contain, for each actor in the database, a list of movies the actor appeared in. Here is a typical entry:

Cronin, Doug (I) Chasing Dreams (1982) [Sheriff] <28>

Scared Straight! (1978)

The movie information comprises several items besides movie name (date, role, tv or film, order in credits, etc).
How would you store the data from actors.list in a Java program? You might start by writing a class to represent the data for a particular actor; lets call the class ActorRecord. This class should store the actor's name, and then a list of the movies that the actor has appeared in. We might also use a class to store the list of actors that appeared in a movie.

The actresses and actors files are quite large, and so we will work with compressed versions, actresses.list.gz and actors.list.gz, which are on Moodle and also in the common/GRAPHS directory on afs. Also in that subdirectory are several classes you can use, including RetrieveActors. The constructor takes a string argument that specifies the file from which to extract the actor data; you should give it the path name to actresses.list.gz and/or actors.list.gz. This class reads the compressed actor data without decompressing the entire file. It contains a method getNext() that returns a string for the next actor, or null if there are no more actor records in the file. The string comprises a list of strings separated by "@@@". The first string is the actor's name, and subsequent strings are the movies that the actor appeared in. Each movie string has two initial characters; a "TV" indicates that the title is a made-for-TV movie, a "TS" indicates a TV series or mini-series, a "VO" indicates a video, and "FM" indicates a film.

For example, the entry displayed above would be returned as

Cronin, Doug (I)@@@FMChasing Dreams (1982)@@@FMScared Straight! (1978)@@@

You do not need to be familiar with the details of how RetrieveActors works, or of the format of the IMDB files.

The program BusyActress.java reads in the data from actresses.list.gz and deter- mines which actress appeared in the most movies. If you go to your cs114 directory on afs, the command.

will copy all java files to your directory. You can then compile and run BusyActress without copying the actresses.list.gz file.

Write a program that creates a graph using the data in actresses.list.gz and actors.list.gz. You should have a vertex for each actor and an edge between two actors if they worked on a film together. (Consider only films; not tv shows or videos.) Choose your favorite actor, and compute the "distance" to each other actor. For each possible distance, give the number of actors that distance away (take the distance to be infinity if there is no path.) Use the graph classes on Moodle. That directory also contains a file shortestActors.list.gz, which is of the same format as the other actor files but with only 8 actors and 5 movies. You can check the distances you obtain with the solution in ActorsSmallWorld.pdf.

Call your program SmallWorld. For part 1 your program should work for short- estActors.list.gz. For part 2, tune your program so that it works with the combined data from actresses.list.gz and actors.list.gz. You may need to reevaluate your choices of data structures and algorithms to deal with the large data set. You may need to increase the memory size of the JVM; for example "java -Xmx16g Small- World". Use only algorithms and data structures (and your modifications) that we have covered in the course.

Here is the table for actress Hedy Lamarr based on all actresses and actors:

dist.	count
1	2,224
2	196,781
3	1,555,043
4	974,718
5	121,062
6	12,232
7	1,358
8	321
9	46
10	7
∞	1,287,288

Notes:

(1) In a January 1994 Premiere magazine interview about the film "The River Wild", Kevin Bacon commented that he had worked with everybody in Hollywood or someone who's worked with them. This claim attracted a lot of attention, even resulting in a parlor game called "Six Degrees of Kevin Bacon";.

(2) If you type in "bacon number name" in google, it will give you the "bacon number" of the name you enter, and also give you the path that results in that number. You can try checking your program with the results from Google, but you might get some different answers. If you are interested in the reason.

(3) In addition to appearing in many films, Hedy Lamarr (born Hedwig Eva Maria Kiesler in 1914, died 2000) patented (with George Antheil) a radio frequency hopping communications system that introduced some of the principles upon which modern wireless communications systems are based.

Exercises: (Not to turn in.)

(1) Use induction to prove that a (simple) graph tt = (V, E) has at most
V ( V 1) /2 edges.

(2) Suppose that you need to be able to quickly determine if two given vertices of a graph are connected by an edge. Which graph representation would you use, adjacency list or adjacency matrix? What are the time and space requirements?

(3) Consider a communications network that is a free tree; that is, a graph with no cycles. The time delay in a signal sent across a path is a small constant times the number of links in the path. Suppose that you want to determine the maximum possible delay in the network. The diameter of a tree T is the length of the longest path between two vertices of T. Describe an efficient algorithm for computing the diameter of T .

Attachment:- Problem set.rar