Using Computer Science Algorithms to Promote Diversity in College Dorms

7 min readJul 4, 2022

Introduction:

When enumerating on the key aspects behind the success of a household company, diversity is a crucial factor that should not be ignored. Having a diverse workforce leads to a variety of different perspectives, as well as increased creativity and a higher level of innovation. However, some people in today’s society are closed to those from other backgrounds and hold prejudices towards those with a different skin color or gender. To combat this, we must be exposed to people from different backgrounds at a young age. One solution to this problem that many have already proposed is making college dormitories more diverse. To ensure that students receive the best dormitory experience possible, students of similar ages yet different socioeconomic backgrounds should be placed in the same dormitory to increase racial awareness within a college campus.

Applying technology to solve many day to day problems is my passion. One way of solving this problem is by using a computer science algorithm. There are many algorithms that can output a desirable arrangement, but a solution to this problem that is both computationally efficient and outputs optimal arrangements is a graph algorithm. Specifically, we can use a matching algorithm to solve this problem. A matching in a bipartite graph is a set of edges chosen in such a way that no two edges share an endpoint. A maximum matching is a matching of maximum size (maximum number of edges). By applying a maximum cardinality bipartite matching to this problem, the optimal scenario can be achieved in polynomial time.

What is a Graph?

Many of the algorithms that are commonly used in computer science often depend on simple yet elegant concepts. One example is the “graph”. A graph is a data structure that consists of multiple “nodes”. Each of these nodes can be connected through other nodes through edges. These edges can either be “undirected”, indicating that the relationship between nodes is a two-way relationship, or “directed”, indicating that the relationship is only one-way. An example of a graph is illustrated above. Graphs are commonly used in computer science, and there are many algorithms that can be implemented with a graph. Similarly, there are many different types of graphs that all have different uses. The 2 types of graphs that will be used in our algorithm are a bipartite graph and a flow network.

Previous Graph Turned Into Bipartite Graph

A bipartite graph, formally, is a graph such that the nodes can be divided into disjoint sets A and B such that no node shares an edge with another node from the same set. In layman’s terms, imagine if we were to color each node red or blue. A bipartite graph would be a graph such that no red node shares an edge with another red node, and no blue node shares an edge with another blue node. A bipartite graph is powerful. It allows to divide information into two categories and create relationships among them. This will be incredibly useful in our algorithm.

The second type of graph that will be used in our algorithm is a flow network. A flow network is a directed graph such that the weights of each edge equal the capacity of the “flow” that can be sent through the edge. If this is hard to think about, suppose you have a plumbing system. Each pipe has a label displaying the maximum gallons of water that can be sent through the pipe. This is exactly what a flow graph symbolizes. In addition to this, there is one source node and one sink node through which all flow starts and ends at. The concept of a flow network will be incredibly useful for solving matching problems.

Matching Algorithms

Now that we have established a baseline, we can move on to the core topic of this article: the maximum cardinality bipartite matching algorithm.

Suppose we have a bipartite graph, with some nodes being labeled as “blue” and others being labeled as “red”. We can draw edges between some blue nodes and red nodes, suggesting that they can be matched to each other. Now that we have our new graph, we can turn this into a flow network in order to find our maximum matching. Set the flow for all of the existing edges in the graph to 1. Then create a source node that has directed edges to all of the blue nodes with a flow capacity of one, and a sink node that has directed edges from all of the red nodes with a flow capacity of one. This is our new flow network, and we can apply flow algorithms to this new graph in order to find our maximum bipartite matching. Specifically, the flow algorithm that we will apply to this new graph is known as the Edmond-Karp algorithm. The Edmond-Karp algorithm is used to find the maximum flow that can be sent from a source to a sink.

This algorithm is somewhat complicated at first, but becomes simpler once it is practiced. The Edmond-Karp algorithm consists of 2 steps:

For every edge in our graph, the algorithm constructs reverse edges that serve as “negative flow” for our algorithm. These are known as residual edges, and the resulting graph is known as a residual graph. This will be important in case we want to backtrack in our algorithm
For every iteration, the algorithm finds the shortest augmenting path using a BFS algorithm. An augmenting path is a path that has a positive residual capacity - or a path such that the total flow capacity minus the total current flow is positive.
The maximum possible flow of the augmenting path is derived and added to the algorithm’s answer. The algorithm goes back to step 2 until no more augmenting paths can be found.

When we apply the Edmond-Karp algorithm to our matchings residual graph, something peculiar happens. The maximum flow is actually equal to the total number of matchings in a maximum matching. This makes sense if you think about it! Each unit of the maximum flow from the source node in our matchings graph must be sent to a separate blue node. This means that the number of blue nodes involved in our algorithm, or the number of total matchings, must equal the maximum flow! To find the edges involved in the matching, just mark the edges that are used as augmenting paths by the Edmond-Karp algorithm.

Procedure:

Now that a basic understanding of the maximum bipartite matching algorithm has been obtained, we can proceed with the method by which we can organize college dormitories.

The algorithm described in this paper will first require data detailing each student’s gender, age, ethnicity and economic background. We can divide the input into 4 groups:

Male <= 23
Male > 23
Female <= 23
Female > 23

For each category, we will create a separate bipartite graph.

The algorithm described in this paper will iterate over the candidates in a category and parse them into nodes in a graph. Then, 2 groups will be created that satisfy the bipartiteness condition required. The “red” group — referring to students who come from a total annual family income of <$70000, and the “blue” group — referring to students who come from a total annual family income of >= $70,000. Then, for each node in the red group, a directed edge can be drawn between students of different cultural backgrounds. This shows that placing these students in the same dormitory will satisfy the requirements that we were initially trying to achieve.

After completing the graph, the matching algorithm will begin. The matching algorithm will first draw a directed edge between an arbitrary source and each red node, and each blue node and an arbitrary sink. Each edge will then be given a weight of 1. The matching algorithm will then use the Edmond Karp algorithm to calculate the maximum flow. This will result in a maximum matching and a list of optimal arrangements.

After the matching algorithm is complete, if there are any nodes left, the algorithm will rudimentarily attempt to combine each red node with an arbitrary blue node, before trying to combine each red node with a red node and each blue node with a blue node. After the algorithm is complete, it will generate a list of pairs. For a dormitory of 4, 2 pairs can be combined with each other.

Conclusion:

Diversity is important. For many years, America’s institutions have largely been dominated by the same demographic. This leads to systemic racism and the perpetuation of a cycle that suppresses the voices of minorities. To combat this, we must take a step in the right direction.

The digital age is an age that is unprecedented in modern history. In today’s age, we can communicate with people who are thousands of miles away in the blink of an eye. We can perform operations that would have taken years to do by hand in a split second. We can extend human behaviors to an object, and make it think on its own.

We must use the tools that our current time period has equipped us with to combat problems that have plagued humanity for centuries. For the first time in a long time. we are seeing change on an exponential scale in regard to technology and the way our economy functions. Let improved diversity and the improvement of society be a part of this massive turning point in the era of human history.