Is discrete mathematics a must in order to study algorithms?

At some level the answer is trivially “yes”.  If you want to analyze the complexity of an algorithm, you need to be able to model it mathematically and use that math to come up with an answer.  Because most algorithms are dealing with discrete objects and discrete steps, that means the applicable mathematics is the mathematics that deals with counting discrete things, which is discrete math.

Similarly, if you want a bound on an algorithms probabilistic behavior (i.e. what is its “average case performance”), you need to understand probability.  There are also algorithms whose complexity is defined by recurrence relations that are most easily understood if one is familiar with differential equations.  The more math you know, the more details you will understand.

That said, many algorithms depend mostly on simple forms of counting, so the knowledge of discrete math does not need to be particularly deep.  Certainly, if you want to understand the deep and tight bound of Tarjan’s “discrete union find” algorithm, you need fairly sophisticated mathematical intuition.  However, to see that it is nearly linear, but not quite, you can model and reason about it much more simply, but one has to “wave one’s hands” a lot more.

The one thing to remember is that we start teaching kids simple discrete math (i.e. counting) before they enter kindergarten and almost all elementary school math is a form of discrete math or geometry.  In truth, one needs a bit more sophistication than a typical elementary school kid to understand “combinations”, “permutations”, and “logarithms”, but once you can deal with those, large amounts of the analysis of algorithms is within your reach.

You basically can’t formalize even computational problems without it (without it leading to any particularly useful analysis).  We describe most of the important problems we study with Discrete Maths normally.  Necessary for analysis, formalization, and a proper understanding of computation if you want a rich understanding of Theoretical Computer Science (which you’ll need for Algorithms research).

Leave a Reply

Your email address will not be published. Required fields are marked *