In many different social networks ,each person prefers to meet with people from their own community and are reluctant to switch affiliations.

In many different social networks ,each person prefers to meet with people from their own community and are reluctant to switch affiliations. If they switch, they pay a penalty for switching csw and if they visit a meeting of a community different from their own they pay a penalty for visiting cvis . Suppose all the meeting rooms have different colors representing communities. Let there be T time steps 1, …, T , n people 1, …, n, and R rooms. Then let a matrix of observed meetings of people in those times be Mij , where mij ⊆ {1, …, n} is the set of people (which may be empty) that met at time i in room j. For example, the matrix that describes the observations in figure 4.1 is M = [ {1; 2; 3} {4} {5} {1; 3} {2; 4} {5} {1; 3} {4} {2; 5} {1; 3} {4} {2; 5} {1; 3; 4} {2; 5} ] Given the M matrix and the penalties csw and cvis , give a dynamic programming algorithm that assigns a community color to each individual at each time step so that the total sum of all the penalty costs incurred by all the individuals is minimized. You can use the fact that the each person’s contribution to the overall minimum is independent. Prove that fact.