cps721: questions about the 2nd assignment.  

Questions related to the 2nd assignment

This page contains questions from students and my answers to them. If a question is asked that has already been answered, then I will not post another answer. So if your questions seems to go unanswered, you should check over previous questions.

Visit this Web page to download an open source version of ECLiPSe Prolog

I was wondering if rearranging elements in a list makes it different. For example if these two lists are equal [ l, i, m, e ] and [ m, i, l, e] or not? Does Prolog recognise them as equal lists?
Two lists are identical if they are identical element by element. So, the list [l, i, m, e] is different from [m, i, l, e] simply because their first elements are different. The head of [l,i,m,e] is the element l, but the head of [m,i,l,e] is the element m.

Can we use other programs to write recursive programs in Part 2 and Part 4?
You allowed to use only predicates member, append, last, first, length, sum that we discussed in class. But do not use them without reason. You are not allowed to use any other predicates from the system library or from the lecture notes. However, you can write rules for your own helping predicates (if it is really necessary). Whenever possible, try to write recursive rules directly (i.e., without using any other predicates). This will help you to practice how to write recursive programs.
In general, I would discourage the tendency to rely on the library predicates without prudence. I noticed that some cps721 students try to use library predicates all the time, even in cases when obviously a predicate can be easily defined in terms of itself. This often leads to confusion, and getting off the right track. For example, imagine someone who tries to implement length(List,N) or sum(List,S) using member(X,List) or append(L1,L2,List). We discussed in class that there are straightforward recursive implementations of length(List,N) or sum(List,S) that do not use any other predicates.

I keep getting an "instantiation fault in ... in module eclipse". Not sure how I can go about fixing that error. What do you suggest I do.
Start tkeclipse (ECLiPSe Prolog with a GUI). Click File/Compile to consult your program. Click Tools/Tracer: this opens a new "ECLiPSe Tracer" window with extensive facilities for debugging. Type a query in the main window and click "run". This activates your Tracer window. Click on "creep" each time to see execution of your program step-by-step. If you are not interested in some predicates (e.g., you know there is no bug there), you can click on "Skip" when execution gets to that predicate, but then keep clicking on "creep' to locate your error.

In Assignment 2: Are we allowed to use "is"?
You have to use   is   whenever you assign a value of an arithmetical expression to a variable. Your arithmetical expressions can be built from numbers, variables, and arbitrary arithmetical operators on them. Remember that when you write Z = 2 + 5 the value of the variable Z will not be 7, as you might expect, but it will be the string 2+5, i.e., the addition will not be performed. However, if you write

X is 2, Y is 5, Z is X + Y.
then the variable Z will be assigned the value 7. Note also, that if you write Z is 1+2, Z is 2 + 5 in your rule, then this conjunction is false, because once a variable Z got an arithmetical value 3 from the assignment 1 + 2, is cannot be assigned another value 7. However, if you write 6 is 2+4, then in this case the operator is works as =:=, and this expression is true, because the LHS is the number 6 equal to the value of the arithmetical expression on the RHS.

I have one question about the different ways of representing list. For e.g. [a|B] could that be converted to [a,B] given that B = [f], so you could replace B with [] there fore, [a|[f]] -> [a, f] or is it not allowed because [a|b] cannot be switched to [a,b] similarly, [a|B] cannot be [a, B] ??
If you have the list [a|[f]], then according to the vertical bar notation, this is the same as [a,f]. However, in a general case, if you have the list [X|Y], and you do not know what the variable Y stands for, then because the variables X and Y can match any list, you cannot re-write [X|Y] as [X,Y] simply because Y can be a list with arbitrary many elements, but when you write [X,Y] then it means that you have a list with 2 elements only: X and Y. For example, [X|[a,b,c]]=[X,a,b,c]. The lecture notes include many examples, read them carefully. Also, the quiz on lists included 6 pairs of lists.

For the Xth set in the first question, this was my answer: <...skip...> Two lists can be made identical by setting the correct variables. <...skip...> Ignoring the correctness of the answer, is this sufficient explanation to obtain full marks?
No this explanation is not good enough for several reasons. First, you start with stating an answer and it remains the mistery how did you guess it. Then, you use your answer to do transformations. This is not right. You have to do transformations using rules of the two list notations that we studied, going from the lists given to you to other intermediate lists, and then gradually go to a final syntactic form. The correct answer should emerge in the result of these transformations. Once you have transformed lists to similar syntactic forms, I always recommend to write one list above another, compare them element by element, and only from this comparison you can make a conclusion whether lists can be made identical strings or not, and if yes. what are the values of variables to make them identical. Second, you explanation is too cryptic and difficult to read. Write English words: it will be easier for a TA to mark this and see your line of reasoning. Remember that the 1st Part is about doing transformations between lists in general and demonstrating that you got skills of doing transformations. You can expect similar questions on tests.

