Degree Planning Assistant Paper

Home : Portfolio : Degree Planner : Degree Planning Assistant Paper

Dan Bjorkegren and Sylvia Kwan

Overview

Many students change their major in their second or third year--finding out that have made poor decisions in choosing courses.

The Degree Planning Assistant is a tool designed to assist undergraduates in registering for courses by displaying relevant information about offered courses required for their degree program. It was designed to empower students to make their own decisions about courses rather than to make automated choices for students. The tool will make recommendations and will display relevant information about courses (such as, 'this course is offered only next quarter' or 'this course is a prerequisite for 4 other courses required for your degree program'), but will give students full freedom in deciding how to use these results. Moreover, the tool is simple: it does not rely on complex heuristics; its utility is in its presentation and synthesis of information from various sources, including the DARS degree auditing tool, the course catalog and the time schedule. This document is a presentation of a possible design for the Assistant; the software itself has not been written.

The tool will benefit the entire university community. The tool is especially useful for freshmen or students who have not declared majors. It can separately show admission requirements and degree requirements to multiple majors and minors and forecast admission dates. If some required courses are full, this tool will show other courses the student can take. Further, the tool can show information about the degree program in both short and long term views: students can plan one quarter ahead while keeping the whole degree program in perspective, and if a student decides to change major, the tool will help the student make the most of the courses they have taken already. As such, advisors can better plan the quarterly schedule for the students, especially if the students are pursuing multiple majors. On the whole, it saves the entire university community a lot of time from poor course decisions that are easy to make at such a large institution with complicated degree programs and an abundance of courses.

Basic Setup

First, we need to know the degree program the student is pursuing. A list of degree programs will be given for the student to choose. After the student selects the degree program, the software finds all of the classes required for admission and graduation. These required courses are assembled as nodes in a graph. Upper level courses are connected to their prerequisite courses-a connection from one node to another represents that one course is a prerequisite of another. Admission into a degree program and graduation from a degree program are inserted into the graph as nodes with prerequisite ('required') courses.

In analyzing this graph, the assistant uses simple graph theory techniques: graph traversal, comparison of distances between nodes, and node counting. After putting the data into this graph form, only simple operations are required to produce useful results.

Courses that the student has already completed are ignored. The courses that have yet to be completed that it is possible for the student to take this next quarter are represented with thicker circles. Ultimately the software will assign weights to these 'possible' courses-the only courses the student could take this next quarter-by analyzing the degree program as a whole.

In this paper we focus on the 3 main quarters of the year: Autumn, Winter and Spring, although the tool could easily be extended to the different terms of Summer quarter. These quarters are represented by the 'quarter index' integer. The current Autumn quarter is stored as 0, Winter as 1, Spring as 2, the next Autumn as 3, and so on. If we want to know which quarter is represented by a quarter index that goes beyond 2, you take the quarter index modulus 3. For instance, if we have index 5, we can find out which quarter that is by looking at 5 % 3, which is 2: it is Spring quarter. Similarly, we can find out how many years in advance a quarter index is by dividing by 3 and discarding the remainder: 5 / 3 = 1 year in advance.

The data for the graph comes from multiple registration tools that are open to the public. The list of courses required for each degree program can be taken from the DARS degree audit tool, course prerequisite and quarters offered data can be taken from the online Course Catalog, and up to date status information about courses can be taken from the online Time Schedule.

Representation

Although the final tool will not display the degree program graphs to the user, it is helpful to come up with a diagramming format to display these graphs in this paper. The following is an example graph representing the courses required for admission to the Computer Engineering program.

ENGL comp, CSE 142, CHEM 142, PHYS 121, and MATH 124 can be taken in the current registration quarter, so the nodes for these courses have thicker borders.

Each node shows the quarters its course is offered below the title of the node. To avoid distraction, nodes representing courses offered every quarter do not have a list the quarters the courses are offered-so in the example graph, Computer Engineering Admission is the only node not offered every quarter, so it is the only node that lists which quarters it is offered. The dashed arrows linking from a course to another indicate that one course is a prerequisite that can be taken concurrently, or at the same time, as the other. The solid arrows indicate that one course is a prerequisite that must be fulfilled before taking other. For instance, MATH 125 is a prerequisite for MATH 126, PHYS 122 and MATH 307. Also, MATH 125 can be taken concurrently with PHYS 122.

