[chevellejnj72]

Alright, I hope i am in the correct section. I have to code a program that makes a students schedule for his/her entire undergrad degree so that they graduate in the fastest time possible. I have really no restrictions in how to create this program. My strongest language is Java and my professor mentioned to use MS access to manage a database. Here is some more information:

The only input will be what year and semester the student starts.

There is a database of all available classes for 12 semesters and a database for the classes required to take to complete the computer science major. The classes are split into two categories, core/required and electives. The rest the program is meant to handle and then outputs each semesters class schedule till graduation.

Each semester will be limited by the maximum credit level which is 18 credits per semester and classes are only offered Monday through Friday and only the fall and spring semesters. Classes also have prerequisites that need to be considered. Meaning CS 331 cannot be taken until CS 252 is taken. We are also assuming the student passes every class signed up for.

I've never programmed a project this complex and not worried so much about the code as more so the logic and data structures/algorithms needed to complete this. I need to figure out how to search the class list for the classes needed, track classes taken, manage conflicts (if two classes are offered same time), and if a class has a prerequisite and if it has been taken yet.

There are some more complex things to take into consideration but would rather have a complete project leaving some more difficult parts out as opposed to incomplete project with them. There might be more than one class that could fill one requirement. For example, say I need to take one type of art class. VIS 201 can fill that requirement but so can MUS 180. I feel like that may cause some issue if not taken into account. Like if I take VIS 201, MUS 180 shouldn't be available since they are equivalent. Another advanced part comes into say the program has two classes to consider, CS 317 and CS 391 but only needs one to complete the semester for spring 2012. Both pass the conflicts test (they dont conflict with other classes) so which does it choose? Both these classes are offered Spring 2012 but maybe only CS 391 is offered the following semester Fall 2012. It would make more sense to take CS317 in the spring and then CS 391 in the fall otherwise if took CS 391 in spring you would have to wait until CS 317 was offered again. On top of this, CS 317 could be equivalent to CS 391 meaning only have to take one so you wouldn't have to worry about this at all.

ANY advice would be greatly appreciated. At this time, I am NOT looking for code but more so a strategy on how to go about this logically. What data structures to use, how to handle time conflicts, what algorithms and more importantly where to start. Thanks in advance!

[modi123_1]

Quote

What data structures to use,

Sounds like a tree to me.

Quote

how to handle time conflicts,

The tree structure should be able to work this out.

Quote

importantly where to start.

I would start with being able to load your data, and constructing the right class/node object for the data.

Out of curiosity - what class are you doing this for?

[Manbearpig101]

At first glance, this seems like a shortest path problem on a directed acyclic graph. However, I'm not totally sure.

[iniaes]

this sounds a little like the travelling salesman or the knapsack problem. . . You need to establish the course interrelations algorythimcally. Do you have a set of answers to compare, or do all the shortest possible permutations have to be generated by your program?

[Manbearpig101]

Do classes span over more than one semester? If they don't, you could greedily just take the maximum amount of classes per semester, making sure not to take a class that you don't have the prerequisites for.

Also, can you post a sample of the database? I'm really interested in writing a solution.

This post has been edited by Manbearpig101: 26 November 2011 - 05:42 PM

[blackcompe]

I'd say this is a Knapsack problem.

[chevellejnj72]

Its for an 3rd level algorithms class and a 3rd level advanced programming class.

[chevellejnj72]

hmmm....Knapsack. That one is new to me. Ill have to do my research on that one otherwise I've heard of all the others.

modi123_1, on 17 November 2011 - 08:34 AM, said:

Out of curiosity - what class are you doing this for?

Its for an 3rd level algorithms class and a 3rd level advanced programming class.

iniaes, on 26 November 2011 - 01:36 PM, said:

Do you have a set of answers to compare, or do all the shortest possible permutations have to be generated by your program?

I don't think I entirely understand to be honest. If I do understand correctly, your asking if the output gets checked against a set of data being the answers to see if they match? If so, no. The program should find the quickest way. There is no way to have a pre-defined answer since it depends on the class availability. While for this project, I will only have one class db, it should handle changes to that db.

Manbearpig101, on 26 November 2011 - 02:11 PM, said:

Also, can you post a sample of the database? I'm really interested in writing a solution.

