CSC 270
Homework 9

Assigned Dec. 1, due Dec. 15

1. Six Degrees of Kevin Bacon, continued

   Rewrite your degrees/3 predicate (from homework 8) so that it works for any positive integer, not only degrees 1 and 2.

   Test your definition by asking a variety of queries, with different combinations of bound and unbound arguments.

   (Getting this to work with the number bound, greater than 1, and one or both of the actors unbound is tricky; let's call it extra credit.)

   What happens if you ask about the "distance" between two actors who have two different connections, e.g. they appeared in two movies together, or they have both a degree-two connection and (through different movies and people) a degree-three connection? What do you think should happen in such situations?

   Extra credit: When people play "six degrees of Kevin Bacon", it's not good enough to say "Joe Schmoe is 4 degrees away from Kevin Bacon"; you have to prove it by giving a path from Joe Schmoe to Kevin Bacon, naming all the actors and movies along the way.
   Write a predicate named path/3 that works like degrees/3, except that its third argument is bound to a list rather than a number. For example,

   path(harrison_ford,kevin_bacon,Path).

   might return the answer

   Path = [harrison_ford,star_wars,carrie_fisher,blues_brothers,john_belushi,animal_house,kevin_bacon]

2. Binary search trees

   1. Design a Prolog data structure to represent a node in a binary search tree, as in section 14.2 of How to Design Programs. Each node must have a social security number, a name, a left subtree, and a right subtree.

      Build several example binary search trees, ranging from 0 to at least eight nodes. (You can memorize these in the rule database, e.g. by asserting a fact example_BST/1 with the tree as an argument; then you can later test all your examples easily by asking example_BST of an unbound variable.)

   2. Write a predicate search_bt/3 that searches a binary tree for a specified name and/or social security number. (Note that, with no extra effort, Prolog allows you to search by either name or social security number, without writing two separate functions as you would in Scheme, C++, or Java.)

      Test your definition by asking a variety of queries, with various combinations of bound and unbound arguments, about several example binary trees, searching for nodes that are at the root, that are higher up the tree, and that are not in the tree at all. Trace through a sample execution or two to confirm that it inspects all the nodes in the tree until it finds the right one (if it exists).

   3. Write a predicate search_bst/3 that does the same thing, but uses the ordering property of the binary search tree to search more efficiently (at least, if the social security number is specified).

      Test your definition by asking a variety of queries. Trace through a sample execution or two to confirm that it's only looking at a few nodes, not every node in the tree.

   4. Write a predicate insert_bst/4 that inserts a new name and social security number into an existing binary search tree, returning the resulting new BST in the remaining argument. You may assume that the first three arguments are bound. (What happens if they're not?)

      Test your definition by inserting several nodes in succession into a BST and checking that the result has all the right nodes in the right order.

   5. Write a predicate list_to_bst/2 that takes in a list of (name,ssn) pairs and produces a binary search tree containing them all. You may assume that the list argument is bound. (What happens if it's not?) You may choose your own representation for the (name,ssn) pairs, but be sure to document it clearly so I can test your program.

      Test your definition on several different lists.

   The assignment may be done in teams of two students, working together at one workstation much or all of the time. Each team should turn in one copy of the homework with both names on it. If more than two people turn in essentially the same program, I will consider it cheating and they will all be penalized, as stated in the syllabus.

   ---

   Last modified:
   Stephen Bloch / sbloch@adelphi.edu