Take the 2-minute tour ×

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of computer science.

share|improve this question
Just as an example: Graph Theory, as an area of discrete mathematics, is used all over the place. Since you mention complexity, it is interesting to note that many graph-theoretic problems are natural examples of NP-complete problems. –  Johannes Kloos Apr 24 '13 at 8:40
"Discrete mathematics" is a somewhat fuzzy concept -- but in some places it is essentially defined as "whatever mathematical subjects a generic computer science student needs to know". That's a pretty direct relation. –  Henning Makholm Apr 24 '13 at 11:37

1 Answer 1

I think a lot of it comes from the fact that discrete structures are easy to operate on in computing, and that computations themselves are usually modeled by discrete concepts.

For example, strictly speaking, formal language theory is a branch of discrete mathematics. It deals with finite structures (strings) in a from a countably-infinite universe. Modelling a yes/no problem as a set of strings allows for a large degree of formal reasoning about computations, so knowing the math/theory behind it is useful for a computer scientist.

Likewise, lots of problems can be reduced to discrete problems. For example, say you want to write a program which schedules a large set of classes so that no student has two classes at the same time. This is in fact a graph theory problem, known as "graph coloring". By knowing the theory behind graph coloring, a programmer realizes first that the problem is NP-complete, so there's not likely a fast general solution, but also can use pre-defined solutions for special types of graphs (chordal, comparability, planar, etc.)

Also, computer science and discrete math share a lot of ground. Both are heavily based in the concepts of recursion/induction.

Perhaps a more relevant question is why continuous mathematics isn't widely applied to computer science?

share|improve this answer

Your Answer


