Homework Assignment 5

CS 2360
Spring 1996
Homework Assignment 5
Due no later than 8:00am, Monday, May 6, 1996


"Savannah" (which, by the way, is filmed entirely on location in 
Atlanta...go figure) is the story of three young women: Lane, Reese, 
and Peyton.  These three have been the closest of friends since 
childhood, and their friendship continues to this day, although it's 
not clear how long that's going to last.  Reese is the spoiled 
daughter of Savannah zillionaire Edward Burton.  Lane is an aspiring 
journalist who has lost her job at the subscription desk of the New 
York Times and who is now working as the cub crime reporter for the 
local newspaper.  Peyton is a cocktail waitress and also the daughter 
of Lucille, who has been Edward Burton's loyal housekeeper for many 
years and a surrogate mom to Reese, whose real mom passed away quite 
a few years ago.  Got it so far?  Good, because now it gets real 
weird.

Reese was engaged to, and subsequently married, Travis, a hunky low-
life account manager at the bank.  Travis is only after Reese's (and 
her daddy's) money, and has been fooling around (interpret that 
however you want to) with Peyton, who expects to marry Travis after 
he divorces Reese and walks away with half of everything she has.  
But Peyton has found out that Travis has been lying to her and 
doesn't intend to divorce Reese, so Peyton anonymously reveals to 
Reese that Travis is a sleazeoid (without revealing that Peyton has 
been a participant in the sleaze).  This of course drives a bit of a 
wedge between Reese and Travis, who figures out that Peyton is the 
root of his current problem.  Travis gets drunk and starts to slap 
Peyton around a bit, but Peyton clonks him on the head with a bottle.
It's lights out for Travis, apparently permanently, but more on that 
later.

Along the way, our cub reporter, Lane, finds out that the money that 
she had given Travis to manage has been embezzled.  She seeks the 
help of Savannah police detective, and former boyfriend, Dean.  Dean 
helps Lane find out that Travis is in fact the embezzler, and Lane 
and Dean start to get cozy, much to the dismay of Dean's estranged 
and somewhat crazed wife Janie (I'm not sure if this is the right 
name, but since you don't watch the show, who really cares?).  Janie 
has something going on the side with some guy in Augusta, but who 
knows where that thread is going?

Back to Peyton and Travis...Peyton plans to dump Travis's body in the 
Savannah River, but before she can get the job done, the body 
disappears.  Later the police find the body in the river, and they
arrest...Lane!  Why?  Because blabbermouth Dean knows that Travis 
stole Lane's money, giving Lane what every TV crime needs...a motive.  
But motive is what you use when you don't have evidence, which the 
police later find in an automobile driven by...LUCILLE!!  Yes, it 
looks like Peyton's mom actually snuffed Travis, who was only stunned 
when his head stopped Peyton's bottle.  Well, to make a long story 
even longer, Lucille is acquitted.  I forget why, exactly, but it has 
something to do with the fact that she and Edward Burton had a fling 
way back when, and that fling resulted in Peyton...yes, Peyton is 
Reese's half-sister!!!  Nevertheless, Lucille can't live with herself 
knowing that she killed Travis but isn't suffering in prison for it, 
so she's on the verge of suicide.  The question hanging over the 
constant viewer's head right now (there have been nothing but reruns 
for the past three weeks) is whether Travis's apparent return from 
the dead (yes, really, trust me) will stop Lucille from pulling that 
trigger.

Where do you come in?  Well, those crazy people at the Institute for 
Television Research want you to create a knowledge base for the 
characters in "Savannah" so that they can keep track of the 
relationships between the characters.  They want you to construct a 
relational network not unlike those for the classic show "Twin 
Peaks".  Your network should capture generalizations and abstract 
away unimportant detail.  It should be easily understood and easily 
modified, and it should be useable in many situations, possibly at 
the expense of complete accuracy.

Then you are to write a function (or functions) which searches for a
relationship between any two characters in "Savannah", no matter how 
distant that relationship might be.  The top-level function is to be 
called "show-relationship-dfs", and this function will take three 
arguments.  The first two arguments are the names of two people who 
may be somehow related.  The third argument should be the "Savannah" 
knowledge base.

To implement this, use a depth-first search algorithm.  But remember 
that this data structure isn't a tree.  That is, this data structure 
has cycles, which means you have to figure out how to keep your 
program from searching around and around through the same cycle.  
Also, it won't be enough to just return T when you find a 
relationship between two "Savannah" inhabitants--you'll have to 
return a list of the labels on the "nodes" and "links" joining the 
two inhabitants.  For example,

? (show-relationship-dfs 'peyton 'reese *knowledge-base*)

might return

(PEYTON HAS-FRIEND REESE)

or it might return

(PEYTON HAS-FATHER EDWARD_BURTON FATHER-OF REESE)

or it might return yet another relationship, depending on what you 
put into your knowledge base.  For any two people, there may be many 
ways of describing relationships between them.  Your depth-first 
search approach to this problem need only return the first one it 
finds.

After you've completed "show-relationship-dfs", construct "show-
relationship-bfs" which, as you might guess, will employ a breadth-
first search algorithm.  The input and the output will be the same, 
except that "show-relationship-bfs" will always return the shortest 
path or relationship between any two people.  If there are multiple 
"shortest" paths, just have your function return any one of them.

Make sure that your program is the pinnacle of good design, good 
documentation, and good abstraction.  Take advantage of what you 
learned in Assignment 4.  And as always, when it comes to grading 
this thing, there will be as much emphasis on how well we understand 
what you were trying to do as there will be on how well the program 
works.  I'll be thinking of you Sunday night while I'm watching 
"Savannah" and you're wrestling with this assignment.



Copyright 1996 by Kurt Eiselt.  All rights reserved.