Comp Sci problem

1. ## Comp Sci problem

I know we have a few geeks on board (and I use that term in a positive way!), so I figured I'd post this.

My wife is volunteering to coordinate the noon-hour programs at my step-daughter's elementary school. Through this program, students can take courses like Yoga, Tae Kwon Do, Safe Bicycling, etc. during their lunch hours for a small fee.

The coordinators have just finished processing all the signup sheets for the students. It's all manual: the coordinators go throught the signup sheets and try to form classes, doing their best to get kids enrolled into all the courses they want (which isn't always possible). They have a few rules regarding priority registration, like when a child requests just one course, they should be given priority over a child who requests two courses. All in all, it's quite complciated, and as I mentioned, done manually. Ugh!

Being the computer geek that I am, I figure there must be an algorithm that solves this problem. But it's been years since I was in my algorithms class, so if I've ever seen an algorithm that provides a solution, I've forgotten about it.

Ideas?

Yes, removing the manual entry/paper submission would help too, but fixing the scheduling is what I'm interested in. It goes even deeper than the original scheduling: if there is enough interest, the coordinators can sometimes get another class organized for another day, which means everything needs to be reorganized

Who's got brains here? Obviously not me! Post up if you know of a good site to post this question on too

2. use a DB..

draw some E-R diagrams for the model used in that school, implement...
make some queries to suit your requirements

3. jaephu is a geek, dont listen to him. Just make him do it for you.

4. Originally Posted by jaephu
use a DB..

draw some E-R diagrams for the model used in that school, implement...
make some queries to suit your requirements
You trivialize the problem greatly. Are you in project management?

I am looking for an algorithm, not implementation. The ER diagram is extremely simple: course, section, enrollment request, enrollment, ... But I'm looking for answers at a higher level than implementation.

Perhaps I am making this more complicated than it needs to be? A simple set of rules, with precendence... iterative enrollment based rule precedence (which students are highest on the pecking order), eventually based on random picks when the set of students with the highest precedence is of greater size than what the classroom can accept? But I want to find a near-optimal solution, something that can give me good results when number of classes change, or there is choice involved (eg. student is enrolled in class A or class B... how will the choice affect others students enrollments?)

5. gord: this isnt something you can do half-assed. if you do, you'l regret it.

what ya need is a database made up of tables of students, courses, locations, instructors, plus all the many-to-many tables etc. ya then need a web app to put the info in and get it out.

lots of work to do it properly

in my experience of these things, unless you can afford a proper system, just carry on with the paper version. sorry.

EDIT: you work for a web-app company don't you? sorry if i don't get the question either. been a long day ya know

6. Originally Posted by iceneweb
gord: this isnt something you can do half-assed. if you do, you'l regret it.

what ya need is a database made up of tables of students, courses, locations, instructors, plus all the many-to-many tables etc. ya then need a web app to put the info in and get it out.

lots of work to do it properly

in my experience of these things, unless you can afford a proper system, just carry on with the paper version. sorry.

EDIT: you work for a web-app company don't you? sorry if i don't get the question either. been a long day ya know
I second that. What you're talking about is an n-tier system. And what's been suggested so far is the data layer, with all the database, tables, and stuff. Once you're done that then you'll need to create the "business layer" where you define all the business rules (e.g. if only 1 class then this, else if 2 classes then this). There isn't going to be an out-of-the-box algorithm that will fit your needs. It's a nice thought but if/when you get this system in place who's gonna maintain it. Rules will change and so will the code, and someone's gonna have to do it. You just may end up regretting initiating this idea. imo, not worth the effort unless you're willing to offer up all of your free time.

7. Yes, I know all (well, a lot) about web apps, at least in reference to our implementation at WebCT (and at my previous job). A web app would be very cool as it would push all the data entry on to the parents and away from the coordinators, but that is simple (!) implementation. I am more concerned about the scheduling logic.

Perhaps a concrete example would help explain the problem:

20 kids want to take Yoga, but there is only room for 15 in the class.

5 of the kids have Yoga as their only class requested. They get priority.

8 kids have Yoga as one of their two classes requested.

7 kids have Yoga as one of the three classes requested.

The other classes the kids have chosen each have a limited enrollment, just like Yoga.

So what is the best way to schedule the enrollments such that we satisfy the greatets number of people? How can we do this programmatically?

8. Things are actually a bit more complicated than this: the student can choose an "alternate" program: a program that he would be satisfied with if his first choice is not available. But that is just another detail.

9. Hmmm, perhaps I am not making it clear that program enrollment is not FCFS (first come, first serve). All the applications are collected, then the enrollments are decided.

10. There is a program to do this already. It is called Class, and is in use by most municipalities and school districts. Check to see if the school district your wife is in uses it. I think you can define all the business logic you want in each module. Resource requirements for Class can be somewhat high, decent server, Windows 2000 server, SQL 2000 server, etc. Pricey, but it does come with a web interface already built in as well.

11. Thanks Dean, but I want to figure out how it's done myself!

12. Haha, yeah one day..pojrect management baybeee..once I learn how to spell

There's just no way I'm gonna pump out a spec on BCSB, it'll take time & \$\$\$ . Yeah like all the others have pointed out, there's multiple layers of development to this. I just gave a quick and dirty idea of what I'd use to keep track of the data if i developed something like this. I believe UBC for example, uses databases for student registration. In addition to a bunch of other layers as well. It will take a lot of time just for the database level(assuming your model of registration is complex).

For the rules, first I'd design the ER diagram to fit the model. For some of your specific rules for example, I'd add them to the database using general constraints and/or triggers (if they're not already limited by participation and key constraints).

Well one thing I know for sure is this will be quite complicated and if it's going to be used by elemntary school staff, you'll have to take so much more consideration into everything. I havn't even included the software/UI layer...

I totally agree with iceneweb...

[QUOTE=iceneweb]gord: this isnt something you can do half-assed. if you do, you'l regret it.

what ya need is a database made up of tables of students, courses, locations, instructors, plus all the many-to-many tables etc. ya then need a web app to put the info in and get it out.

lots of work to do it properly

Originally Posted by iceneweb
gord: this isnt something you can do half-assed. if you do, you'l regret it.

in my experience of these things, unless you can afford a proper system, just carry on with the paper version. sorry.

One solution that MIGHT be feasible is search for some open source software. There's alot of development going on, especially in education, for this type of software.

I'd maybe do some google searches for some, or even check out sourceforget.net

I hope I was at least a bit helpful...(or maybe my database course has gotten the best of me)

Good luck!

13. Quick examples:
http://sourceforge.net/projects/ors/
http://sourceforge.net/projects/eledge/ (off topic, but good example of the educational open source software being developed)
http://sourceforge.net/projects/phpscheduleit/

...just do a search at sourceforget.net

14. I'll say it again: I'm looking for a description of the scheduling algorithm that I can use to solve the scheduling problem. I don't need input on databases, relational schemas, or webapps. I'm hoping that this problem maps to a well known algorithm, just as there are well known design patterns.

The algorithm will be independent of the implementation -- that's the whole point.

15. Oops. Sorry then..I don't know much about algorithm design, so I don't think I can help there.

I thought a database-driven solution would be more efficient for a scheduling task, but I could be wrong

Good luck ~

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•