Why Discrete Math

Introduction

Discrete mathematics is the study of mathematical structures that are distinct and separable; i.e. structures that are “discrete.” The branches of mathematics that this field is comprised of are very useful in computer science. Before the invention of the computer, mathematicians focused their efforts on developing the branches of continuous mathematics as it is better suited to quantify properties that arise from the study of physical sciences (such as physics, chemistry, etc…) which was the main focus of early scientists. While the concepts of discrete math were developed by some of the earlier mathematicians in recorded history, they found very little application before the invention of the computer and the development of the field of computer science. Branches of discrete math that are most important to computer science include:

• logic and proofs
• sets and set theory
• recursion and recurrence relations
• number theory
• combinatorics

The Need for Proofs

Computers are good at implementing algorithms that would be too tedious or error-prone for a human to do manually as they could do them for an extended period without getting bored or making mistakes. An algorithm is simply a series of instructions that are repeatedly executed until a certain task is complete. When you follow the recipe to prepare your favorite dish, you are following an algorithm. When designing an algorithm, we do need to prove that it is correct. It is not possible to test an algorithm by manually computing it and using that to verify the computer’s results. One of the most powerful proof methods to conduct is called a proof by induction in which an algorithm is verified by proving that it is valid for some base case and then proving that it also works for the base case’s immediate successor which is known as the inductive step. This proof technique is analogous to the toppling of dominos; when the first domino falls over (the base case) it will knock over the next domino (inductive step) which will continue to knock over a potentially infinite amount of succeeding dominos.

Set Theory

Another important branch of discrete math is set theory. Set theory is the study of collections of discrete objects (known as a set), their properties, as well as the mathematical operations that can be performed on them. This is crucial to the field of computer science because it presents a formal way of dealing with collections. Common topics in set theory are:

• set construction
• counting techniques
• set combinations
• set exclusions.

This field also has major applications in probability theory.

Number Theory

As the entire world rushes to connect everything to the internet, online security becomes a major concern. To protect everyone and their data from bad actors on the internet, advancements in cryptography have been made. Cryptography is a branch of computer science that is primarily concerned with the study of algorithms that are used to secure data. A majority of the security algorithms employ ideas from number theory, the study of properties and relations of numbers. A particularly important and useful subject is that of congruence. We say two numbers are congruent if they yield the same remainder when divided by some number n. This has many useful applications in cryptography and beyond.

Sequences and Series

A series of numbers can be used to express many things ranging from how to arrange books on a shelf to an attempt to model the population of rabbits in a forest. The study of how to arrange a sequence is explored in the branches of combinatorics and recurrence relations. Combinatorics is a branch of mathematics that studies methods of how to compute the number of ways things can be arranged while considering the order of arrangement matters or not. If a number in a sequence can be expressed in terms of earlier numbers, it is known as a recurrence relation. The subject of recurrence relations (implemented as recursive functions on a computer) explores how to define a recurrence relation as well as how to solve one. A common application of this field is computing the number of ways to do something in terms of the number of ways to do it for a smaller number (ex: how to climb n stairs by climbing one or two steps at a time).

Binary: a Number System for Computers

The traditional number system everyone is familiar with was invented by Hindu mathematicians many centuries ago. This base-10 number system is known as the decimal number system as every possible number in this system is composed using only ten digits. It is theorized that this number system was invented because humans have 10 fingers they can use to count. However, computers are essentially billions of tiny circuits configured to behave like switches. A switch can exist in only one of two discrete states. A switch is either “on” (represented by a 1) or “off” (represented by a 0) suggesting that computers only have two “fingers” they can use to count; therefore, for a computer, it is better to express numbers using a base-2 number system. This system is known as the binary number system.