Exercise: Plan Your Class Schedule

A college planning app must tell students what they can take now, an order for every course that keeps each prerequisite first, and how many semesters the degree takes, and spot a catalog mistake that makes any order impossible, fast enough for a catalog of 50,000 courses.

Freelancer · Data Structures · Updated

By

Here's the ticket from the college's registrar:

Students keep signing up for courses they aren't ready for, and nobody can tell them how long a degree really takes. Our planning app needs three answers.

  1. What can I take now? Given the courses a student has finished, every course they can sign up for, in catalog order.
  2. Plan my whole degree. Every course once, each after all of its prerequisites. If the catalog has a mistake, courses that wait on each other in a circle, say so instead of making up an order.
  3. How many semesters? If a student takes every course the moment it's ready, how many semesters does the degree take?

Next year the state's colleges share one catalog of 50,000 courses, and some chains of prerequisites run very long. Planning the whole catalog must take under 2 seconds.

The demo uses a small web development degree of eight courses. Each prerequisite is a pair of course names, before then after.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-class-schedule, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-class-schedule.git

Git makes a folder, exercise-ds-class-schedule, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • your code: one file with three functions to finish (the repository's README.md names the file for each language);
  • the tests that check your functions. You don't need to change them;
  • a demo program that tries your functions on a small eight-course degree.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

Every function is already there, with its parameters, and returns an empty list or 0 for now. The comment above each one says what it should return. Here is the third one in Python, as the starter has it (the other languages say the same in their own syntax):

def semesters_needed(courses, prerequisites):
    """
    How many semesters the degree takes, if a student can take any number
    of courses in a semester, but only once all their prerequisites were
    finished in an earlier semester. Return -1 when there's a loop.

    semesters_needed(sample degree) -> 5
    semesters_needed(three courses with no prerequisites) -> 1
    """
    return 0
  1. What can I take now? Finish readyNow (ready_now in Python, ReadyNow in C#): the courses not done yet whose prerequisites are all done, in the catalog's order.
  2. Plan the whole degree. Finish planSchedule: every course once, each one after all of its prerequisites. If some courses wait on each other in a loop, no order works: return an empty list.
  3. Count the semesters. Finish semestersNeeded: take every ready course in the first semester, every course they unlock in the next, and so on. Return -1 when there's a loop.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project ClassSchedule
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 9 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Web Apps also needs Databases, so it isn't ready yet.

The last test plans a catalog of 50,000 courses in one long chain, and has to finish in under 2 seconds. If it runs for a long time, stop it with Ctrl+C: it's telling you to change your approach, not that your answer is wrong.

<details> <summary>Stuck?</summary>

  • Read each pair as an arrow: ("Intro to Programming", "Programming 2") means Programming 2 needs Intro to Programming. The catalog is a directed graph.
  • readyNow doesn't need anything clever. For each course that isn't done, look at every pair that ends at it: is the course it starts from done?
  • planSchedule is a topological sort, from Which Course First? Topological Sort: count what each course waits on, start a line with the courses that wait on nothing, take from the front, and take 1 off each course it unlocks. A course whose count reaches 0 joins the back of the line.
  • A loop leaves courses behind. If your plan holds fewer courses than the catalog, the rest are stuck in, or behind, a loop.
  • semestersNeeded is the same method in rounds, like the levels of breadth-first search: everything ready now is one semester, and the courses that become ready during it make up the next.
  • If the 50,000-course test is slow, your plan probably rescans the whole catalog to place each course. If it stops with a stack overflow or a recursion error, it goes deep with recursion. The counting method needs neither.

</details>

When you're done

Every test is green, and the demo prints these five lines in every language:

Ready at the start: Intro to Programming, College Math
Ready after Intro to Programming: College Math, Web Basics, Programming 2
Plan: Intro to Programming, College Math, Programming 2, Web Basics, Data Structures, Databases, Web Apps, Capstone
Semesters needed: 5
With a loop: 0 courses planned, semesters -1

Your plan line may differ and still be right, if every course comes after its prerequisites: there's often more than one order. The comment above planSchedule says how to get exactly this one.

Now look at the semesters. Five is the length of the longest chain of prerequisites in the degree. Which chain is it, and which single prerequisite would you drop to make the degree a semester shorter?

<details> <summary>Why Should I Choose This?</summary>

Open this once your tests are green. The big catalog is 50,000 courses, each needing the one before it, listed backward.

  • Sort them some simple way (A to Z, or fewest prerequisites first): fast, but wrong. A course lands before what it needs.
  • Rescan the catalog for a ready course, place it, and rescan: right, but each of the 50,000 rounds reads the whole catalog again, O(V × (V + E)). It ran more than 4 minutes in Python (we stopped it there) and took 80 seconds in C#.
  • Depth-first search with recursion: O(V + E), but a chain 50,000 deep runs out of call stack in most languages.
  • Count what each course waits on, and keep a line of ready courses: each course joins the line once and each prerequisite is crossed off once, O(V + E). It took under a tenth of a second in Python and C#, and it finds a loop for free, as the courses left over.

</details>

Where else does this shape show up?

This chapter built two shapes on top of a graph: "the cheapest route when every edge has a cost" and "an order where every 'before' comes first". Before you open the answers, think of three places, at work or in daily life, where one of them is the real question.

<details> <summary>Some answers</summary>

  • A build tool compiles each project after the projects it uses: an order where every "before" comes first.
  • A package manager installs what a package depends on before the package itself.
  • A recipe app orders the steps so the oven is hot before the tray goes in.
  • A delivery app picks the route with the fewest minutes, not the fewest turns: the cheapest route.
  • A flight search finds the cheapest set of connections, where every flight has a price.
  • Your network sends each message along the quickest links between routers.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-class-schedule), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-class-schedule.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-class-schedule, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

So what

You've used a topological sort for a real planning tool, at the size of a whole state's catalog, and the same steps order builds, installs and spreadsheet updates. Next, the course's last chapter hands you problems you haven't seen, and the choice of structure is yours.

Key terms

Related