University of Toronto - Winter
Department of Computer Science
Principles of Programming Languages
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.
You may not use the built-in Prolog predicates
findall/3, bag/3, setof/3.
You may use \+.
if you want to include another prolog source file in your files
you can use the following:
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
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.
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
Note that Orig, Dest, and Air are just my choices for variable names.
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.
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.
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. ?,?,?).
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
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
Back to the main page