Welcome to Lecture Note Two – Introduction to Discrete Mathematics, In this lesson, we shall understand what is discrete maths, why do we need it and how do we apply it in our day-to-day activities.
Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.
Introduction to Discrete Mathematics – DMS
What is Mathematics?
Mathematics is the science and study of quality, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish the truth by rigorous deduction from appropriately chosen axioms and definitions.
There is debate over whether mathematical objects such as numbers and points exist naturally or are human creations. The mathematician Benjamin Peirce called mathematics “the science that draws necessary conclusions”. Albert Einstein, on the other hand, stated that “as far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality.”
Through abstraction and logical reasoning, mathematics evolved from counting, calculation, measurement, and the systematic study of the shapes and motions of physical objects. Practical mathematics has been a human activity for as far back as written records exist. Rigorous arguments first appeared in Greek mathematics, most notably in Euclid’s Elements. Mathematics continued to develop, in fitful bursts, until the Renaissance, when mathematical innovations interacted with new scientific discoveries, leading to an acceleration in research that continues to the present day.
Today, mathematics is used throughout the world as an essential tool in many fields, including natural science, engineering, medicine, and the social sciences. Applied mathematics, the branch of mathematics concerned with the application of mathematical knowledge to other fields, inspires and makes use of new mathematical discoveries and sometimes leads to the development of entirely new disciplines. Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind, although practical applications for what began as pure mathematics are often discovered later.
Introduction Discrete Mathematics
Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It’s often said that mathematics is useful in solving a very wide variety of practical problems which broadly conceived, underpins about half of pure mathematics and of operations research as well as all of computer science.
As time goes on, more and more mathematics that is done, both in academia and in industry, is discrete. But what are the actual applications people talk about when they say discrete mathematics can be applied? and What problems are being solved? Mathematics can be broadly classified into two categories:
Continuous Mathematics is based upon a continuous number line or real numbers. It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks.
Discrete Mathematics involves distinct values; i.e. between any two points, there are a countable number of points. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects and can be presented as a complete list of those pairs.
Discrete Mathematics and its Applications
Discrete mathematics is the study of mathematics confined to the set of integers. And its applications in the fields of continuous mathematics such as calculus and algebra are obvious to many, the applications of discrete mathematics may at first be obscure.
Nevertheless, discrete math forms the basis of many real-world scientific fields especially computer science. The primary techniques learned in a discrete math course can be applied to many different fields.
Discrete Math in Cryptography
The field of cryptography, which is the study of how to create security structures and passwords for computers and other electronic systems, is based entirely on discrete mathematics. This is partly because computers send information in discrete or separate and distinct bits.
Number theory, one important part of discrete math, allows cryptographers to create and break numerical passwords. Because of the quantity of money and the amount of confidential information involved, cryptographers must first have a solid background in number theory to show they can provide secure passwords and encryption methods.
Discrete Math in Relational Databases
Relational databases play a part in almost every organization that must keep track of employees, clients, or resources. A relational database connects the traits of a certain piece of information.
For example, in a database containing client information, the relational aspect of this database allows the computer system to know how to link the client’s name, address, phone number, and other pertinent information.
This is all done through the discrete math concept of sets. Sets allow information to be grouped and put in order. Since each piece of information and each trait belonging to that piece of information is discrete, the organization of such information in a database requires discrete mathematical methods.
Discrete Math in Logistics
Logistics is the study of organizing the flow of information, goods, and services. Without discrete mathematics, logistics would not exist. This is because logistics makes heavy use of graphs and graph theory, a sub-field of discrete math.
Graph theory allows complex logistical problems to simplify into graphs consisting of nodes and lines. A mathematician can analyze these graphs according to the methods of graph theory to determine the best routes for shipping or solving other logistical problems.
Discrete Math in Computer Algorithms
Computer Algorithms are a set of rules that govern how a computer operates. These rules are created through the laws of discrete mathematics. A computer programmer uses discrete math to design efficient algorithms. This design includes applying discrete math to determine the number of steps an algorithm needs to complete, which implies the speed of the algorithm. Because of discrete mathematical applications in algorithms, today’s computers run faster than ever before.
Everyday applications of discrete mathematics
Computers run software and store files. The software and files are both stored as huge strings of 1s and 0s. Binary math is discrete mathematics.
Networks are, at the base, discrete structures. The routers that run the internet are connected by long cables. People are connected by social media (“following” on Twitter, “friending” on Facebook, etc.). The US highway system connects cities with roads.
Doing web searches in multiple languages at once, and returning a summary, uses linear algebra.
Google Maps uses discrete mathematics to determine the fastest driving routes and times. There is a simpler version that works with small maps and technicalities involved in adapting to large maps.
Scheduling like deciding which nurses should work which shifts, or which airline pilots should be flying which routes, or scheduling rooms for an event, or deciding timeslots for committee meetings, or which chemicals can be stored in which parts of a warehouse are solved either using graph coloring or using combinatorial optimization, both parts of discrete mathematics. One example is scheduling games for a professional sports league.
An analog clock has gears inside, and the sizes/teeth needed for correct timekeeping are determined using discrete math.
Wiring a computer network using the least amount of cable is a minimum-weight spanning tree problem.
Encryption and decryption are part of cryptography, which is part of discrete mathematics. For example, secure internet shopping uses public-key cryptography.
Area codes: How do we know when we need more area codes to cover the phone numbers in a region? This is a basic combinatorics problem.
Scaling COVID-19 testing by more efficiently using patient samples is assisted by linear algebra. Designing password criteria is a counting problem: Is the space of passwords chosen large enough that a hacker can’t break into accounts just by trying all the possibilities? How long do passwords need to be to resist such attacks?
Machine Job Scheduling: Scheduling tasks to be completed by a single machine uses graph theory. Scheduling tasks to be completed by a set of machines is a bin-packing problem, which is part of discrete optimization. Google describes the issue for multiple types of jobs on multiple machines.
Railway planning uses discrete math: deciding how to expand train rail lines, train timetable scheduling, and scheduling crews and equipment for train trips use both graph theory and linear algebra.
Apportionment: In the U.S., the legislative branch of the government has a House of Representatives with 435 members. The process of deciding how many of these members should be allocated to each state is called apportionment, and there is a lot of discrete mathematics involved both in creating and implementing various apportionment methods.
Computer graphics (such as in video games) use linear algebra to transform (move, scale, change perspective) objects. That’s true for both applications like game development, and operating systems.
Bankruptcy proceedings can involve lots of different reasonable ways to resolve claims. Some involve discrete optimization.
Electronic health care records are kept as parts of databases, and there is a lot of discrete mathematics involved in the efficient and effective design of databases.
Compact discs store a lot of data, which is encoded using a modified Reed-Solomon code (a binary code, and thus discrete math) to automatically correct transmission errors.
Voting systems: There are different methods for voting, not just the common cast-a-ballot-for-exactly-one-candidate method. The study of possible voting methods and how well their outcomes reflect the intent of the voters use discrete mathematics.
Cell phone communications: Making efficient use of the broadcast spectrum for mobile phones uses linear algebra and information theory. Assigning frequencies so that there is no interference with nearby phones can use graph theory or can use discrete optimization.
Digital image processing uses discrete mathematics to merge images or apply filters. Methods of encoding data and reducing the error in data transmission such as are used in bar codes, UPCs, data matrices, and QR codes are discrete mathematics. Hidden Markov models, which are part of linear algebra, are used for large vocabulary continuous speech recognition.
Food Webs: A food web describes how a set of species eat (and don’t eat) each other. They can be studied using graph theory.
Delivery Route Problems: If you need to leave home, visit a sequence of locations each exactly once and then return homes such as might happen with a newspaper delivery route or scheduling bread to be delivered from a bakery to grocery stores this is known as the traveling salesperson problem, or TSP. There is a definitive source on the history of, and state-of-the-art work on TSP.
Discrete mathematics and its applications solutions
Research and corporate applications that use discrete mathematics
Spatio-temporal optimization is a type of algorithm design that has been applied to reducing poaching of endangered animals.
Graph theory, and in particularly rooted tree diagrams of a genome, is used in the evolution of SARS-CoV-2. Logistics deals with managing inventory and supply chains, as well as transporting goods and people to where and when they are needed.
Many of the problems involved use discrete optimization. Detecting deepfakes (fake videos) uses linear algebra and related discrete mathematics.
Discrete math is used in choosing the most on-time route for a given train trip in the UK. The software determines the probability of a given train trip being completed on time in the UK uses Markov chains. Linear algebra is discrete mathematics and is used for compressive sensing (efficient image/sound recording) and medical imaging.
Archaeology uses discrete math to construct 3D images from scans of archaeological sites. Determining voting districts, a process is known as redistricting, is rife with problems and influenced by politics.
Many researchers in various fields work on methods for fair redistricting, and some use lots of discrete math. Network flows, a part of discrete math, can be used to help protect endangered species from the threat of global warming (see the abstract for this paper).
Power grids: Graph theory is used in finding the most vulnerable aspects of an electric grid. Graph theory and linear algebra are used in power grid simulations.
Graph theory is involved in routing concrete trucks. Voting theory (see earlier on this page) can be used to decide how to prioritize biodiversity conservation sites (see the abstract for this paper).
Graph theory is used in kidney donor matching (bonus: the speaker on the podcast has given Daily Gathers at MathILy). Determining how best to add streets to congested areas of citiesuses graph theory (and in fact an area of graph theory taught in one of the MathILy branch classes!).
Matching medical-school graduates to hospital residencies are solved using a provably optimal algorithm. Here are twoarticles that describe the discrete mathematics involved and what happens when this is extended to the problem of matching middle-school students to high schools.
Measuring the evolutionary distance between genomes can be done using permutations, as described here. Graph theory is involved in searching for terrorist groups sending covert messages on public fora.
Data compression, reduction of noise in data, and automated recommendations of movies all use the same tool from linear algebra. The spread of infectious disease is affected by personal contacts and by behaviors influenced by information.
One model of epidemics uses graph theory by encoding personal contacts and behaviors as layers in a large network.
We can model a crystal structure based on a set of electron microscope images using discrete tomography. Linear programming can be used in discrete tomography. Discrete tomography can also be used in medical imaging, to reconstruct an image of an organ from just a few x-ray images.
Graph theory and linear algebra can be used in speeding up Facebook performance. Assessing risk in heart-attack patients, categorizing species using few characteristics, and data mining analytics all use the same discrete math.
Chemistry: Balancing chemical equations uses linear algebra and understanding molecular structure uses graph theory. We can straighten an image taken by a misaligned camera using linear algebra. Many ways of producing rankings use both linear algebra and graph theory.
Specific examples include ranking relevance of search results using Google, ranking teams for tournaments or chicken pecking orders, and ranking sports team performances or restaurant preferences that include apparent paradoxen.
Modeling traffic: Determining the effect of regulation on network traffic flow whether that’s cars on roads or packets across the internet is a matter of game theory and graph theory together. Optimizing traffic-light cycles uses both discrete and continuous mathematics.
The design of radar and sonar systems uses graph theory via Golomb rulers. Graph theory is used in neuroscience to study brain network organization (see abstract here) and understand neuropathology for nervous system disorders. Understanding the spread of information through a social network which includes trying to make items go viral uses graph theory.
Linear algebra and graph theory are used in clustering analysis on geosocial data to locate gangs and insurgencies. Researchers have used phylogenetic trees, which are part of graph theory, to test hypotheses for why birds lay eggs of different shapes (also see the research article).