Questions related to the 1st 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. You can send email only from your Ryerson address: read the CMF for details about all course policies.

Q1
I was just wondering if its ok to work on the assignments with people from other sections?
A1
You can work on the assignments with students from any section, but the number of people in a team must be less than or equal to 3.

Q2
I was wondering where I can find the handouts you were using in class.
A2
Take notes in class: write down the most important definitions and ideas. Also, copy all notes that I write on the board. A PDF copy of overheads that I use in class is available from D2L.

Q3
I was wondering if you want us to buy all 3 textbooks, and if so, do you have some sort of recommended readings/chapters for each book that relates to this course, or do you expect us to read both the entire books?
A3
As I mentioned in class, you have to read only Levesque's textbook. I recommend sections and chapters to read in my notes on D2L. When you'll complete this cps721 course, and if you would like to read more about AI, you can buy one of the recommended books as a supplementary reading, e.g., Russell and Norvig's book. Note that some sections of this book assume that the reader has a certain level of mathematical maturity. If you really want to learn more about AI, then you might wish to browse some of the suggested extra-curriculum materials, but this is not required.

Q4
Can we use the symbol ";" (OR symbol) in the bodies of our rules or in our queries?
A4
No, you are not allowed to use ";" and you also are not allowed to use commands "->" and "!" when you work on your assignments. Note that any rule with disjunction (i.e., with ";") in its body can be written as a couple of rules with the same predicate in the head, but with one disjunct per body. Similarly, you never need to use the disjunction symbol ";" in your queries. As we discussed in class, using De Morgan's rule, a query with disjunction ("or") can be equivalently reformulated using only conjunction ("and") and negation ("not").

Q5
Can we use anonymous variables (underscore) in our queries?
A5
No, to avoid confusion, please try using named variables only to formulate queries as it was discussed in class. Simply write a named variable starting with a capital letter even if a variable is somewhat irrelevent to a query. The "anonymous variables" (underscore symbols) would be beyond the scope of the 1st assignment.

Q6
In Part 1 of the assignment, queries 9 and 10 are difficult to write in Prolog. Can I write them using rules with recursion? If not, please give me a hint on how can I write these queries.
A6
In Part 1, you can write queries only. So, you are not allowed to write any rules (recursive, or otherwise). If you cannot formulate quires 9 and 10 in Prolog directly, think how can you reformulate them in English so that the reformulated query is easy to express in Prolog. Make sure that you do logically equivalent transformation when you transform one logical statement in English into another statement in English before you encode it in Prolog.

Q7
I'm getting a strange error when I try to test my Prolog program. It says:

*** Overflow of the local/control stack!
If this is not okay, is there a way to fix it?
A7
Usually, this error occurs when your program starts making too many recursive calls. So, when you are testing your program, your rules are probably written so that predicates in the heads have several mutual recursive dependencies. As a consequence, back-chaining invokes same predicates (with different variables) again and again, until the recursive calls overflow the stack. To fix this problem, you can change the order of rules, re-write the rules by rearranging the predicates in their bodies, or place atomic statements on top. These are the main recipies to fix problems with recursion in a Prolog program. See the Handout with a related example discussed in class. This example demonstrates that if the body of the rule starts with a recursive call, this may easily lead to the problem.

Q8
Can we use ; (or more) to list all tickets and find the least expensive ticket ourselves in Q9 ?
A8
No, you have to formulate a clever query, that will search through the whole database and will retrieve itself the price of the least expensive ticket no matter how large is KB. When you formulate this query, you can use only the predicates given to you, conjunction, negation, variables and constants.

Q9
I have a quick question about the first assignment, Part 1, Query 1. I am not sure whether you want us to actually check whether such a flight exists, or to simply assume it does in the KB. (... skip ...) In (1) i ask if such a flight exists, then find the price of said flight, but in the alternate answer i know such a flight exits in the KB so i simply ask for the price of that flight. I am unsure how you intended me to answer the question.
A9
Your Prolog query should be faithful rendering of an English query no matter what is included in your KB. The 2nd version is not ok, because it uses specific dates 918 and 922, that are not mentioned in the English query. Imagine that one person inputs data into a KB. Another person (an user) queries KB without knowing what is inside; if the 2nd person already knows what is included in the KB, there is no point in querying. Consequently, your queries should use named variables whenever possible, unless formulation of a query in the assignment uses a specific constant, e.g., a number. For example, Query3 uses specific dates: September 13 and September 14.

