Description
Background
In this assignment, you are going to complete a Prolog knowledge base that contains facts and rules
about the prerequisite relationships between undergraduate courses in Computer Science (we’ll ignore
all courses numbered 600 and above). The starter code that I have provided already includes the
following information:
• Facts and rules that describe the prerequisites for non-computer science courses1
• Facts about consent of the department courses
• Facts about prerequisites for computer science courses that can only have their prerequisites
satisfied in one way
• A rule that generates all of the different combinations of direct prerequisites for CPSC 331
• Facts about courses that are antirequisite to each other
You will make several extensions to this knowledgebase through the remaining parts of this assignment.
Part 1:
Add rules to the knowledgebase that encode the prerequisites for the computer science courses
numbered between 217 (inclusive) and 599 (inclusive) that are not already listed in the knowledgebase.
Information about the prerequisites for the courses can be found at
http://www.ucalgary.ca/pubs/calendar/current/computer-science.html.
Like the facts and rules already in the knowledgebase, your encoding for these courses should use the
prereqFor functor. The first parameter is the course number, including its 4 letter department prefix,
and its second parameter should be a list of courses that must be taken before a student is eligible to
take the course provided as the first parameter. All of these courses have multiple combinations of
1 The provided prerequisites only consider university level (rather than high school level) requirements. A course
that only has high school level requirements is considered to have no prerequisites. The provided information also
only considers currently active courses (meaning that they are hyperlinks in the calendar). Historical courses that
are no longer being offered (which are reference without a link in the calendar) are ignored.
courses that can be used to fulfill their prerequisites. Your rules should ensure that Prolog generates all
such combinations through backtracking using a strategy similar to that of the provided rules for
data311, math311 and cpsc331 (among others).
Once you have completed this part of the assignment you should be able to use Prolog to query the
prerequisites for any undergraduate computer science course. For example, the query
prereqFor(cpsc313, X) should return the following 12 responses (the order in which the responses are
returned is not important).
X = [math271,phil279,cpsc219] ? ;
X = [math271,phil279,cpsc233] ? ;
X = [math271,phil279,cpsc235] ? ;
X = [math271,phil377,cpsc219] ? ;
X = [math271,phil377,cpsc233] ? ;
X = [math271,phil377,cpsc235] ? ;
X = [math273,phil279,cpsc219] ? ;
X = [math273,phil279,cpsc233] ? ;
X = [math273,phil279,cpsc235] ? ;
X = [math273,phil377,cpsc219] ? ;
X = [math273,phil377,cpsc233] ? ;
X = [math273,phil377,cpsc235]
Courses that do not have any prerequisites (such as CPSC 217) will instantiate the variable provided as
the second parameter to the empty list, indicating that they do not have any prerequisites.
You must encode the prerequisites for the courses as rules rather than as long lists of facts. For
example, while you could encode CPSC 319 using 5 facts:
prereqFor(cpsc319, [cpsc219]).
prereqFor(cpsc319, [cpsc233]).
prereqFor(cpsc319, [cpsc235]).
prereqFor(cpsc319, [encm335]).
prereqFor(cpsc319, [ensf337]).
Such an encoding is cumbersome, particularly when the number of combinations is large (CPSC 313 has
a dozen different valid prerequisite combinations and some other courses have a similarly large number
– you don’t want to have to list all of them off separately). Instead, the prerequisites for such courses
can use the member predicate and backtracking to generate all combinations.
With judicious use of rules involving member, the prerequisites for all of the courses can be encoded in
approximately 50 lines of code (and one could write the code more compactly by placing more than one
clause on each line if one wanted to). Note that you do not need to encode anything for notes like
“Prior complete of CPSC XXX is strongly recommended”.
Part 2:
Write a Prolog rule named allPrereqFor that identifies all combinations of courses that can be used to
satisfy the prerequisites for a course (both its direct prerequisites and recursively, all of its prerequisites
prerequisites). You should sort each generated list using the sort/2 built-in predicate, both because that
predicate merges duplicate elements so that you never see the same course listed twice, and because it
will make it easier for you to compare your results to the provided test cases. Note that this rule will
generate a large number of combinations for some courses. For example, allPrereqFor(cpsc413, X)
generates over 1724 possible combinations because of all the different ways that the math prerequisites
can be satisfied. Applying it to cpsc331 generates the following 12 results:
| ?- allPrereqFor(cpsc331, X).
X = [cpsc217,cpsc219,math211,math271] ? ;
X = [cpsc219,data211,math211,math271] ? ;
X = [cpsc217,cpsc219,math213,math271] ? ;
X = [cpsc219,data211,math213,math271] ? ;
X = [cpsc231,cpsc233,math211,math271] ? ;
X = [cpsc231,cpsc233,math213,math271] ? ;
X = [consent235,cpsc235,math211,math271] ? ;
X = [consent235,cpsc235,math213,math271] ? ;
X = [cpsc217,cpsc219,math273] ? ;
X = [cpsc219,data211,math273] ? ;
X = [cpsc231,cpsc233,math273] ? ;
X = [consent235,cpsc235,math273]
Applying it to cpsc501 generates the following 36 results:
| ?- allPrereqFor(cpsc501, X).
X = [cpsc217,cpsc219,cpsc319,cpsc449,phil279] ? ;
X = [cpsc219,cpsc319,cpsc449,data211,phil279] ? ;
X = [cpsc231,cpsc233,cpsc319,cpsc449,phil279] ? ;
X = [consent235,cpsc235,cpsc319,cpsc449,phil279] ? ;
X = [cpsc319,cpsc449,encm335,engg233,phil279] ? ;
X = [cpsc319,cpsc449,engg233,ensf337,phil279] ? ;
X = [cpsc217,cpsc219,cpsc319,cpsc449,phil377] ? ;
X = [cpsc219,cpsc319,cpsc449,data211,phil377] ? ;
X = [cpsc231,cpsc233,cpsc319,cpsc449,phil377] ? ;
X = [consent235,cpsc235,cpsc319,cpsc449,phil377] ? ;
X = [cpsc319,cpsc449,encm335,engg233,phil377] ? ;
X = [cpsc319,cpsc449,engg233,ensf337,phil377] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math211,math271,phil279] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math211,math271,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math213,math271,phil279] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math213,math271,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math211,math271,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math213,math271,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math211,math271,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math213,math271,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math273,phil279] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math273,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math273,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math273,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math211,math271,phil377] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math211,math271,phil377] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math213,math271,phil377] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math213,math271,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math211,math271,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math213,math271,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math211,math271,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math213,math271,phil377] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc449,math273,phil377] ? ;
X = [cpsc219,cpsc331,cpsc449,data211,math273,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc449,math273,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc449,math273,phil377]
My solution to this part of the assignment is approximately a dozen lines of code, consisting of the
allPrereqFor rule and a second rule to help generate the required results.
Part 3:
You may have noticed that some of results generated by allPrereqFor were contradictory insomuch as
they included pairs of courses that can’t be taken together, such as both cpsc231 and cpsc217, or both
cpsc319 and cpsc331. For example, the first four results generated for cpsc441 by my implementation
are:
| ?- allPrereqFor(cpsc441, X).
X = [cpsc217,cpsc219,cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [cpsc217,cpsc219,cpsc319,cpsc355,cpsc359,data211,phil279] ? ;
X = [cpsc217,cpsc219,cpsc231,cpsc233,cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [consent235,cpsc217,cpsc219,cpsc235,cpsc319,cpsc355,cpsc359,phil279] ? ;
…
Notice that the second, third and fourth results are contradictory lists – the second result includes both
cpsc217 and data211, the third list includes both cpsc217 and cpsc231, and the fourth result includes
both cpsc235 and cpsc217 (and cpsc219 with is also an antirequisite for cpsc235).
Using the antirequisite information that I already included in the knowledgebase, create a Prolog rule
named allPrereqFor_NoAnti. It will generate a sorted list (with duplicates removed) of all of the
prerequsiites for a course (both its direct prerequisites, and recursively, all of its prerequisites
prerequisites) such that the generated lists never contain a pair of courses that are antirequisite to one
another. For example, allPrereqFor(cpsc457, X) generates 252 different lists of courses, many of which
contain antirequisites. In contrast, allPrereqFor_NoAnti(cpsc457, X) generates the following 36
combinations:
| ?- allPrereqFor_NoAnti(cpsc457, X).
X = [cpsc217,cpsc219,cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [cpsc217,cpsc219,cpsc319,cpsc355,cpsc359,phil377] ? ;
X = [cpsc219,cpsc319,cpsc355,cpsc359,data211,phil279] ? ;
X = [cpsc219,cpsc319,cpsc355,cpsc359,data211,phil377] ? ;
X = [cpsc231,cpsc233,cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [cpsc231,cpsc233,cpsc319,cpsc355,cpsc359,phil377] ? ;
X = [consent235,cpsc235,cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [consent235,cpsc235,cpsc319,cpsc355,cpsc359,phil377] ? ;
X = [admit_ENEL_or_ENSF,cpsc319,encm335,encm369,enel353,engg233] ? ;
X = [admit_ENEL_or_ENSF,cpsc319,encm335,encm369,enel353,engg233,ensf337] ? ;
X = [admit_ENEL_or_ENSF,cpsc319,encm335,encm369,enel353,engg233,ensf337] ? ;
X = [admit_ENEL_or_ENSF,cpsc319,encm369,enel353,engg233,ensf337] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math211,math271,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math213,math271,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math211,math271,phil377] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math213,math271,phil377] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math211,math271,phil279] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math213,math271,phil279] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math211,math271,phil377] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math213,math271,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math211,math271,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math213,math271,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math211,math271,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math213,math271,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math211,math271,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math213,math271,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math211,math271,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math213,math271,phil377] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math273,phil279] ? ;
X = [cpsc217,cpsc219,cpsc331,cpsc355,cpsc359,math273,phil377] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math273,phil279] ? ;
X = [cpsc219,cpsc331,cpsc355,cpsc359,data211,math273,phil377] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math273,phil279] ? ;
X = [cpsc231,cpsc233,cpsc331,cpsc355,cpsc359,math273,phil377] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math273,phil279] ? ;
X = [consent235,cpsc235,cpsc331,cpsc355,cpsc359,math273,phil377] ? ;
My solution to this part of the assignment is less than 20 lines of code spread across multiple predicates.
Part 4:
Create a Prolog rule named neededCourses that identifies sets of courses that can be taken in order to
allow enrollment in a desired course. The rule will take a list of courses that the student has completed
previously as its first parameter, and a single course that is desired as its second parameter. The final
parameter will be an uninstantiated variable that will be instantiated with a list of courses that the
student needs to take in order to take the desired course. The generated lists of courses should be
minimal, meaning that they should not include courses outside of the prerequisite chain for the course
in question. In many cases, there will be multiple minimal options. All such options should be
generated via backtracking.
Note that the lists generated in this part of the assignment should not contain any courses that are
antirequities to courses that the student has already taken. For example, if the student has already
taken cpsc231 and cpsc233 and wants to take cpsc331 then your rule should generate results indicating
that the student only needs to take either math211 and math271, or math213 and math271 or
math273. Don’t return any results that include cpsc217, cpsc219 or cpsc235.
Consider the following examples:
| ?- neededCourses([cpsc231, cpsc233], cpsc457, X).
X = [cpsc319,cpsc355,cpsc359,phil279] ? ;
X = [cpsc319,cpsc355,cpsc359,phil377] ? ;
X = [cpsc331,cpsc355,cpsc359,math211,math271,phil279] ? ;
X = [cpsc331,cpsc355,cpsc359,math213,math271,phil279] ? ;
X = [cpsc331,cpsc355,cpsc359,math211,math271,phil377] ? ;
X = [cpsc331,cpsc355,cpsc359,math213,math271,phil377] ? ;
X = [cpsc331,cpsc355,cpsc359,math273,phil279] ? ;
X = [cpsc331,cpsc355,cpsc359,math273,phil377] ? ;
| ?- neededCourses([], cpsc219, Y).
Y = [cpsc217]
Y = [data211]
| ?- neededCourses([cpsc231, cpsc233, math211, math271, cpsc331], cpsc585, Z).
Z = [consent585,cpsc453,math249,math267] ? ;
Z = [consent585,cpsc453,math265,math267] ? ;
Z = [consent585,cpsc453,math267,math275] ? ;
Z = [consent585,cpsc453,math275,math277] ? ;
Hint: You may find it helpful to look at the list predicates in Section 8.20 of the gProlog manual located
at http://www.gprolog.org/manual/gprolog.html#sec209. By using facts and rules that I developed for
the previous parts of the assignment I was able to complete this part using only 5 lines of code.
Additional challenge:
Write a rule that identifies which courses a student still needs to take to complete the Concentration in
Computer Graphics. The requirements for the concentration can be found near the bottom of this page:
http://www.ucalgary.ca/pubs/calendar/current/sc-4-3-1.html (searching for graphics will help you find
it quickly). The first parameter to the rule will be a list of courses that the student has already taken.
The second parameter will be an uninstantiated variable. Your rule should instantiate the variable with
minimal combinations of courses (through backtracking) that the student can use to complete the
Concentration in Computer Graphics.
Grading:
A+: All parts of the assignments are completed successfully, included the additional challenge.
A: All parts of the assignment, except for the additional challenge, are completed successfully.
B: Parts 1, 2 and 3 of the assignment are completed successfully.
C: Parts 1 and 2 of the assignment are completed successfully.
D: Part 1 of the assignment is completed successfully.
