Selecting the project
Making this choice was a hard decision, considering the complexity of the project. There were other interesting topics for project, but none was challenging enough. After a bit of brainstorming and talking with professors, we realized that making a generalized timetable generator wasn't a good idea. It would have been too complex and using it would also be complicated for the end user. Thanks to M.S. Chavan Sir, he suggested us to make a customized generator for the second year computer department of PICT. It could be later extended for the third and fourth year with little modifications. The timetable generation for second, third and fourth years almost took one month through manual process. So making an automated generator was also helpful in terms of time of people who worked on it.
After the idea was finalized we decided that I will work on the algorithm, Aaryaman Vasishta would work on the user interface, generating PDFs and printing it directly from a connected printer. Akhil Koul would be working on an Android plugin which will enable the timetable to be accessed directly through a widget.
Working on the algorithm
So the first task was to get the exact constrains needed to be taken care of while assigning labs and lectures to classes. We have four classes, first three have timings 8:30 AM to 3:30 PM. The fourth class have timings 11 AM to 6 PM. Each class is divided into four batches. Lectures are common for all students of a class and labs are common for all students of a batch. While there are four classes, the number of available classrooms are only three. So at a point of time, there must be maximum three classes having lectures. There are total 5 lab subjects for each batch per week. Also, there are constrains on the laboratories available per lab subject. Teachers have to be assigned to classes as well as labs sessions. Individual teachers have varying lecture load and lab session load, which changes every year. So, it needs to be dynamic and should be accepted as input from end user.
After analyzing the constrains, the task was to find a proper algorithm to generate the actual timetable. I came up with an idea of doing it recursively using depth first search to arrange the lectures and labs in slots of batch. The problem was that the algorithm had a lot of time complexity in its worst case. But I realized that there was no worst case in this particular problem statement. There was only one case. So, if the recursive algorithm was implemented in the right way, it would run within seconds.
My approach
The manual generation of timetable is done by arranging labs to batches initially and when it is arranged, the lectures are arranged. So I decided to go with the same approach. I wrote a recursive algorithm which arranged first lab to each batch, then second lab to each batch and so on for all five labs. The algorithm worked just fine within time constrains but there was one problem. All batches belonging to the same class should either have all labs at a point of time or all lectures. This was the validation which was to be performed on the generated timetables for labs. With the validation, it was taking a lot of time for execution (greater than 5 minutes).
I changed my approach and first fixed if all the bathes of a class will have a lecture at a point of time or lab. So the condition checking after the algorithm has generated the timetable was not needed.
Why it worked, while the first one did not
Both algorithms were recursive, and both had a very large worst case complexity. But the recursive tree which was formed in the first case had very few successful nodes as leaf nodes (nodes where a valid timetable is generated). Once these nodes are encountered, a valid timetable is formed. So the algorithm took time. While in the second case, the number of success nodes as leaf nodes are greater in number. So it generated the timetable within seconds.
What next?
Next task was to take input of the number of teachers and their respective lectures load and labs load and arrange them to classes and batches. Arranging teachers was pretty easy. A small recursive function which arranged teachers to batches for each of the lab subjects.
The arrangement of labs and teachers to these lab slots is done. Next task would be to arrange the lectures to the classes and then teachers to these classes.
And Finally...
When the algorithm was completed till this point, it was just a single file with a sequential code with standard input and output. It had to be converted into a class which Aaryaman Vasishta could use for the interface and creating PDFs.