Q10
My group is working on the second half of question 3 in assignment 1, where we formulate a few queries to test if our rules are correct. We notice that the scenario described does not contain any yellow lights, so we cannot write a query to test the rules involving yellow lights. Is this acceptable? Should we submit another set of atomic statements to test the yellow light rules?
A10
This is fine: you do not lose any marks if you do not test rules for yellow light. You can develop your own scenarios to test rules for yellow light just for fun, but this is not required.

Q11
I was wondering how detailed does the knowledge base need to be? for instance, in question 1, number 2: "is it possible to purchase a ticket to the opera tosca in toronto in january for less than $100?" I'm confused as to how the predicates should work. Do I just randomly make 'day' atoms? Do I need to specify that the 'price' is only for certain days and/or only for certain attractions? Or can I put something like this?:
city(toronto).
day(101).
attraction(tosca).
price(50).

A11
Read the assignment carefully: your KB should be written using the predicates given to you: flight, ticket, hasRoom. It is up to you what facts are you going to include in your KB. But you cannot use any other predicates in Part1 except of those given to you. In your queries, you can also use equality and inequality. When you write your KB, you might wish to group all your flight atomic statements together, also write consecutively all your ticket facts, and group together your hasRoom facts. Otherwise, if you mix these facts, so that the predicates are not consecutive, then you have to tell the compiler that these predicates are dynamic (this is the keyword to the compiler). Read the handout on ECLiPSe Prolog. There is an example there how you can use this dynamic declaration.

Q12
I have a question about Assignment 1 Part 3. Are the traffic lights in this scenario properly functioning? Specifically, streetlights opposite of each other always matched, and that if a light is red, the light to the left is either green or yellow.
A12
Yes, you can assume that all streetlights work as they are supposed to work on two-way city streets. Note also, that in Part 3 your task is to express the rules given to you in terms of Prolog.

Q13
is there a way to stop repetitive results from occuring? (i.e. X=a,Y=b followed by Y=b,X=a). I'm finding that some of the later questions produce far more results then they really need to.
A13
Repetitions in answers are fine. We discussed in class when and why this happens when I was talking about the slide 17 (queries in Prolog with equality) in "Prolog basics". The issue of how to prevent repetitive answers to a given query is beyond the scopes of this assignment. You are only responsible to make sure that all the answers are correct with respect to your KB.

Q14
How I can use mod to check that a particular day is not 13th day of a month?
A14
There are two ways you can use mod in arithmetical expressions. You can use an arithmetical expression with the syntax X is (1213 mod 100), then X gets assigned a value 13 (of course, in your query in the assignment, instead of 1213 you will be using a variable for a date that gets assigned an integer value before "mod" expression will be evaluated). Otherwise, you can also use the ECLiPSe Prolog's system predicate mod(+Number1, +Number2, -Result) that computes the remainder from dividing Number1 by Number2 and unifies the resulting value with Result, e.g., if you use the query mod(1213,100,X) then X gets the value 13. Note that the sign (+) in front of Number1,Number2 means that these variables should be instantiated with a particular value (in this case with an integer), before the predicate mod(+Number1, +Number2, -Result) will be evaluated. The sign (-) in front of Result means that it is expected that Result will be a variable and a query will retrieve a value for this variable. You can read more details if your run the query help(mod/3) in ECLiPSe Prolog (using a system predicate help) that prints manual for a given argument). Note that the call to Result is Number1 mod Number2 should be preferred for portability, so try to use it in this assignment.

