{ Last edited on 2001-09-05 22:19:49 by stolfi } { Course curriculum planner } { J. Stolfi - aug/2001. } { The input file contains a sequence of declarations that define the properties of curriculum subjects, courses, time slots, and various kinds of constraints. Course declarations ------------------- A course declaration has the form | "course" TAG "=" SLOTS ";" where TAG is an identifier for the course, and SLOTS is a comma-separated list of identifiers for the time slots (semesters, quarters, etc.) that make up the course's recommended curriculum. Each slot identifier has the form YTAG ":" PTAG where YTAG indicates the academic year within the curriculum, and PTAG the quarter or trimester within the year. For example, a four-year, trimester-based Computer Engineering course could be declared as | course CE = y1/a, y1/b, y1/c, y2/a, y2/b, y2/c, y3/a, y3/b, y3/c, y4/a, y4/b, y4/c; The full identifier of the semesters has ":" and CTAG appended. In the example, "y1/a:CE", is the first quarter of the first trimester of the "CE" course. The year identifiers must have all the same number of letters and digits, and ditto for the period identifiers. The SLOTS pairs must be listed in increasing lexicographic order, which is assumed to match their chronological order. Subject declarations -------------------- A subject is a set of lectures that fits in a single time slot and is allocated and taken as a whole. A subject declaration has the form | "subject" TAG ":" CTAG "=" CREDITS [ "<" PREREQS ] [ ">" POSREQS ] ";" where TAG is the subject's identifier, CTAG is the identifier of the corresponding course, CREDITS is a comma-separated list of credit weights, and PREREQS:POSREQS are comma-separated lists of prerequisites and reverse pre-requisites. For example, the subject MC202 for the Computer Engineering course, that has MC102 and MA101 as a pre-requisite, and is itself a pre-requisite for MC326 and MC600, could be declared as | subject MC202:CE = [2,0] < MC102,MA101 > MC326,MC600; Each declared subject is specific to a given course, so MC202:CE is different from MC202:BCS. You should think of the CTAG suffix as being part of the subject's identifier. In the above declaration, the ":CE" suffix is implied in each pre-requisite or post-requisite. The CREDITS attribute is defined as a vector, rather than a scalar, to account for constraints of the form "in each semester of the course's curriculum, there can be at most 8 credits total, at most 4 of them being lab classes. In such case, the cre Each constraint has the form | "require" EXPR ";" where EXPR is a formula that yields a single boolean value. Expression syntax ----------------- The operators that can be used in an expression are Set constructors "(" EXPRS ")", where EXPRS is a comma-separated list of expressions. Vector constructors "[" EXPRS "]". Boolean operators "!" (not), "&" (and), "|" (or). Arithmetic operators "+" and "-". Comparison operators "=", "<", ">", ">=", "<=" "<>". A subject identifier, STAG ":" CTAG. A slot identifier, YTAG "/" PTAG ":" CTAG. Postfix operators "." OPTAG where OPTAG is one of "$" "@" "max" "min" "sum" "and" "or" "num" "size" Operator precedences are, from highest to lowest: (1) postfix operators, (2) arithmetic operators, (3) comparison operators, (4) negation "!", (5) conjunction "&", (6) disjunction "|", and finally (7) the vector/set separator ",". Expression evaluation --------------------- The result of an expression is always a set of vectors of `simple' values. Both sets and vectors may be empty. A simple value can be either an integer, a subject, or a slot. Boolean values are special cases of integers: "0" for false, "1" for true. The simple values contained in a general values are said to be its `atoms'. A set constructor evaluates the expressions in EXPRS and returns the union of the resulting sets. In a vector constructor, each expression in EXPRS must yield a single vector (more precisely, a set whose only element is a single vector); the result is the concatenation of those vectors. Except where noted otherwise, a binary operator requires that the operands be sigleton sets of vectors, and is distributed over corresponding vector elements, yielding a single vector result. When the vectors have unequal lengths, the shortest one is implicitly extended with zeros. In general, a unary operator will distribute over the elements of both set and vector arguments, yielding a result with the same shape, except that duplicate set elements are unified. In general, slot and course identifiers must be fully qualified, although certain contexts (e.g. the "course" and "subject" declarations) may define default values for the CTAG. Any component of an identifier may be "*", meaning `any'; the value of such an expression is, in general, a non-trivial set. An `assignment' is a mapping from subjects to slots. An expression is always evaluated relative to some `current assignment'. The ".@" operator (see below), applied to a subject, yields the corresponding slot in the current assignment. Arithmetic, comparison, and boolean operators --------------------------------------------- Arithmetic operators apply to integers only. Comparison operators require that the operands be two integers, or two slots from the same course. For this purpose, slot order is defined by their chronological position within the course (which is also alphabetic order of their names). The Boolean operators apply only to boolean values, and follow the general distribution rules. Postfix operators ----------------- ".$" Applied to a set of single subjects, returns the sum of their credit vectors. If the set is empty, returns the empty vector <>. ".@" Applied to a single subject, returns the slot currently assigned to it. ".sbj" Applied to a single slot, returns the set of all subjects that are assigned to them. ".max" Can be applied to a set of vectors whose simple elements are all integers or all slots. Returns the maximum of the simple elements (a single integer or a single slot). ".min" Idem, for the minimum element. ".sum" Can be applied to a set of vectors whose simple values are all integers. Returns the sum of all those integers. ".and" Can be applied to a set of vectors whose simple values are all booleans. Returns the conjunction of all those booleans. ".or" Ditto for disjuntion. ".num" Applied to any set, returns the number of elements in it (a single integer). ".size" Applied to a single vector, returns its number of elements (a single integer). Value coercion -------------- Some contexts of an EXPR may imply coercion of the result to a specific type or shape, e.g. a single vector or a single value. In particular, a set of vectors of booleans is coerced to a single boolean, if needed, by `and'ing all the single booleans in it. It follow that "!(x = y)" may be different from "(x <> y)" when "x" and "y" are not single booleans. Whenever a subject is used in a context that requires a slot (for example, in a comparision), its currently assigned slot is used instead. Thus, for example, | require MC202:CE > MC102:CE; says that the slot assigned to MC202 in course CE must come after the slot assigned to MC102. Goal ---- The goal of the algorithm is to find an assignment that satisfies all prerequisites and requirements. } program ofcourse; uses courses; type SVClass = (SVClass_Int, SVClass_Slot, SVClass_Subj); { Class of a simple value } ID = string[MaxIDChars]; Subject = record sj: ID; { Subject matter tag. } cr: ID; { Course tag. } end; Slot = record yr: ID; { Year matter tag. } pd: ID; { Period tag. } cr: ID; { Subject's course. } end; SValue = record class: SVClass; case class of SVClass_int: intv: integer; { Value when Integer. } SVClass_Slot: slotv: Slot; { Value when a Slot. } SVClass_Subj: subjv: Subject; { Value when a Subject. } end end; VSet = record v: Vector; { prox: ^VSet; end; var Prb: Problem; begin initialize(Prb) while not eof do read_declaration(