Designing a course prerequisite structure using tree data structure

Courses
1

I’m working on a personal project to build a website for managing courses and their prerequisites. I’m using this to learn MERN stack development.

I’ve created a tree-like structure to show how courses depend on each other. The tricky part is that some courses have multiple prerequisites. I’m struggling to turn this into a working data structure.

My main issues are:

  • Can’t figure out how to have multiple parent nodes
  • Can’t traverse the tree to find available courses

I tried using a Tree/Node setup in JavaScript, but I’m open to other languages. Here’s a simplified version of what I’ve tried:

class CourseTree {
  constructor(rootCourse) {
    this.root = rootCourse || null;
  }

  addCourse(newCourse, parentCourse) {
    // Add new course logic here
  }

  findAvailableCourses() {
    // Logic to find courses with completed prerequisites
  }
}

const curriculum = new CourseTree();
curriculum.addCourse('MATH101');
curriculum.addCourse('PHYS201', 'MATH101');

Any suggestions on how to approach this? Maybe there’s a better way to structure this data? Thanks for any help!

2

hey jack, have u tried using a directed acyclic graph (DAG) instead? it’s perfect for prereqs. each course is a node, edges are dependencies. u can use adjacency list to represent it. for finding available courses, try topological sorting algorithm. it’ll give u courses in order. good luck with ur project!

3

Hey Jack27! Your project sounds super interesting! :smiley: I’m actually working on something similar for my university’s CS department.

Have you considered using a graph structure instead of a tree? Graphs are perfect for representing complex relationships like course prerequisites. Each course could be a node, and the edges could represent the prerequisites.

You could implement it like this:

class Course {
  constructor(name) {
    this.name = name;
    this.prerequisites = [];
  }

  addPrerequisite(course) {
    this.prerequisites.push(course);
  }
}

class Curriculum {
  constructor() {
    this.courses = new Map();
  }

  addCourse(name) {
    if (!this.courses.has(name)) {
      this.courses.set(name, new Course(name));
    }
    return this.courses.get(name);
  }

  setPrerequisite(courseName, prerequisiteName) {
    const course = this.addCourse(courseName);
    const prerequisite = this.addCourse(prerequisiteName);
    course.addPrerequisite(prerequisite);
  }
}

This way, you can easily add multiple prerequisites to a course. What do you think about this approach? Have you tried something similar before?

For finding available courses, you could use a depth-first search algorithm. It’d be cool to see how you implement that!

BTW, how far along are you with the MERN stack? I’m curious about how you’re planning to integrate this with MongoDB. Any thoughts on that?

4

I’d recommend using an adjacency list to represent your course structure. It’s efficient for storing relationships and allows for multiple prerequisites easily. Here’s a basic implementation:

class CourseGraph {
  constructor() {
    this.courses = new Map();
  }

  addCourse(name) {
    if (!this.courses.has(name)) {
      this.courses.set(name, []);
    }
  }

  addPrerequisite(course, prerequisite) {
    this.addCourse(course);
    this.addCourse(prerequisite);
    this.courses.get(course).push(prerequisite);
  }

  findAvailableCourses(completedCourses) {
    return Array.from(this.courses.keys()).filter(course => 
      this.courses.get(course).every(prereq => completedCourses.includes(prereq))
    );
  }
}

This structure allows for multiple prerequisites and efficient traversal. You can easily integrate this with MongoDB by storing course objects with an array of prerequisite IDs.