Discrete mathematics: the secret weapon to break into a programming career!
Discrete Mathematics, or the study of mathematical structures which are infinite and discrete, as opposed to continuous in structure, have significant implications and deep connections with the field of computer science. These include the areas of algorithm design, graph theory, number theory and counting, where discrete mathematics techniques and theories are applied to datasets to solve practical issues in the field of computer science. This essay will discuss how these key areas can be applied to solve problems in computer science.
Applications of discrete mathematics in computer science
Discrete mathematics covers topics linked to logic, number theory, probability, recurrence and graph theory, which have several applications in computer science. For example, discrete mathematics is used to construct propositional logic for computer programs to reason through a given problem statement or decision making process.
Computers can tap on a system of boolean logic and truth tables to infer logical choices that can guide them down a specific decision path. For example, in the area of machine learning, computer programs can be trained on large image datasets to identify specific image characteristics which can drive decision points.
By identifying the shade, hue, tone or structural feature of an image at each step, computer programs can then follow a boolean logic structure to mathematically infer the potential nature of the image, and thus identify objects and settings from complex images (Hunter, 2021).
Mathematical induction principles are applied in iterative programming and functional programming to verify loops and recursive function calls. For example, Microsoft Research uses Haskell and F*, and Oracle uses Java 8 and Javascript, all of which are functional paradigms for the concepts of induction and recursion, which help to define and analyse algorithms and data structures (Tilahun & Ngnotchouye, 2017).
The branch of relational logic in discrete mathematics can also be used to implement languages such as SQL and domain-specific languages, to provide a hierarchy of logic for decision making programmes (Tilahun & Ngnotchouye, 2017).
Graph theory and the travelling salesman problem
Graph theory provides mathematically-founded data structures which can help computer scientists and programmers to model relationships between variables. Principally, graphs are a grouping of elements (dots and lines) which can represent relationships between pairs of objects, and allow for a systematic mapping of networks of pairs. These have applications in the area of social networks and navigation, where graph search algorithms are used to optimize connections between nodes.
Graph theory can also be applied for version control, functional programming and file system representation, which have vital applications in computer science (Hunter, 2021). Advanced graph theory concepts such as list structures and matrix structures can also be used as mathematical structures to map more complex datasets, such as natural ecosystems or political voting behaviors (Hunter, 2021).
Graphing theory can also be used to solve applied problem statements in computer science such as the travelling salesman problem (Ezugwu & Adewumi, 2010). The travelling salesman problem aims to identify the shortest possible route that visits a preset list of cities before returning to an origin city, given the distances between cities (Ezugwu & Adewumi, 2010). The problem allows for the application of discrete mathematics techniques such as combinatorial optimization to test the efficacy of optimization methods (Ezugwu & Adewumi, 2010).
Algorithm design
Algorithms define specific rules that guide the operation of a computer program or system. Discrete mathematics can ensure that algorithms are designed in a simple and efficient manner, which increases the speed of the algorithm’s operation. The programmer can also decide on the desired complexity measure to select the accurate algorithmic model, such as quadratic, linear, log-linear and exponential models, in order to optimize the algorithm’s efficiency (Schmidt et al, 2012).
Number theory
Number theory, a branch of discrete mathematics, can be applied to the computer science fields of cybersecurity, blockchain and cryptography analysis. This is because the cryptographic transactions required to verify such applications in a secure manner rely on mathematical foundations.
For example, modular arithmetic is used for hash functions to verify tools within applications (Ralston, 1982). Checksums, which are premised on hashing, help to verify the accuracy and safety of internet file transfers. Furthermore, hash maps serve as data structures premised on modular arithmetic to complete complex operations efficiently (Wigderson, 2019).
Counting
Counting techniques, a branch of discrete mathematics, allow computer programs and systems to develop quantitative intuition. For example, counting is used to calculate the quantity of valid passwords from a predetermined number of rules, to extrapolate the time required for a brute-force attacker to try all possible combinations.
In another application, the pigeonhole principle governs compression algorithms which help to reduce computer file sizes. Furthermore, counting helps to optimize resource usage in the deployment of resources and algorithms to complete computer-based tasks in a structured manner (Wigderson, 2019).
Probability
Discrete mathematics covers the field of probability, which serves as a systematic manner of assessing risk and likelihood of events in a computer program or system. For example, probability can be used to calculate the risk of a system crash for a given program due to bugs or external attacks. Software programmers can use probability as a tool to calculate the likelihood that a system would exceed its capacity, resulting in a system crash.
Furthermore, conditional probability can be deployed as a means of calculating the likelihood of unwanted inputs, such as spam emails or flawed protein design structures, from entering a system, and can reject these unwanted inputs before they are included in the computer program or system.
Real-world applications of discrete mathematics in computer science
Discrete mathematics has a range of natural applications in computer science. These include designing message routing paths, spam detection systems, cryptographic protocols and executing web searches, identifying strong sorting algorithms and verifying them for efficiency, and designing high-speed networks. These applications are underpinned by key discrete mathematics principles such as set theory, number theory, counting, probability and logic.
Conclusion
In conclusion, discrete mathematics has a variety of applications for computer science, in areas such as algorithm design, graph theory, number theory and counting. Computer science students with a background in discrete mathematics will thus be able to design, construct and manage algorithms, computer system architectures, distribution systems and operating systems in a more effective manner, by being able to identify and analyze key patterns from mathematical data to form functional tools and frameworks for computer programming.
References
Ezugwu, A. E. S., & Adewumi, A. O. (2017). Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems with Applications, 87(1), 70–78. https://doi.org/10.1016/j.eswa.2017.06.007
Hunter, D. J. (2021). Essentials of discrete mathematics. Jones & Bartlett Learning.
Ralston, A. (1982). De Bruijn sequences — a model example of the interaction of discrete mathematics and computer science. Mathematics Magazine, 55(3), 131–143. https://doi.org/10.1080/0025570X.1982.11976970
Schmidt, G., & Ströhlein, T. (2012). Relations and graphs: discrete mathematics for computer scientists. Springer Science & Business Media.
Tilahun, S. L., & Ngnotchouye, J. M. T. (2017). Firefly algorithm for discrete optimization problems. KSCE Journal of Civil Engineering, 21(2), 535–545.
Wigderson, A. (2019). Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press.