Recently have a death in the family so I will post my db later this week/the weekend. I am open to any suggestions even if the changes are to the DB.

Thanks for everyone's replies. I need to look into the Knapsack problem as the wiki description isn't very clear to me but does sound ideal from what I understand.

[Manbearpig101]

chevellejnj72, on 28 November 2011 - 01:21 PM, said:

hmmm....Knapsack. That one is new to me. Ill have to do my research on that one otherwise I've heard of all the others.

modi123_1, on 17 November 2011 - 08:34 AM, said:

Out of curiosity - what class are you doing this for?

Its for an 3rd level algorithms class and a 3rd level advanced programming class.

iniaes, on 26 November 2011 - 01:36 PM, said:

Do you have a set of answers to compare, or do all the shortest possible permutations have to be generated by your program?

I don't think I entirely understand to be honest. If I do understand correctly, your asking if the output gets checked against a set of data being the answers to see if they match? If so, no. The program should find the quickest way. There is no way to have a pre-defined answer since it depends on the class availability. While for this project, I will only have one class db, it should handle changes to that db.

Manbearpig101, on 26 November 2011 - 02:11 PM, said:

Also, can you post a sample of the database? I'm really interested in writing a solution.

Recently have a death in the family so I will post my db later this week/the weekend. I am open to any suggestions even if the changes are to the DB.

Thanks for everyone's replies. I need to look into the Knapsack problem as the wiki description isn't very clear to me but does sound ideal from what I understand.

I'm not entirely sure that this is a knapsack problem. It makes some sense, but I think it's more of an interval covering problem rather than a 0-1 knapsack problem.

[blackcompe]

Quote

I'm not entirely sure that this is a knapsack problem. It makes some sense, but I think it's more of an interval covering problem rather than a 0-1 knapsack problem.

It's simple. I'll use Sedgewick's analogy. Your a house robber. You go to the house with a bag that can accommodate a certain weight. There are many items you could take steal. Some heavy, some light. Some are more valuable than others. Which items should the robber choose to maximize his value. Suppose the bag can hold 15 lbs, and the following items are available: Clock (10 lbs, $5), Watch (1 lbs, $3), TV (3 lbs, $4), Shoes (2lbs, $3), Computer (11 lbs, $10), IPad (2 lbs, $6), Playstation 3 (7 lbs, $4). Which items do you take so that you maximize your total value?

I could take:

[Clock, IPad, TV] - 15 lbs, $15
[Computer, IPad, Shoes] - 15 lbs, $19
[Watch, TV, Shoes, IPad, PS3] - 15 lbs, $20

and so on. The last subgroup above is the best you can do.

How does that relate to your problem?

Suppose I have this case: I need to choose between CS1541 and CS1555 (they're competing for one spot). If I take CS1541 now, I can take CS1551 and CS1555 next term. CS1541 is a pre-requisite for CS1551, and CS1555 is available next term (and I've fulfilled the pre-req). If I take CS1555 now, I can't take CS1551 next term, because I have to take CS1541, even though CS1551 is offered. I'll have to take CS1551 in 2 terms.

So you end with a graph representing the total amount of time:

		 Current
		/		\
	 CS1541    CS1555
	   |		 |
	 CS1551	   CS1541
	 CS1555      |
	           CS1551

When I'm at Current I want to take the next best move that ultimately results in the least amount of terms. At each leaf I've completed the same courses, but by choosing CS1541 now, I get there 1 term faster. That's the theme with all dynamic programming questions. Try and take the best move at every decision point. DP is a top-down solution. The other alternative is a recursive (bottom-up) solution, where you generate all the possible paths down the tree.

The Knapsack problem can be solved with dynamic programming or recursion. Recursion takes O(n!) time, which may be suitable for small input sizes. You can significantly speed up computation time with memoization for recursive solutions.

Let's try to visualize a recursive (bottom-up) solution. Suppose you graduate in 3 terms. Basically, you choose some random permutation of courses for your first term. On the second term try another random permutation of courses. For the third term try all permutations. You have to keep some kind of cost variable that decides which path is the current best. Once you've tried all perms for the 3rd term, back track to the 2nd term, create a new permutation for that, and then go down the tree into the 3rd term again and try all possible perms.

