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.