University of Toronto - Winter 2007
Department of Computer Science

CSC 324: Principles of Programming Languages

Assignment 6
Clarification Page

Help Sessions

We have scheduled the following A6 Help Sessions:

  • Wednesday April 4: 2:00-3:00 PM (Bahen 5256)
  • Thursday April 5: 4:30-5:30 PM (Pratt 378 - 6 King's College Rd)
  • Tuesday April 10: 4:30-5:30 PM (Pratt 378 - 6 King's College Rd)
  • Thursday April 12: 4:30-5:30 PM (Pratt 378 - 6 King's College Rd)
  • Apr 9: Don't forget about Sheila's regular office hour on Wednesday 3:30 - 4:30 in Pratt 398D.



    General Clarifications

    Apr 5:
  • You may not use the built-in Prolog predicates findall/3, bag/3, setof/3.
  • You may use \+.

    Apr 10:
    if you want to include another prolog source file in your files you can use the following:
    :- [otherfile]. This will load 'otherfile.pl' when compiling (loading) the file this line is in.

    You may want to use this in your solution to Q3 to load your solution to Q2. Note that for marking Q3, we are simply going to replace your a6-trip.pl file with our correct solution before loading your a6-optimizing.pl file. This way you won't get punished twice for potential mistakes you did in Q2



    Question-Specific Clarifications

    Question 1
    Apr 5: flight/5 and airport/3 are the only prolog predicates of your own creation that you can use. You are allowed to use other prolog built-ins like >, etc.. If you want to use something else and you aren't sure, please ask Sheila.

    Question 1b
    Apr 11: Some clarification about "pairs of distinct cities": In the example database, you can fly from Toronto to Barcelona via Madrid with Iberia, and from Barcelona to Toronto via Madrid with Iberia. We expect your query will return both
    Orig=toronto
    Dest=barcelona
    Air=iberia
    AND
    Orig=barcelona
    Dest=toronto
    Air=iberia
    Note that Orig, Dest, and Air are just my choices for variable names.

    Question 1e
    Apr 9: The question asks for all cities that cannot be reached from Valencia in one flight. This includes cities which cannot be reached from Valencia at all, and those that can only be reached with two or more flights. Your query should however not need to distinguish between these two cases.

    Question 2a
    Apr 9: The assignment asks you to implement this predicate for the '?Origin, ?Destination, ?Path' mode and there is a very straightforward implementation for this. However, if you have problems with this case, it is sufficient to implement it assuming that at least one of the arguments will be instantiated, i.e. the modes
    +Origin, -Dest, -Path
    -Origin, +Dest, -Path, and
    -Origin, -Dest, +Path.
    Note that all of these are special cases of the ?,?,? case.

    Question 2b
    Apr 9: Above comments do not hold for the 'trip' predicate. This we require you to implement the way it says in the assignment handout (i.e. ?,?,?).


    Question 3
    Apr 11:
    Separate Algorithms:Question 3 says Do not write separate algorithms for price and duration. What we mean by this is that you should have one piece of code that tries to construct a trip. The only place that should be specific to price or duration is the place (e.g., a predicate) where you check the criterion. This place (e.g., a predicate) can be specific to price or duration and will succeed or fail, telling you whether to carry on with your search or to abort.

    As we discussed in class, you could construct the trip by starting at the origin and adding legs to your trip until you reach the destination. If you've got a partial trip constructed that is already over the limit, you want to stop exploring that particular path because no completion of the path you've constructing will ever allow you to find a trip that adheres to the criterion because your partial trip already exceeds the criterion. E.g, if you want to fly to Toronto to Hong Kong for under $700 and you've found a flight Toronto to Vancouver for $800, you're not going to be able to complete that path Toronto-Vancouver-..-Hong Kong for $700 or less, so you may as well abort and try another path!

    Clarifying the hint: The description of Question 3 starts with 3 paragraphs of text. The approach described in the third paragraph, which talks about finding better routes, only relates to Question 3b. Question 3a requests that you construct a trip that does not exceed some fixed limit. In 3a, you need to try to construct a trip and if your partial path exceeds the limit you want to stop exploring that path. In 3b, you want to follow the basic algorithm described in the 3rd paragraph.
    Back to the main page