Q15
I have a question about Assignment 1 Part 4. When it says to rewrite the rules, does that mean old and/or inefficient rules can abandoned, and that new rules may be added?
A15
Yes, the current inefficient rules implementing the left(X,Y) predicate should be replaced with a more efficient implementation. The new program must answer same queries as the old program, but the new program should answer queries in linear time. Also, your program should be within same restrictions as the whole assignment. In particular, you cannot use any library predicates, but you can introduce your own predicates if you wish. Note Part 4 is more challenging than other exercises and you do not have to try this exercise.

Q16
My question concerns Assignment 1, Part 2, end of page 2. It states: If the call numbered as N has lasted longer than the overtime limit, then its price is calculated as rate ∗ duration + surcharge ∗ (duration − overtime), where duration means total length of a phone call. Why is that the case? Instead I think that the surcharge should only be applied to the overtime minutes (anything over 10 minutes).
A16
Your understanding is correct, but the "overtime" variable in the given formula refers to the "overtime limit" itself, not to the number of minutes that exceeds this limit. In the formula above, we use the variable instead of the hard coded number 10 because we would like our program to remain modular. Suppose if someone changes the limit 10 up or down, then we update only once from 10 to a new number in the rule that defines what overtime limit is. All other formulas and rules would remain intact.

Q17
I am not sure why we need the predicate surcharge since overtime(Duration) performs the differentiation whether the length is overtime charge or not. The current way to use Surcharge within the predict is shown below. 
Surcharge(overtime(10)) -> return false since the length did not pass the 10 minute mark. 
A17
We use predicate overtime to hard-code duration 10min, and use predicate surcharge to hard-code the amount 25c. This is to isolate two lines in the program where we have to hard-code the numbers and to make sure the remaining part of the program is as generic as possible with respect to any overtime duration and any surcharge amount. You lose marks if your program in Part 2 will be using the numbers 10 and 25 more than once.

> Surcharge(overtime(10)) -> return false since the length did not pass the 10
> minute mark. 
You cannot write predicates inside other predicates, they are *NOT* functions. Each predicate is a primitive logical statement that can be true or false. You can write complex logical statements using conjunction (,) and negation (not). Moreover, each predicate must start with a lower case letter. Review the slides we discussed in class and read the textbook.

Q18
In the second question the "call" predicate has a collision with the library i am using for Prolog
A18
Use tkeclipse: my program runs there well with the 4-argument predicate call. If you insist on using another Prolog implementation, where your atomic statements with the 4-argument predicate call conflict with a library predicate "call", then rename your predicate. See the handout linked from D2L with recommendation (at the bottom) on how to rename predicates to avoid conflict with the library predicates. Since the TA will be marking and testing assignments on ECLiPSE Prolog, you better check your final version with tkeclipse anyway.

Q19
I was unclear about what this statement meant in assignment 1: The predicate surcharge(S) is true if S is the current surcharge for overtime that is representedas overtime(Duration): any phone call longer than Duration has to be surcharged. Does this mean overtime(Duration) is also another required predicate? If so, what would its function be?
A19
Surcharge(S) describes the cost S in cents for each extra overtime minute. Overtime(M) characterizes the boundary value M in minutes: as long as call length is less than the certain number M, the call is not overtime. You program must use both predicates overtime(Duration) and surcharge(S). They serve to minimize hard-coding in your program: see above Q16 and Q17

Q20
Can we use library predicates in this assignment, e.g., to process lists?
A20
No, you cannot use any external library predicates in the 1st assignment. You are not allowed to use lists in the 1st assignment: you do not need them.

Q21
I was just wondering if we were allowed to add new predicates and rules to help us make left(X,Y) more efficient in Part 4.
A21
Yes, you can in this part only. In Part 4, you get marks based on (1) quality of your analysis of what is the problem in the BW implementation discussed in class, i.e., why queries may take a long time; (2) correctness of your solution that should spend linear time with respect to n, the number of blocks; and (3) arguments why your solution is actually efficient. In other words, you have to convince the TA that your solution actually spends O(n) time for all queries. All of this should be written in your report. Note this bonus question is not mandatory.


CPS721