CS322 Fall 1997
Assignment 4

Due: 1:30pm, Friday 3 October 1997.

Question 1

In this question we will investigate using graph searching to design video presentations.

Suppose we represent a node as the term

vp(To_Cover,Segs)
where Segs is a list of segments that must be in the presentation, and To_Cover is a list of topics that also must be covered, such that none of the segments in Segs covers any of the topics in To_Cover.

The neighbors of a node are obtained by first selecting a topic from To_Cover. There is a neighbor for each segment that covers the selected topic. [Part of this exercise is to think about the exact structure of these neighbors.]

For example, given the segment database (from Assignment 3), 

segment(seg0,10,[welcome]).
segment(seg1,30,[skiing,views]).
segment(seg2,50,[welcome,computational_intelligence,robots]).
segment(seg3,40,[graphics,dragons]).
segment(seg4,50,[skiing,robots]).
the neighbors of the node vp([welcome,robots],[]), assuming that welcome was selected, are vp([], [seg2]) and vp([robots], [seg0]).

Thus each arc adds exactly one segment, but can cover one or more topics. Suppose that the cost of the arc is equal to the time of the segment added.

Given that the goal is to design a presentation that covers all of the topics in MustCover, the starting node is vp(MustCover,[]), and the goal nodes are of the form vp([],Presentation). The length of the path from a start node to a goal node the time of the presentation. An optimal presentation is then the shortest presentation that covers all of the topics in MustCover.

  1. [6 marks] Suppose that the goal is to cover the topics [welcome,skiing,robots]. Suppose you always select the leftmost topic to find the neighbors for each node. Draw the search space expanded for a lowest-cost-first search until the first solution is found. This should show all nodes expanded, show which node is a goal node, and show the frontier when the goal was expanded.
  2. [6 marks] Give a non-trivial heuristic function h that is an underestimate of the real cost. [Note that h(n)=0 for all n is the trivial heuristic function.] Does it satisfy the monotone restriction for a heuristic function?

Question 2

The aim of this question is to get a bit more practice writing simple logic programs.
  1. [4 marks] Write a relation remove(E,L,R) that is true if R is the resulting list of removing one instance of E from list L. The relation is false if E isn't a member of L.

    What are all of the answers to the following queries: 

    ask  remove(a,[b,a,d,a],R).
ask  remove(E,[b,a,d,a],R).
ask  remove(E,L,[b,a,d]).
ask  remove(p(X),[a,p(a),p(p(a)),p(p(p(a)))],R).
  2. [4 marks] Write a relation subsequence(L1,L2) that is true if list L1 contains a subset of the elements of L2 in the same order.

    How many different proofs are there for each of the following queries: 

    ask  subsequence([a,d],[b,a,d,a]).
ask  subsequence([b,a],[b,a,d,a]).
ask  subsequence([X,Y],[b,a,d,a]).
ask  subsequence(S,[b,a,d,a]).
    Explain why there are that many.

Question 3

For each of the questions in this assignment, please estimate the amount of time you spent on it. What this a reasonable amount of time for one week in one course?

If you can, please recall how much time you spent on each of the previous assignments.