I have a question regarding part I of the assignment. Generically, do these two lists match?

              [X, a] and [b, X]
Because to me, matching is.. for example, when you have a predicate, predicate([X, a]) in your knowledge base and you perform a query of the predicate ?- predicate([b, X]), this would return yes since the X in the query will be given the value a. So the X in the knowledge base will be different than the X in the query. So wouldn't these two lists match since the query can successfully call the predicate passing in the list as an argument? Or would they NOT match because X must be the same in both lists, even though one X is in the query and one X is in the predicate. I thought this process of matching the list with the argument in the predicate was the definiton of matching.
First of all, write these 2 lists one above another:
        [X , a]
        [b , X]
Now, if we match them element by element we can match the opening bracket in the top list with the opening bracket in the 2nd list. We can match X=b because a variable X can match anything. We can match commas in both lists too. Also, we can match the second elements in both lists a=X and the closing brackets. Once we have did matching, we got some equations that must have a solution if two lists are equal. In this case, we got 2 equations:
             X=b  and  a=X
but obviously it is not possible for X to be equal both to "a" and to "b" at the same time. Hence, these two lists do not match. Of course, if you have lists
        [X , a]
        [a , X]
then they will match: X=a in both cases. Similarly, in the example that you mentioned, predicate([X, a]) in a knowledge base cannot match the query ? - predicate([b, X]) because X cannot be both "a" and "b" at the same time.

Are we supposed to test our implementation of the predicate mixElements using variables in queries?
Yes, you have to make sure that your program can answer correctly queries like
?- mixElements(L1,L2,[1,2,3,4,5]).
?- mixElements(List,[2,4],[1,2,3,4,5]).

In Part 4 of the assignment, I'm just wondering what should happen for this query, trip(r1, r1, Path,Total)? And what should happen if Start, End, or both doesn't exist? Would the program need to handle those cases? Thanks.
Yes, your program should be able to answer queries correctly in all these cases that you mentioned. The predicate trip(Start,End,Path,Time) is true if and only if there exists a path on a given graph from Start to End and the variable Path lists all rooms on this path without cycles. See what my program answers about the rooms r8 and r9 that do not belong to the given graph:

?- trip(r1, r1, Path, Total).
Path = [r1]
Total = 0
Yes (0.00s cpu, solution 1, maybe more
?- trip(r8, r1, Path, Total).
No (0.00s cpu)
?- trip(r1, r9, Path, Total).
No (0.00s cpu)

Part 5 (bonus): should I implement permutation myself? If yes, what about the query permutation([a,b,b,c], [a,b,c,c]). This query should fail, right?
If you would like to use permutation in Part 5 (bonus question), then you have to implement it yourself. You cannot use any of the library predicates in this Bonus question, except of those we discussed in class. As for your query, you are correct: I tried this with my program and got the answer No. By the way, if I run the query that has a variable as the 2nd argument, and keep pressing "more" button, then I get all possible permutations, sometimes with repetitions. Note that repetitions are OK; eliminating repetiitons in answers is beyond this 2nd assignment.

?- permutation([a, b, b, c], X).
X = [a, b, b, c]
Yes (0.00s cpu, solution 1, maybe more)
X = [b, a, b, c]
Yes (0.03s cpu, solution 2, maybe more)
X = [b, b, a, c]
Yes (0.04s cpu, solution 3, maybe more)
X = [b, b, c, a]
Yes (0.06s cpu, solution 4, maybe more)
X = [a, b, b, c]
Yes (0.07s cpu, solution 5, maybe more)
X = [b, a, b, c]
Yes (0.08s cpu, solution 6, maybe more)
X = [b, b, a, c]
Yes (0.08s cpu, solution 7, maybe more)
X = [b, b, c, a]
Yes (0.09s cpu, solution 8, maybe more)
X = [a, b, c, b]
Yes (0.10s cpu, solution 9, maybe more)
X = [b, a, c, b]
Yes (0.11s cpu, solution 10, maybe more)
X = [b, c, a, b]
Yes (0.12s cpu, solution 11, maybe more)
X = [b, c, b, a]
Yes (0.12s cpu, solution 12, maybe more)
X = [a, b, c, b]
Yes (0.13s cpu, solution 13, maybe more)
X = [b, a, c, b]
Yes (0.14s cpu, solution 14, maybe more)
X = [b, c, a, b]
Yes (0.16s cpu, solution 15, maybe more)
X = [b, c, b, a]
Yes (0.17s cpu, solution 16, maybe more)
X = [a, c, b, b]
Yes (0.17s cpu, solution 17, maybe more)
X = [c, a, b, b]
Yes (0.18s cpu, solution 18, maybe more)
X = [c, b, a, b]
Yes (0.19s cpu, solution 19, maybe more)
X = [c, b, b, a]
Yes (0.20s cpu, solution 20, maybe more)
X = [a, c, b, b]
Yes (0.21s cpu, solution 21, maybe more)
X = [c, a, b, b]
Yes (0.22s cpu, solution 22, maybe more)
X = [c, b, a, b]
Yes (0.23s cpu, solution 23, maybe more)
X = [c, b, b, a]
Yes (0.24s cpu, solution 24)

For the bonus questions, are we allowed to use Union for myUnion and Intersection with myIntersection.
No, your implementation can use only the predicates we discussed in class, or do not use any extra predicates. See Q10/A10 above.

In question 2 of the assignment it says: "you may use (unless prohibited) any of the programs we wrote in class" Does that mean it is possible to write, for example, palindrome(List) without using any predicates other than palindrome itself recursively?
Yes, you have to write a correct recursive implementation of "palindrome" without using any of the library predicates. However, you may introduce your own helping predicates similar to what we did in class when we implemented reverse(List,RevList) using an accumulator technique.

For part 3, what level of functionality does the predicate trip need?
Does trip need to function with 1 unknown room or 2 unknown rooms? ie. trip(r1,X,Path,10) or trip(X,Y,Path,10).
Does trip need to function without a give a cost max? i.e. trip(r1,r6,Path,X).
First of all, make sure that all queries of the form "?- trip(r1,r6,Path,Time)." get correct answers. My program finds 8 correct paths from r1 to r6 that take time 8,9,11,14,19,21,22,24. The TA will be running queries with variables for Path and Time to test your program (on a different graph than the graph given to you). See the given graph reproduced below with ASCII graphics that you can use to verify answers you are getting. Second, if you are getting the right answers, then try queries with one of the rooms as a variable, or both initial and destination rooms as variables, see below.

/*     r6
       / \
      5   9
     /     \
    |    / | \
    4  2   7   3
    | /    |    \
?- trip(X, Y, Path, T), length(Path, 7).  
   No (0.00s cpu)   /* note there are only 6 rooms and repetitions are not allowed */
?- trip(X, Y, Path, 20).
X = r6
Y = r5
Path = [r6, r4, r1, r3, r2, r5]
        Yes (0.00s cpu, solution 1, maybe more)
X = r5
Y = r6
Path = [r5, r2, r3, r1, r4, r6]
        Yes (0.02s cpu, solution 2, maybe more)
        No (0.03s cpu)  /* This means there are only 2 solutions on a given graph */
?- trip(X, Y, Path, T), T =:= 4.
X = r1
Y = r4
Path = [r1, r4]
T = 4
        Yes (0.00s cpu, solution 1, maybe more)
X = r5
Y = r4
Path = [r5, r3, r4]
T = 4
        Yes (0.06s cpu, solution 2, maybe more)
X = r4
Y = r5
Path = [r4, r3, r5]
T = 4
        Yes (0.06s cpu, solution 3, maybe more)
X = r4
Y = r1
Path = [r4, r1]
T = 4
        Yes (0.08s cpu, solution 4, maybe more)
/* No more solutions */

In Part 3 of the assignment, are we allowed to assume an entry room that connects to all other rooms, for the purpose of having Path initialized to some value before we start using it.
No, you are not allowed to modify a given graph in any way. In particular, you cannot insert a new node (that you call "entry room"), that connects to all other rooms. Do your initialization in a different way. Remember that the base case should cover the simplest arrangements. You might wish to introduce your own helping predicate that you can use to do initialization. Of course, then the predicate "trip" should be implemented using your helping predicate (and possibly something else). Subsequently, you can implement your helping predicate: write a recursive program. The TA will be testing only the queries with the predicate "trip" (it serves as API to your program). The details of implementing your helping predicate(s) are up to you. Test your program using queries as explained in Q13/A13 above.

Bonus (Part 5): Are we assuming we get input for the two lists? That is my program won't be given myUnion([a,b,c],X,Y).
Yes, 2 input lists (representing sets) are expected and the program computes their union. Similarly, there is no need to answer queries like ?- myUnion([a,b,c],X,[c,b,a,1,2,3]) or ?- myUnion(Init, Last, [c, b, a]).
Note that input lists are intended to represent sets. But since sets cannot have repeated elements your implementation can assume that each element in the input lists occurs without repetitions, e.g.
?- myUnion([a, b, c, 1, 2], [3, 2, 1, b, a], [c,b,a,1,2,3]).
is fine, but the input (query)
?- myUnion([a, b, c], [1,3,2,1,2,3], [c,b,a,1,2,3]).
is not allowed.

For Q3 of the assignment, I know that we are not allowed to modify the original tree given by the query. However, are we allowed to send a copy of the tree to a helper predicate and modify that?
You are given a stationary graph representing rooms and corridors between them. It makes no sense to modify the given graph. The task of a program is to find paths from one room to another in a given graph. You can use a helper predicate to compute a path between two rooms, but then you have to implement your helping predicate.