What is Discrete Mathematics?
Discrete mathematics is a branch of mathematics concerned with the study of objects that can be represented finitely (or countably). It encompasses a wide array of topics that can be used to answer many tangible questions that arise in everyday life:
- Logic: Is a given argument logically sound, or does it contain a fallacy?
- Number theory: If a leap year happens every 4 years and US Senators are elected every 6 years, how frequently is a Senate election held in a leap year?
- Counting: How many different outfits can you make from the clothes in your closet?
- Probability: What are your chances of winning the lottery? (Hint: very, very low)
- Recurrences: How much will you pay over the lifetime of a mortgage if interest is compounded monthly?
- Graph theory: What is the fastest way to get from your home to your workplace?
All of these topics are covered in the MPCS Discrete Mathematics immersion course.
How is discrete mathematics used in computer science?
Discrete Mathematics provides an essential foundation for virtually every area of computer science, and its applications are correspondingly vast.
At the most fundamental level, all of a computer’s data is represented as bits (zeros and ones). Computers make calculations by modifying these bits in accordance with the laws of Boolean algebra, which form the basis of all digital circuits (which are represented as graphs). Low-level programming languages rely directly on logical operators such as and, not, and or. Software developers using high-level languages will often work to optimize their code by minimizing the number of low-level operations, and may even operate directly on bits. Programmers also use Boolean logic to control program flow -- that is, which instructions are executed under certain conditions.
When programming, it is important to be confident that your code will achieve the desired results. Programs can be described precisely with mathematics, and the tools of propositional logic can be used to reason about their correctness. This skill is critical to the design and analysis of algorithms, a core area of computer science. Iterative programming and functional programming are two major paradigms which rely upon the principle of mathematical induction to verify their loops (for and while) and recursive function calls, respectively. Logic is the language used for most formal specification languages, and is fundamental for understanding much of the literature in verification and in programming language foundations and design. For instance, languages in the SQL family are just implementations of relational logic with added features, and many other domain specific languages are similarly implementations of some particular logical calculus. Program verification and formal methods are seeing increasing adoption in industry, and are being used in tandem with traditional testing techniques to increase the confidence that software behaves as it is supposed to.
Induction and recursion are key concepts in understanding the functional paradigm for programming, which is seeing increased adoption in industry with companies such as Apple (Swift), Microsoft (F#), Microsoft Research (F*, Haskell), Oracle (Java 8, Javascript), Facebook (Haskell), and Amazon adopting the paradigm both for niche tasks and general use. Recurrences are also a common way of defining algorithms and data structures, even if the concrete implementation is defined iteratively. Furthermore, they form the backbone for many models of computation and for more theoretical areas of computer science. They are also fundamental for software verification, another area of computer science that is increasing in adoption, as the correctness and security properties of software become increasingly more critical in sensitive applications.
Number theory has critical applications across blockchain, cryptography, and computer security. Modern cryptographic systems must be mathematically correct in order to secure users’ data from malicious adversaries. Modular arithmetic is the mathematical basis for hash functions, which are extremely useful tools with many applications. Checksums, based on hashing, can verify that files transferred over the internet do not contain errors. Data structures such as hash maps rely on modular arithmetic for efficient operations. Number theory also has memory-related uses in computer architecture and operating systems.
Counting techniques are used to develop quantitative intuition. For example, they can be used to determine the number of valid passwords which can be formed from a given set of rules, and how long it would take for an attacker to brute force all of them. The pigeonhole principle explains why there is no universal lossless compression algorithm: every compression algorithm must make certain files smaller and others larger. Therefore each compression algorithm is designed for compressing a different type of file (text, images, video, etc). Counting is helpful in analyzing the complexity of algorithms. In real-world applications there are complicated tradeoffs between several different resources that are available. Certain tasks need fast algorithms and can afford using a lot of space for achieving speed, while others do not have much space and therefore need to sacrifice time for space. In more complex situations, a sweet spot in resource usage needs to be achieved so that the system is not starved of a resource and can keep running. Counting is the basis for making such considerations in a structured manner and can in fact be used to give formal guarantees about resource usage.
Probability is ubiquitous not only in Computer Science but also in other quantitative fields. Software engineers use probability to assess risk. For example, when designing a certain system, probability can be used to calculate the likelihood that the system will experience a peak load beyond its capacities and crash. Similarly, probability can be used to measure the reliability of a network. Conditional probability has many applications in machine learning, which is used for tasks ranging from calibration of spam filters to developing better medical treatments by folding proteins. Randomized algorithms are often more efficient in practice, and sometimes are the best known algorithms for approximating tasks that are too hard to compute exactly. Probability is also one of the foundations of statistics, and therefore, also of data science, one of the hottest fields in industry at present. Studying probability in the context of computer science gives students a quantitative intuition which is useful throughout their careers and everyday life.
Graphs are powerful data structures which are used to model relationships and answer questions about said data: for example, your navigation app uses a graph search algorithm to find the fastest route from your house to your workplace. Linked-In uses a graph to model your professional network, as does your telecommunications company for its cellular network (in fact, network is an alternate name for a graph). Computer scientists use graphs extensively: to represent file systems, for version control, and in functional programming, deep learning, databases, and many more applications.
How do MPCS students benefit from learning discrete mathematics?
Mastering discrete mathematics positions an MPCS student for success in both the Masters Program and also a career in software engineering or a similar technical field. Principles of discrete mathematics are utilized in many courses in the MPCS, including Algorithms, Computer Architecture, Computer Systems, Databases, Distributed Systems, Functional Programing, Machine Learning, Networks, Computer Security, and Operating Systems.
The problem-solving techniques honed in discrete mathematics are necessary for writing complicated software. Students who are successful in discrete mathematics will be able to generalize from a single instance of a problem to an entire class of problems, and to identify and abstract patterns from data. These are valuable real-world skills, particularly because, unlike knowledge of a specific framework, platform, or programming language, they are highly transferable.
Finally, discrete mathematics and algorithms constitute a lingua franca for computer scientists and software developers. Since these concepts are both universal and essential to the field, they are widely used to communicate with peers, and form a major component of many technical interviews.
