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

** Q1**

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?

** A1**

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.

** Q2**

Can we use other programs to write recursive programs in Part 2 and
Part 4?

** A2**

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.

** Q3**
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.

** Q4**
In Assignment 2: Are we allowed to use "is"?

** Q5**
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] ??

** Q6**
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?

** Q7**
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,

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=Xbut 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:

** Q8**

Are we supposed to test our implementation of the predicate
`mixElements` using variables in queries?

** A8**

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])`.

** Q9**

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.

** A9**

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)

** Q10**

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?

** A10**

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)

** Q11**

For the bonus questions, are we allowed to use Union for myUnion and
Intersection with myIntersection.

** A11**

No, your implementation can use only the predicates we
discussed in class, or do not use any extra predicates. See Q10/A10 above.

** Q12**

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?

** A12**

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.

** Q13**

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)`.

** A13**

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 / \ r4--1---r3 | / | \ 4 2 7 3 | / | \ r1--8--r2--2--r5 */ ?- 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 */

** Q14**

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.

** A14**

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.

** Q15**

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)`.

** A15**

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.

** Q16**

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?

** A16**

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.

** Q17**

** A17**

** Q18**

** A18**

** Q19**

** A19**

** Q20**

** A20**