If you incorporate conflicts into that algorithm, then your path will spill into 4 or more terms since some permutations (in your 1st and 2nd terms) will have 3, 4, or 5 classes instead of 6 (the max). That's because some classes may not be available or there may be time conflicts, and there are no more classes that you can replace them with.

You'll have a list of available courses, where you remove selected classes, that you'll pass into your recursive calls as a copy; you'll constantly check to see if you've fulfilled your total requirements at every recursive call before you attempt to create a new term semester.

So your generating all possible schedules. Like I said, it's not efficient -- especially for this application -- but it's an easy solution to implement. Unfortunately, your application might not even finish the calculation.

I don't have a lot of experience with dynamic programming, so my advice is limited. In TSP, you have to assign a cost to each edge, and I can't see how that would work in this scenario. A simple DP solution for TSP is 2-opt. Here's the DP solution (top-down) for the knapsack problem (on the next page, Sedgewick shows the recursion tree visualization in case you didn't understand my example). You should be able to adapt this, since it's the opposite of the bottom-up solution I talked about. If you can, your application will be must faster. Also consider posting your question on StackExchange (in the StackOverflow or Theorectical CS forums), tagged as "Algorithms." Maybe ask if this is similar to the Knapsack problem, or ask for someone to suggest a similar DP problem to study. Either way good luck!

This post has been edited by blackcompe: 28 November 2011 - 04:45 PM

[Manbearpig101]

blackcompe, on 28 November 2011 - 04:40 PM, said:

Quote

I'm not entirely sure that this is a knapsack problem. It makes some sense, but I think it's more of an interval covering problem rather than a 0-1 knapsack problem.

It's simple. I'll use Sedgewick's analogy. Your a house robber. You go to the house with a bag that can accommodate a certain weight. There are many items you could take steal. Some heavy, some light. Some are more valuable than others. Which items should the robber choose to maximize his value. Suppose the bag can hold 15 lbs, and the following items are available: Clock (10 lbs, $5), Watch (1 lbs, $3), TV (3 lbs, $4), Shoes (2lbs, $3), Computer (11 lbs, $10), IPad (2 lbs, $6), Playstation 3 (7 lbs, $4). Which items do you take so that you maximize your total value?

I could take:

[Clock, IPad, TV] - 15 lbs, $15
[Computer, IPad, Shoes] - 15 lbs, $19
[Watch, TV, Shoes, IPad, PS3] - 15 lbs, $20

and so on. The last subgroup above is the best you can do.

How does that relate to your problem?

Suppose I have this case: I need to choose between CS1541 and CS1555 (they're competing for one spot). If I take CS1541 now, I can take CS1551 and CS1555 next term. CS1541 is a pre-requisite for CS1551, and CS1555 is available next term (and I've fulfilled the pre-req). If I take CS1555 now, I can't take CS1551 next term, because I have to take CS1541, even though CS1551 is offered. I'll have to take CS1551 in 2 terms.

So you end with a graph representing the total amount of time:

		 Current
		/		\
	 CS1541    CS1555
	   |		 |
	 CS1551	   CS1541
	 CS1555      |
	           CS1551

When I'm at Current I want to take the next best move that ultimately results in the least amount of terms. At each leaf I've completed the same courses, but by choosing CS1541 now, I get there 1 term faster. That's the theme with all dynamic programming questions. Try and take the best move at every decision point. DP is a top-down solution. The other alternative is a recursive (bottom-up) solution, where you generate all the possible paths down the tree.

The Knapsack problem can be solved with dynamic programming or recursion. Recursion takes O(n!) time, which may be suitable for small input sizes. You can significantly speed up computation time with memoization for recursive solutions.

Let's try to visualize a recursive (bottom-up) solution. Suppose you graduate in 3 terms. Basically, you choose some random permutation of courses for your first term. On the second term try another random permutation of courses. For the third term try all permutations. You have to keep some kind of cost variable that decides which path is the current best. Once you've tried all perms for the 3rd term, back track to the 2nd term, create a new permutation for that, and then go down the tree into the 3rd term again and try all possible perms.

