What is QuACS?

QuACS is a course scheduling tool to help students pick which courses to register.

Key features:

• Automatic schedule generation
• Conflicting course detection
• Automatic prerequisite checking
• Up-to-date data
• View past semesters

Our goals

• Always up-to-date data
• Zero maintenance
• Mobile-first
• Open data availablity
• Above all else, it must be fast

Analytics

Website implementation

Frontend technologies

Vue.js

QuACS is a Progressive Web App

• Installable as an application
• Fully functional offline

Analytics

Privacy focused

Self hosted

Tracks unique sessions, page views, and events

Analytics helps us drive design choices

Course conflict algorithm

Problem: Given some selected courses, can you mark which courses can still be registered for without conflicts?

Sounds simple, right?

Course conflict algorithm

Problem: Given some selected courses, can you mark which courses can still be registered for without conflicts?

What if the user has selected multiple sections from each of their courses?

How about an example?

Course conflict example

I've selected up for these sections.

• Course A: S1 S2 S3
• Course B: S1 S2 S3

Can I select these sections?

• Course C: S0 S1 S2

Course conflict example

I've selected up for these sections.

Yes!

• Course A: S1 S2 S3
• Course B: S1 S2 S3
• Course C: S0 S1 S2

Course conflict example

I've signed up for these sections.

• Course A: S1 S2 S3
• Course B: S1 S2 S3
• Course C: S0 S1 S2

Can I add this one now?

• Course D: S1 S1 S2

Course conflict example

I've signed up for these sections.

• Course A: S1 S2 S3
• Course B: S1 S2 S3
• Course C: S0 S1 S2

No!

• Course D: S1 S1 S2

Course conflict algorithm

1. Generate all valid schedules (use DFS)
• Each level is a course
• Each branch is a section of that course
• Check each section against every time block of every other section in the schedule


2. Does the course/section we're checking work in at least one of the schedules?

This takes a while! Imagine the poor freshman who has every section of CS1, Calc 1, and Chem 1 selected :(

Can we mitigate the runtime?

• Use our RPI education to come up with a fundamentally better algorithm
• Only check a few schedules
• Pre-compute which sections conflict with each other
• Write it in Rust
• If all else fails, upgrade the server

• Use our RPI education to come up with a fundamentally better algorithm

Despite Professor Bringsjord's "proof" of P=NP, we've been unable to show it in practice

There isn't a fundamentally faster algorithm

Please: If you can figure this one out, let us know

Can we mitigate the runtime?

• Use our RPI education to come up with a fundamentally better algorithm
• Only check a few schedules
• Pre-compute which sections conflict with each other
• Write it in Rust
• If all else fails, upgrade the server

• Only check a few schedules

If a course doesn't work in the first N schedules, it probably doesn't work at all

Might be good enough for some course schedulers 😉

Not good enough for QuACS

Can we mitigate the runtime?

• Use our RPI education to come up with a fundamentally better algorithm
• Only check a few schedules
• Pre-compute which sections conflict with each other
• Write it in Rust
• If all else fails, upgrade the server

• Pre-compute which sections conflict with each other

We won't have to check if two sections overlap (That was the nested loop in our DFS)

This makes the algorithm a lot faster!

It takes up a bit more memory, but compresses well

Can we mitigate the runtime?

• Use our RPI education to come up with a fundamentally better algorithm
• Only check a few schedules
• Pre-compute which sections conflict with each other
• Write it in Rust
• If all else fails, upgrade the server

• Write it in Rust

Can we mitigate the runtime?

• Use our RPI education to come up with a fundamentally better algorithm
• Only check a few schedules
• Pre-compute which sections conflict with each other
• Write it in Rust
• If all else fails, upgrade the server

• If all else fails, upgrade the server

Wait a second... I thought we didn't want any maintenance???

We don't want to have to manage a cluster of servers

Why do we even need a server?

Course conflict algorithm (revisited)

Problem: Given some selected courses, can you mark which courses can still be registered for without conflicts, all within the browser?

This sounds impossible :(

Old ideas, revisited

• Pre-compute which sections conflict with each other?
• Pre-computing on page load increases load times
• This is a lot of data, so downloading it takes a while
• Turns out it's still not fast enough
• Write it in Rust?
• Websites are written in Javascript 😭

• Write it in Rust?

But I really like Rust!

• Write it in Rust?

But I really like Rust!

New ideas

Store the times a section occurs in a bitvector

Allocate a single bit for every hour in the week

Bits are 1 when the section occurs and 0 for all other times

Section meets at times T1 T2 T3 T4 T5

This would be stored asT1 T0 T0 T1 T0

Store the times a section occurs in a bitvector

Allocate a single bit for every hour in the week

Bits are 1 when the section occurs and 0 for all other times

Check for conflict with "bitwise and"

Pre-computation can minimize the number of bits needed

Bitvectors can be "ORed" together to store the times of the schedule

One operation to check if a section can be added

Run the algorithm in a separate thread

This means the site won't freeze while running the algorithm

Does it work?

2.45ms

to generate all schedules for CS1, Calc 1, and Chem 1

Data Collection and Site Generation

Data Collection

We want the most up-to-date and accurate data

Course availablity is determined by SIS

You shouldn't see any difference between SIS and QuACS!

Scraping Data

Helper scripts log into SIS for course times, seats, prerequisites, etc.

Course descriptions come from the catalog

Also collect data not on frontend

All stored in quacs/quacs-data

Automation

QuACS is fully automated by GitHub Actions!

QuACS is fully automated by GitHub Actions!

Standard actions

• Linting
• Site performance
• CodeQL

QuACS is fully automated by GitHub Actions!

Data collection

• Four scraper actions
• Runs every hour

QuACS is fully automated by GitHub Actions!

Site building

• Each semester is a separate instance
• One action builds all semesters

QuACS is fully automated by GitHub Actions!

Total time from scraping to deploy: 37 minutes

Hosted with GitHub pages

Zero downtime