CS322 Fall 1997
Assignment 3

Due: 1:30pm, Friday 26 September 1997.

Question 1

rd(co(H,co(H,T)),T).
rd(co(A,T),co(A,R)) <-
   rd(T,R).

ask rd(co(a,co(co(a,X),co(B,co(c,co(d,em))))),W).

1. [2 marks] How many answers are there to this query? What are they (give just the values for the variables B and W in the answer)?

   Answer: There are two answers. One with B=co(a, X) and W=co(a,co(c,co(d,em))), and one with B=c and W=co(a, co(co(a, A), co(d, em))).

2. [5 marks] Give an SLD derivation showing all substitutions for one of the answers in the above query.

   Answer: The answer clause corresponding to the query is

   yes(X,B,W) <-rd(co(a,co(co(a,X),co(B,co(c,co(d,em))))),W)

   this can be resolved with a copy of the second clause:

   rd(co(A₁,T₁),co(A₁,R₁)) <-rd(T₁,R₁).

   using the substitution

   {A₁/a, T₁/co(co(a,X),co(B,co(c,co(d,em)))),W/co(a,R₁)}

   The resulting answer clause is

   yes(X,B,co(a,R₁)) <-rd(co(co(a,X),co(B,co(c,co(d,em)))),R₁)

   we can use a copy of the first clause

   rd(co(H₂,co(H₂,T₂)),T₂).

   with substitution

   H₂/co(a,X),B/co(a,X),T₂/co(c,co(d,em)),R₁/co(c,co(d,em))

   this results in answer clause

   yes(X,co(a,X),co(a,co(c,co(d,em)))) <-.

   which corresponds to the first answer above.
3. [3 marks] Give a failing derivation for this query.

   Answer Selecting the second clause instead of the first clause in the aove derivation, gives the answer clause clause

   yes(X,B,co(a,co(co(a,X),R₃))) <-rd(co(B,co(c,co(d,em))),R₃)

   selecting a copy of the second clause again results in the answer clause

   yes(X,B,co(a,co(co(a,X),co(B,R₄)))) <-rd(co(c,co(d,em)),R₄)

   selecting a copy of the second clause again results in the answer clause

   yes(X,B,co(a,co(co(a,X),co(B,co(c,R₅))))) <-rd(co(d,em),R₅)

   selecting a copy of the second clause again results in the answer clause

   yes(X,B,co(a,co(co(a,X),co(B,co(c,co(d,R₆)))))) <-rd(em,R₆)

   which fails because there are no applicable rules.

   Possible Alternative Answer: (although not as good as the first) Selecting the first rule on the initial query does not lead to a successful derivation as we can't unify rd(co(H₁,co(H₁,T₁)),T₁) with rd(co(a,co(co(a,X),co(B,co(c,co(d,em))))),W) as then H₁ would need to be replaced by both a and co(a,X) and these cannot be made the same.

Question 2

You should assume that the video is annotated using the relation

segment(SegId, Duration, Covers)

1. [7 marks] Axiomatize a predicate

   presentation(MustCover, Maxtime, Segments).
   

   That is true if Segments is a presentation whose total running time is less than or equal to Maxtime seconds, such that all of the topics in the list MustCover are covered by a segment in the presentation. The aim of this predicate is to design presentations that cover a certain number of topics within a time limit.

   Answer: I have three different solutions.

   For the first solution, a segment is chosen that covers the first topic, and all of the topics that this segment also covers are removed from the list of topics left to cover.

   The second solution is a directly recursive definition with no predicates defined other than in the question.

   The third solution uses an iterative method, where we define another predicate add_to_presentation that adds to existing an presentation to also include more topics. Presentation then asks to add the topics it must cover to an empty presentation.

   The fourth solution generates presentations that satisfy the length criterion, and then tests them to see if they cover all of the topics. This is the only one that defines more than one extra predicate.

2. [3 marks] Note that what is required for part 1 is reasonably straightforward. However, this example domain will be used for future assignments, so it is worthwhile thinking about what you may want in such a presentation design program.

   Assuming you have a good user interface and a way to actually view the presentations, list three things that the above program doesn't do that you may want in such a presentation system.

   [There is no right answer for this part, you need to be creative to get full marks]. Here are some ideas:

   • Maybe we want some measure of quality rather than just a time limit (e.g., we may want the shortest presentation).
   • We may want to return the best presentation first.
   • We may want a sensible order to the presentation. (The current versions don't worry about the order of the clips within a presentation).
   • We may want some continuity for the presentations; the video should flow, and be coherent.
   • What presentation a person wants may not only depend on what they are interested in, but what they already know about.
   • The terms used to describe the topics for the user may not necessarily match with the topics in the segments database. For example, they may just want something about CS research, in which case either computational intelligence or graphics would be OK. The system should do this automatically (the user needn't know that there is computational intelligence research going on).
   • There should still be a presentation if some topic cannot be covered. In this case we want the best presentation.
   • The user may not know what sorts of things are in the video, even though they may be interested in it. We would like to implement "give me an interesting video that matches what I am interested in".