If you incorporate conflicts into that algorithm, then your path will spill into 4 or more terms since some permutations (in your 1st and 2nd terms) will have 3, 4, or 5 classes instead of 6 (the max). That's because some classes may not be available or there may be time conflicts, and there are no more classes that you can replace them with.

You'll have a list of available courses, where you remove selected classes, that you'll pass into your recursive calls as a copy; you'll constantly check to see if you've fulfilled your total requirements at every recursive call before you attempt to create a new term semester.

So your generating all possible schedules. Like I said, it's not efficient -- especially for this application -- but it's an easy solution to implement. Unfortunately, your application might not even finish the calculation.

I don't have a lot of experience with dynamic programming, so my advice is limited. In TSP, you have to assign a cost to each edge, and I can't see how that would work in this scenario. A simple DP solution for TSP is 2-opt. Here's the DP solution (top-down) for the knapsack problem (on the next page, Sedgewick shows the recursion tree visualization in case you didn't understand my example). You should be able to adapt this, since it's the opposite of the bottom-up solution I talked about. If you can, your application will be must faster. Also consider posting your question on StackExchange (in the StackOverflow or Theorectical CS forums), tagged as "Algorithms." Maybe ask if this is similar to the Knapsack problem, or ask for someone to suggest a similar DP problem to study. Either way good luck!

Yea, but how would you use this to create an actual schedule? What would you weight the actual classes? I don't really think this would be an easy translation of the 0-1 knapsack problem.

[blackcompe]

Quote

Yea, but how would you use this to create an actual schedule? What would you weight the actual classes? I don't really think this would be an easy translation of the 0-1 knapsack problem.

If in some way it's similar to knapsack I can't explain how. I too wondered how I could assign a weight to classes, and I determined I can't. I said that they were similar because the goal is to make the best possible schedule for each semester on the fly, just like picking the right item to go into the knapsack (with the DP solution). In short, your right, it's really not a knapsack problem.

But I'm pretty sure my bottom-up solution would work. It really isn't specific to knapsack at all. It's simply recursively finding all possible schedules. The bottom-up knapsack solution (which is shown in Sedgewick's text that I linked to) uses sort of the same concept, so that's why I said to look at it. But recursively generating permutations of a string is just as similar. I could probably code up a simplified example, but that's too much work. A bottom-up solution would be highly in-efficient. I'm tempted to say you could add memoization in some capacity to prevent re-computing sub problems that have already been solved.

This post has been edited by blackcompe: 28 November 2011 - 08:20 PM

[Nikitin]

That's just a simple tree traversal algorithm.

Each level of the tree represents a semester. So first level is semester 1, the next level is semester 2, etc. Each node represents the classes you're currently taking. The node also stores information about classes you already took (so you know which prerequisites you have satisfied for future schedules).

Each node will have a child for every valid next-semester class schedule. You need to take into account which classes are available, which have all prerequisites satisfied, etc.

Find the shallowest leaf node and that's it. You can use BFS / DFS / or whatever else you want to do it. That node won't have any children, since all required classes have been taken. It will be a leaf with the lowest level, which gives the number of semesters required to get to it.

You can optimize the searching, since you don't really need to generate all the possible scheduling at every step. But this brute force search will do. No need for TSP or Knapsacks. Though I'd love to see how people will reduce this problem to those ones.

[blackcompe]

Nikitin, on 28 November 2011 - 08:12 PM, said:

That's just a simple tree traversal algorithm.

Each level of the tree represents a semester. So first level is semester 1, the next level is semester 2, etc. Each node represents the classes you're currently taking. The node also stores information about classes you already took (so you know which prerequisites you have satisfied for future schedules).

Each node will have a child for every valid next-semester class schedule. You need to take into account which classes are available, which have all prerequisites satisfied, etc.

Find the shallowest leaf node and that's it. You can use BFS / DFS / or whatever else you want to do it. That node won't have any children, since all required classes have been taken. It will be a leaf with the lowest level, which gives the number of semesters required to get to it.

You can optimize the searching, since you don't really need to generate all the possible scheduling at every step. But this brute force search will do. No need for TSP or Knapsacks. Though I'd love to see how people will reduce this problem to those ones.

Awesome. My idea is comprehensible to others.

This post has been edited by blackcompe: 28 November 2011 - 08:27 PM