CODEWITHSUNDEEP
javaalgorithm
jaywalker
jaywalker

Reputation: 1146

Group Students on the Basis of Marks

I am developing an application in java which suggests possible groups of students (two or three students per group) on the basis of the marks they obtain in various subjects. I would like to study similar algorithms before i devise my own. For instance of there are a total of two courses and also two students per group than the algorithm should pair students up in groups in such a way that student a should be good in subject 1 whereas student b should be good in subject b.

Detailed Explanantion: The input will be in this form:

student1<90.38<labs
Student1<93.01<exam
Student2<90.38<labs
Student2<85.20<exams
.         .       .
.         .       .         
.         .       .
.         .       .
Studentn<61.48<exams

The first part is the unique id of each student, the second part is marks obtained and the third part is the particular course component the marks have been obtained.

The algorithm should create groups of two of students which complement each other on the basis of marks obtained in each component, labs as well as exams.

Output should be somewhat like 

student1|student13|
student17|student15|
student8|student10|
.               .
.               .
.               .
studentn|studentm|

where each line corresponds to a single group of two students.

Upvotes: 2

Views: 690

Answers (2)

HAL9000
HAL9000

Reputation: 3761

I try to suggest you a Pareto optimal algorithm:

  • build a single tree
  • the first node is about choosing the number of groups: for example if you have 10 students you can have a number of groups from 4: {3,3,2,2} to 5: {2,2,2,2,2}. In this way, in this simple example, the first node has only TWO sons, one with 4 groups and one with 5 groups.
  • You start expanding the node with less groups and you generate all possible combinations (without repetitions).
  • For example you generate combination {3,3,2,2}. From here you assign in order a student and you generate another node: you start from student s1 { {s1,,}, {,,}, {,}, {,} }, then you add s2: { {s1,s2,}, {,,}, {,}, {,} } etc. Each time you arrive to a final node, you calculate the value of the solution. One example of value could be the sum of the mean difference between groups, differentiated for subject and component (or you can do a weighted sum on lab and exam, if you prefer). For example with two subjects and two components per subject you will have 4 incomparable values. The solution would be something like { D1, D2, D3, D4} where the value Dn is the average distance between groups on value n.
  • If a solution is Pareto optimal or is the only solution available, you add it to the set of feasible solutions. Each time you get a solution you have to compare it's optimality with all the solutions in the solution set. If a solution of the set is dominated by this solution, you have to remove it from the set.
  • Finally you will have a set of Pareto efficient solutions from which to choose from. The choice can be done by apply some solution concept, in this case I would use social efficiency, which means to choose from the Pareto frontier the solution which minimizes the sum of differences in the all values. This means SocialValue = -(*D1*+*D2*+*D3*+*D4*). Note the sign minus: it's because you have to maximize SocialValue, which is the minimization of the sum of values.

Upvotes: 0

Anirban Nag &#39;tintinmj&#39;
Anirban Nag &#39;tintinmj&#39;

Reputation: 5772

This is quite easy. I will tell you only algorithm.

  1. Make two TreeMap. One with value of all the marks in exam and one with all the marks in lab. Use Student ID as the key.

  2. Now start with first index of each TreeMap and pick the values.

    2.1. If both values have same key then pick the next one else pick both different key and remove the pair from the maps.

An example may help. Suppose the scenario is like below

Student ID      lab       exam

 1              80         10
 2              50         50
 3              40         70
 4              20         40

So after creating TreeMap it will look like

labMap      examMap
<K,V>        <K,V>

<1,80>       <3,70>
<2,50>       <2,70>
<3,40>       <4,70>
<4,20>       <1,70>

So you can see we will first take 1 and 3.

Then as 2 and 2 is same we will choose 2 and 4.

After 3 and 2.

Atlast 4 and 1.

Upvotes: 2

Related Questions