Mathematics in Computer Science I
In this series, we will begin to explore the various ways in which the knowledge of mathematics can be applied to the field of Computer Science.
One of the most important branches of mathematics in the field of computer science is linear algebra. Formally, linear algebra is the branch of mathematics interested in linear equations and their representations through matrices and vector spaces.
Before we discuss some of the applications of linear algebra in computer science, let us briefly review the concepts of linear algebra. First, let’s take a look how we can model and represent systems of linear equations.
Consider the following system of equations:
One way of solving this system is through algebraic substitution. This involves picking one of the equations in the system and then solving for one of the variables in terms of the others. Then you would substitute the result into the other equations. By repeating this process on different variables, eventually you would arrive at the answer; however, this approach becomes very difficult and time consuming when dealing with even moderately sized systems.
A more scale-able solution would be to represent the system as a matrix, and solve it using elementary matrix operations.
The matrix representation of the equations above is:
The first, second and third columns contain the coefficients of the x, y and z variables respectively.
The elementary matrix operations that were mentioned previously mentioned allow us to add, subtract and swap rows. Additionally, they allow us to multiply rows by constants. The method of using elementary row operations to solve a system of equations is commonly referred to as row reduction.
To row reduce our matrix, we start off by swapping row two with row one yielding:
Subtract two times row three from row one:
Subtract five times row one from row two and three times row one from row 3.
Subtract three times row three from row two.
Multiply row two by one over twenty-three.
Finally, subtract five times row two from row one and add seventeen times row two to row three.
From our row reduced matrix we now know that the value of x is negative one hundred thirty-one over twenty-three , y is four hundred twenty-seven over twenty-three and z is one hundred fifty-five over twenty-three.
Now that we’ve refreshed our knowledge of how we can solve linear equations, let’s take a look at some of the ways we can apply this skill as computer scientists.
In the first part of my Let’s Build Our Own Regex Library tutorial series I introduced an algorithm for converting deterministic finite automata into regular expressions. The algorithm featured in that post works, but isn’t very efficient. However, now that we know how to efficiently solve systems of linear equations, we can design a new algorithm for the task that is leagues ahead of the original method in terms of time complexity. As an additional bonus, this new method tends to produce regular expressions that are more concise than those derived using other algorithms.
We will apply this new algorithm to the same DFA that we did in the aforementioned tutorial series:
For each state in the DFA, we create the equation:
Thus our system of equations looks like:
We can now plug this solution into Qr yielding:
Finally, we can plug our solution to Qr into the equation for Qq and solve:
Note that Qi represents the set of strings that our DFA recognizes when it starts at state qi thus since our DFA starts at state q, and we simplified Qq to the regular expression above, then we know that we’ve successfully converted the DFA into an equivalent regular expression.
The regular expression representation that we’ve obtained is our solution to Qq.
Understanding how to model problems as systems of linear equations and knowing the various methods one can employ to solve them is crucial in the development of many efficient algorithms such as this one.