In the rest of the paper we represent program logic using a simple form of pseudocode which borrows from C and can easily be transformed into production code in a standard language. The prefix '&' before a type represents a reference, and '[]' after a name represents a vector or dynamically sizeable array.

Basic Code

The node datatype
Each node represents a course and contains a dynamically sizable array of integers representing the quarters the course is offered and an array of references to nodes representing the leaves of the node-the courses that rely on this course for a prerequisite. Note that this information can be stored much more efficiently-for simplicity we leave optimization up to the implementers.

struct node
   string course_name
   int quarters_offered[]
   &node leaves[]
end

The offered function returns 1 if a course is offered a given quarter, 0 if it is not, and -1 if no data is available. Additional work would be required to support classes that are not offered every year (every other year, for instance).

offered ( node, quarter )

   if node.quarters_offered.length == 0 then
      return -1
   end

   for every q of node.quarters_offered
      if q == quarter % 3 then
       return 1
      end
   end

   return 0
end

The soonest_quarter_offered function returns the next quarter index after a given quarter that a course is offered or -1 if there is an error.

soonest_quarter_offered ( node, given_quarter )
   if offered ( node, given_quarter ) == 1 then
      return given_quarter
   else if offered ( node, given quarter + 1 ) == 1 then
      return given_quarter + 1
   else if offered ( node, given_quarter + 2 ) == 1 then
      return given_quarter + 2
   end
   return -1 // we have no data for this course
end

Components of the System

Prerequisite Test

The prerequisite test gives each course a weight according to how many prerequisites they satisfy. A course that will open up a lot of other courses is given a large weight.

Benefit

This test gives students more freedom: by suggesting that students complete prerequisite courses first, students will have more options available to them in future quarters. Ultimately, this means that students will not be 'trapped' into having a quarter where they can take no classes that help them toward their degree.

Assumptions

It is best to complete prerequisite courses sooner rather than later
Data for prerequisite courses remains relatively stable year-to-year and quarter-to-quarter

Example

The prerequisite test recommends we take MATH 124 and PHYS 121.

Function

number_of_leaves_no_duplicates ( node, already_counted = null )
   int number = 1

   // If this is the first time the function is called
   // (before we start recursing), initialize already_counted

   if already_counted == null then
      already_counted = new &node[]
   end

   for every leaf of node.leaves

      // Ensure that we don't count nodes twice

      if not already_counted.contains( leaf ) then
       already_coutned.add( leaf )

       number = number + number_of_leaves ( leaf )
      end

   end

   return number
end

calculate_prereq_weight ( node )



   return number_of_leaves_no_duplicates ( node )

end

Note that we need to keep a list of nodes we have counted-otherwise, in our example, Computer Engineering Admission would be counted twice when calculating the number of courses that taking MATH 124 opens up-once from MATH 307 and once from MATH 126.

Quarters Offered Test

The Quarters Offered test will give weight to courses that are offered for the current registration quarter and not the quarter after. It signals to students when a sequence is starting, or when a course is offered only for one quarter, so that students will not miss the course and have to wait a year for it to be offered again.

Benefit

The Quarters Offered test will help students start sequences on time, and help them avoid missing courses that are only offered one quarter each year.

Assumptions

It is possible to find out which quarters courses are offered in advance with a good degree of certainty
Students unknowingly miss sequences and series of courses

Example

Since the courses used in our Computer Engineering Admission example are offered every quarter, the Quarters Offered Test won't show us anything.

Function

offered_this_quarter_but_not_next ( node, registration_quarter )

   return node.offered ( registration_quarter ) == 1 and not
   node.offered ( registration_quarter + 1 ) == 1

end

