CS 4341 Homework #3 Solutions

Problem 1:

Exercise 9.1

Part 1.
Class-precedence list using topological sorting procedure:
        Crazy
        Professors
        Eccentrics
        Teachers  <-- procedure to be stored here
        Hackers   <-- procedure to be stored here
        Programmers
        Dwarfs
        Everything

Crazy's income will be low because the Teacher class appears before
the Hacker class in the class-precedence list.


Part 2.
Crazy's income will be erratic because the Eccentric class appears
before the Teacher and Hacker classes.

Problem 2:

Exercise 10.1.

Part 1.
Robbie grew plants with fertilizer.
thematic-role frames:
   agent:  Robbie
   verb:   grow
   instrument:  fertilizer
   thematic object:  plants 

Part 2.
action and state-change frames
action frame
   Primitive:  Move-object
   Agent:   Robbie
   Object:  fertilizer
   Destination:  plants
   Result:
        state-change frame
           Object:   plant's size
           Destination:  increase or adult

Problem 3:

Exercise 12.9.

Part 1.
If x and y are the same, and y is different from z, then x is
different from z.  

Part 2.
        Scientist       Lawyer          Manager
Pat     X,1             X,R5            I,R1
Terry   I,R1            X,5             X,R2
Lynn    X,R4            I,R3            X,R2

        Scientific      Business        Mercenary
        American        Week            World
Pat     X,R5            I,R1            X,2
Terry   I,R1            X,4             X,R5
Lynn    X,R3            X,R4            I,R2

          Scientific    Business        Mercenary
          American      Week            World
Scientist I,R3          X,R4            X,3
Lawyer    X,R4          X,6             I,R3
Manager   X,7           I,R1            X,8

Terry wants to be a scientist.

Problem 6:

Exercise 12.10. For each node B, there are at most (n-1)(n-2)/2 pairs of nodes A, C and links such that there is a link from A to B and B to C. Because there are are n possible such B nodes, reducing the link label count takes at most n(n-1)(n-2)/2 link pairs.

If looking at all nodes produces no change, then stop. On the other hand, each look may reducethe label count on only 1 link, and that may be just a one-link reduction. Each of the n(n-1)/2 links may have 13 labels, so the worst case is looking at all nodes 13n(n-1)/2 times, for a total of examining 13n(n-1)/2 (n-1)(n-2)/2 pairs of links. Thus, the worst case for examining pairs is O(n⁴).

CS 4341 Home Page

CS 4341 Homework

WPI CS Home Page

WPI Home Page