From UBC Wiki

Authors: Yi Ang Mao, Kevin Yuen Gee Lee

What is the problem?

Given a knowledge base containing university courses that have information on:

  • the term and year in which a course is offered
  • which courses should be taken before which other courses (prerequisites)

our prolog program will take:

  • a list of courses you want to take

and return an ordering of courses such that prerequisites for any given course X are completed before one is scheduled to take course X.

What is the something extra?

Our program will use Kahn's topological sorting algorithm (implemented in prolog) to calculate the order courses should be taken in.

Our program will also consider things like handling

  • Alternate prerequisites (MATH xxx or CPSC yyy is a prerequisite to CPSC zzz)
  • Co-requisites (CPSC xxx can be taken before or at the same time as CPSC yyy)

In addition, we will provide a prolog query to determine whether a given ordering of courses can be completed without exceeding a maximum number of credits per term.

What did we learn from doing this?

We learned how to build a complex representation of a knowledge space by:

  1. Designing data structures to store relevant information like when a course is offered and what it's prerequisites are
  2. Writing small logical queries to answer simple questions that when combined can represent complex knowledge area

We also learned more about the vast library of prolog functions available for use. In particular we utilized ugraphs library extensively from SWI-Prolog to come up with a bug free implementation of topological sort.

We thought that logical programming was very suitable for our project since it's particular useful for representing a complex logical domain in simple syntax. We were able to write a small number of true statements and simple queries that when combined could actually answer very complex questions about our knowledge base. For example, from a simple list of courses containing information like credits, term offered and prerequisites we were able to design queries to answer complicated questions like: Is there an order I can finish a given set of requirements such that I don't exceed taking 12 credits per term?

Links to code etc

Example Queries in the project README