calculate_quarter_weight ( node, registration_quarter, already_counted = null )

   int weight = 0

   // If this is the first time the function is called
   // (before we start recursing), initialize already_counted

   if already_counted == null then
      already_counted = new &node[]
   end

   if offered_this_quarter_but_not_next ( node, registration_quarter ) then
      weight = 1
   end

   for every leaf of node.leaves

      // Ensure that we don't count nodes twice

      if not already_counted.contains( leaf ) then
       already_counted.add( leaf )

       weight = weight + calculate_quarter_weight( leaf, registration_quarter + 1 )
      end

   end

   return weight

end

Critical Path Test

The critical path test will find the shortest path through a set of required courses. If we find the critical path, or the set of courses that forms a lower bound on how long it takes to complete these courses (because of prerequisites and the quarters courses are offered), we can recommend that students complete these critical courses before others. This test is a more heavy-duty version of the Quarters Offered test, and it assumes that more knowledge is available in forecasting courses for future quarters.

Benefit

The critical path test helps students look at the bigger picture of their degree program by showing areas that need to be investigated. Specifically, this test will highlight the series of courses that form a lower bound on a student's graduation date, recommending that the student complete these courses to avoid delaying graduation.

Assumptions

It is possible to find out which quarters courses are offered in advance with a good degree of certainty
Course offerings do not vary greatly from year to year
There are long sequences or series of courses that students do not start early enough, forcing them to spend an extra year in school to complete their degrees

The critical path test has the strongest assumption of the tests mentioned in this paper: that we can forecast when courses will be available not only for the current year, but also for several years in advance. If this information were reliable, this test would be extremely useful.

Example

The critical path test recommends that we take MATH 124 and PHYS 121 (the critical paths are represented by the thicker lines).

Function

The critical path test determines the longest time possible to complete a number of courses. It traverses the prerequisite tree, finding the path through them that will take the longest-the path that forms a lower bound on how long it will take a student to complete the courses.

critical_path_length ( node, quarter, already_counted = null )
   int current_quarter = soonest_quarter_offered ( quarter )
   int pathlength = current_quarter

   // If this is the first time the function is called
   // (before we start recursing), initialize already_counted

   if already_counted == null then
      already_counted = new &node[]
   end

   for each leaf of node.leaves

      // Don't waste time calculating the path twice for one node

      if not already_counted.contains( leaf ) then

       already_counted.add( leaf )

       int currentlength = critical_path_length ( leaf, current_quarter) )

       if currentlength > pathlength then
         pathlength = currentlength
       end

      end

   end

   return pathlength

end

Putting it All Together

To put the tests together and build a completed product requires more information about our users and more information about our data, as well as more testing with edge-case examples. Only after finding out more about our how this tool will be used could we combine the tests we have build to actually rank the courses.

So then, what we have presented is a solution to the difficult problem of course registration and degree planning; a solution that uses simple graph theory rather than complex algorithms. Ultimately the utility of the Degree Planning Assistant is derived from its synthesis of data from multiple sources, which makes complex information available to the user in a form they can understand. This gives the implementers tremendous creative freedom in stringing together data from multiple sources to provide useful information for the user.

Sample Degree Plan

Joe Freshman is a new student at the University of Washington with no transfer credits. He is thinking about completing one of either the Electrical Engineering, Computer Engineering, or ACMS majors. He uses the Degree Planning Assistant to rank the possible courses he could take for his first Autumn quarter (2003) at the University. The tool internally makes an graph of his situation before running the tests:

The prerequisite test recommends that Joe take Math 124 (satisfies a total of 4 prerequisites for courses and required for 3 degree programs), Physics 121 (satisfies a total of 2 prerequisites for courses and required for 3 degree programs), and CSE 142 (satisfies 1 prerequisite for a course and required for 3 degree programs) above the other courses.

The quarters offered test doesn't impact the recommendations of the tool, because all of the courses that are required for admission to these degree programs are offered every quarter.

The critical path test shows that the soonest Joe could apply to either EE or CE is next autumn quarter (it will take him a year to complete the Physics and Mathematics sequences, and he can take Math 307 and Math 126 at the same time). The soonest Joe could apply to ACMS is next winter, because he will need to take Math 308 after completing the one year Math sequence. So the critical path test recommends that Joe take Physics 121 and Math 124 for his first quarter.

Here is an example of what the Degree Planning Assistant will show Joe Freshman: