Algorithm
The algorithm of TeamDivider is based on users' available time. We think the meeting time is the most important factor for a team. If a group team have no common meeting time, how can they share their thoughts? Skype and Slack may be alternative ways, but they are not perfect. Therefore, The principle of our algorithm is to make sure every group has at least one available meeting time.
Our algorithm is greedy. That means that we don't compare all the grouping schemas to get the optimal one, but always group the people who have the least meeting time with others at each time.This makes ensures three things:
- The algorithm can run very quickly.
- We can group the people with many meeting time at last.
- People with less meeting time can be grouped at first.
The complexity time of our algorithm is:
Here, we want to show the reliability and success of our algorithm by giving you our test result. One thing we need to define first is the success rate. What is success rate? For each group, if the group has at least one common meeting time, we call the group a success.
We calculate FreeTime rate. FreeTime rate is easy to understand. We have five days on Weekdays. If we are free on three of them, then the FreeTime rate is 3/5.
We have three graphs. They indicate how the success rates look if we run it a thousand times (each time, we generate 50 people with random free time). The difference between these graphs is the Freetime rate. In the first graph, the Freetime rate is 33%. In the second one, it is 40%. In the last one, we are comparing these two cases.
When the Freetime rate is 33%, the mean of the success rate is 65%. The minimum is about 20% and the maximum is 100%.
When the Freetime rate is 40%, the mean of success rate is 80%. The minimum is 50%. You can see that our algorithm performs better when the Freetime rate goes up.
Here, we directly compare the performances between 33% Freetime rate and 40% Freetime rate. Going up only 7% in Freetime increases the performance of our algorithm rapidly.
Now, we get that the Freetime rate is an important factor for our performance. We generate the following graph to show the how the success rates will work as the Freetime rate increases.
From the above graph, it can be easily seen that our greedy algorithm works very well when the Freetime rate is larger than 35%. But why is the success rate low when the Freetime one is lower than 35%? We think the reason is that when people have less free time, then the choices of grouping them with meeting time will be less. That is to say, the low FreeTime rate will make some people unavailable to meet with others. Therefore, even though we take the optimal algorithm by comparing all the possible schema, we cannot get high success rate. We can never find a way to group a person who has no matched time with others.
If you want to see my codes, please type the following URL in the top bar of your browser.
https://github.com/lightertu/TeamDivider/tree/algorithm
All the code about the algorithm is in the directory:
.
|
└───server
│ ├── algorithms
│ │ ├── greedy_algorithm.js -> the greedy algorithm is written in it
│ │ ├── RandomUserGenerator.js -> generate users with random free time
│ │ ├── test_greedy_Algorithm.js -> you can test the algorithm by running this file
| | ├── testResult.txt |
│ │ ├── testResult2.txt |-> some test result files
│ │ ├── testResult3.txt |
│ │ └── randomAlgorithm.js -> algorithm to randomly group people (we don't use it for now)
The algorithm is written in the file "greedy_algorithm.js".
We can run "test_greedy_Algorithm.js" to test it.
In the "test_greedy_Algorithm.js", we have two function:
The first function is used to generate users and to group them, print the "success rate".
Test_For_Only_One_Time(NumOfPeople, SizeOfGroups, TimeSlots, FreeTimeRate)
The second function is similar to the first one; however, it will run multiple times and print "success rate" for each time.
Test_Mutiple_Times(NumOfIterators, NumOfPeople, SizeOfGroups, TimeSlots, FreeTimeRate);
For each of the parameter, we have a global variable with the same name. Here is the explanation of the parameter:
NumOfIterators -> how many times you want to iterate
NumOfPeople -> for each time, how many number of people you want to test with
SizeOfGroups -> for each time and each group, how big you want the group to be?
TimeSlots -> How do you define the time.
FreeTimeRate -> We have five days on Weekdays. If we are free on three of them, then the FreeTime rate is 3/5.
You can change them if you want.
To run the test, code:
node test_greedy_Algorithm.js
Our greedy algorithm not only runs very quick but also has good success rate. We think it is the best one in our class