Introduction to Discrete Mathematics
What is Discrete Mathematics? We need to know that first. Second, we need to know what is the relationship of Discrete Mathematics to Computer Science. Finally, we want to know how we can implement the Discrete Mathematical concepts into various fields of Computer Science.
Here, we are primarily concerned with Algorithm and Data Structure. These topics sit at the core of any Computer Science curriculum. Without understanding these two components properly, we can not claim that we are students of Computer Science!
Therefore, I have chosen these two topics and try to implement Discrete Mathematical concepts into them so that our understanding might take a proper shape. In this chapter, our first and foremost concern is to know what is Discrete Mathematics.
What is Discrete Mathematics
Discrete Mathematics is a branch of Mathematics and, to be very particular, it is the study of Mathematical structures, and objects that are discrete.
In that sense, ‘people’, ‘animal’, ‘chair’ and everything we see around us, fall under this mathematical study. Why? Because, they are discrete, distinct. They are not continuous. Think about real numbers that consist of rational and irrational numbers, or a number line, which is continuous; so that is not discrete mathematics. Rather, natural numbers (N), like 0, 1, 2, etc, which are discrete fall under this category.
Discrete Mathematical conceptions handle with distinct and separated values. The opposite of discrete mathematics is continuous mathematics, such as calculus or Euclidean Geometry. However, Euclidean Algorithm that helps us find the greatest common divisor of two positive natural numbers (GCD), is very much discrete mathematics. We will see to an example in a minute.
Have you found any contradiction in the above statement?
I have found one; and before proceeding further, I think, we should make it clear first. We have just said that real numbers, or a number line where between 1 and 2, there are infinite numbers, cannot be discrete. However, when we say, positive natural numbers like 1, 2, 3, which are distinct and separated, belong to discrete mathematics. 1, 2 or 51, every positive natural numbers are also real numbers. Right? They belong to the number line. Right? Then where we stand? We are contradicting ourselves.
Therefore, we can conclude that there is no exact definition of Discrete Mathematics. At best, we can say, that the opposite of continuous mathematics is discrete mathematics.
In Mathematics, there are many things that are not continuous. You may think of Set theory, x co-ordinate and y co-ordinate, that refer to different positions on the quadrants, without joining them. You may think of GCD and LCM. Greatest common divisor and least common multiple. They are always discrete.
Consider the statement in logic. True or False. They are discrete. Consider 0 and 1. The binary code, the core conceptions of Computer Science, they are very much discrete.
Consider objects in any object-oriented-programming language. Every new object is discrete.
That is why, Discrete Mathematical conceptions are closely related to every field of Computer Science. In this book, we will only consider Algorithm and Data Structure part.
In the following part we will compute the number of molecules in a hydrocarbon. First, we will compute this program using Java, after that, we will use C++ to compute the same program.
Notice the algorithm. That is same for two languages, although syntactically there are differences. So the steps of algorithm varies. Let us see the algorithm first.
The algorithm will be like this:
1 Step 1: take input and store the mass of hydrocarbon, the number of carbon, and the \
2 number of hydrogen atoms
3 Step 2: find and store the formula weight of one mole
4 Step 3: find the number of molecules in given mass of hydrocarbon using the above f\
5 ormula
6 Step 4: output the stored input values and the result
Considering that the algorithm is the same, suppose for both languages, its value is 1. However, the syntactical difference makes the second value change.
If we consider that algorithm is the X axis, and the syntactical difference as Y axis, then the hypothetical value might be (1, 2) and (1, 5). Moreover, they are discrete, distinct and separated.
If we want to connect them drawing a line, that no longer remains discrete. That becomes a continuous mathematical conceptions.
With the help of these two programs, what I would like to point out is a simple mathematical statement. The difference between discrete mathematics and continuous mathematics is paper-thin. It also proves our definition of discrete mathematics. Anything, that is not continuous mathematics, is discrete mathematics.
Let us see the Java program first.
1 //code 1.1
2 //Java
3 package fun.sanjibsinha.languagebasics;
4 /*
5 we will compute number of molecules in a hydrocarbon
6 a mole of any substance contains 6.02 * 10^23 molecules
7 this is called Avogadro's number
8 relationship of a mass of a substance and the number of molecules is:
9
10 molecules = mass * 1mole/FormulaWeight * (6.02 * 10^23 molecules)/i mole
11 */
12 import java.util.Scanner;
13
14 public class HydroCarbonMolecule {
15
16 static float massOfHydrocarbon = 0.00f;
17 static int numberOfCarbonAtoms = 0;
18 static int numberOfHydrogenAtoms = 0;
19
20 public static void main(String[] args) {
21
22 System.out.println("Enter mass of HydroCarbon in a floating point: ");
23 Scanner mh = new Scanner(System.in);
24 massOfHydrocarbon = mh.nextFloat();
25 System.out.println("Enter the number of carbon atoms: ");
26 Scanner nc = new Scanner(System.in);
27 numberOfCarbonAtoms = nc.nextInt();
28 System.out.println("Enter the number of hydrogen atoms: ");
29 Scanner nh = new Scanner(System.in);
30 numberOfHydrogenAtoms = nh.nextInt();
31 final int CarbonAMU = 12;
32 final int HydrogenAMU = 1;
33 long formulaWeightOfOneMole = 111111111111L;
34 formulaWeightOfOneMole = (numberOfCarbonAtoms * CarbonAMU)
35 + (numberOfHydrogenAtoms * HydrogenAMU);
36 double AvogadroNumber = 6.02 * Math.pow(10, 23);
37 double molecules = (massOfHydrocarbon/formulaWeightOfOneMole) * Avogadro\
38 Number;
39 System.out.println(massOfHydrocarbon + " grams of hydrocarbon with " + n\
40 umberOfCarbonAtoms
41 + " carbon atoms and " + numberOfHydrogenAtoms + " hydrogen atoms contai\
42 n "
43 + molecules + " molecules.");
44
45 }
46 }
Here goes the output:
1 //output of code 1.1
2 Enter mass of HydroCarbon in a floating point:
3 16.00
4 Enter the number of carbon atoms:
5 1
6 Enter the number of hydrogen atoms:
7 4
8 16.0 grams of hydrocarbon with
9 1 carbon atoms and 4 hydrogen atoms contain 6.019999999999999E23 molecules.
I would like to write the Avogadro’s number using the scientific notation this way:
1 double AvogadroNumber = 6.02e23;
The output changes from 6.019999999999999E23 to 6.02E23, although it should not have mattered how you have written the Avogadro’s number. In the first case,
I have used the Java pow() method. In the second case,I have used the scientific notation. However, the outputs are discrete.
I would like to show you the same program in C++, where I have used the ‘cmath’ library’s pow() function, the same way I have used pow() method in my Java code.
Let us see the program first.
1 //code 1.2
2 //C++
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6
7 using namespace std;
8
9 int main() {
10 /* code */
11 std::cout << "Enter mass of hydrocarbon in decimal point value, like 2.33" << '\n';
12 float massOfHydrocarbon;
13 std::cin >> massOfHydrocarbon;
14 std::cout << "Enter number of carbon atoms in positive integer, like 2" << '\n';
15 int numberOfCarbonAtoms;
16 std::cin >> numberOfCarbonAtoms;
17 std::cout << "Enter the number of hydrogen atoms in positive integer, like 3" << '\n\
18 ';
19 int numberOfHydrogenAtoms;
20 std::cin >> numberOfHydrogenAtoms;
21 const int carbonAMU = 12;
22 const int hydrogenAMU = 1;
23 long formulaWeightOfOneMole = (numberOfCarbonAtoms * carbonAMU) + (numberOfHydrogenA\
24 toms * hydrogenAMU);
25 const double AvogadroNumber = 6.02 * pow(10, 23);
26 double moleculesInHydrocarbon = (massOfHydrocarbon / formulaWeightOfOneMole) * Avoga\
27 droNumber;
28 std::cout << massOfHydrocarbon << " grams of hydrocarbon with " << numberOfCarbonAto\
29 ms <<
30 " \ncarbon atoms and " << numberOfHydrogenAtoms << " hydrogen atoms contain " << mol\
31 eculesInHydrocarbon;
32 return 0;
33 }
The output is: 6.02e+23. Now, if we change the Avogadro’s number to this:
1 const double AvogadroNumber = 6.02e23;
The output remains the same. In Java, although the value changes.
Now, we can conclude that every programming language is discrete, not only syntactically, but also in their output.
What is the relationship between Discrete Mathematics and Computer Science
We can now understand how discrete mathematics and computer science are related. Through our programming logic and algorithm, we can reproduce continuous mathematics in any programming language, like Java.
Let us see another example in Java.
First the code, then we will discuss the concept.
1 //code 1.3
2 //Java
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 /*
8 Finding the y-coordinate of a point on a line
9 where x-coordinate is given
10 */
11 public class FindingYCoordinate {
12
13 static int lineSlope = 0;
14 static int yIntercept = 0;
15 static int xCoordinate = 0;
16 static int yCoordinate = 0;
17
18 public static void main(String[] args) {
19
20 System.out.println("Enter the value of the line-slope in positive integer: "\
21 );
22 Scanner slopeOfLine = new Scanner(System.in);
23 lineSlope = slopeOfLine.nextInt();
24 System.out.println("Enter the intercept of y-axis: ");
25 Scanner interceptOfY = new Scanner(System.in);
26 yIntercept = interceptOfY.nextInt();
27 System.out.println("Enter the value of x-coordinate: ");
28 Scanner coordinateOfX = new Scanner(System.in);
29 xCoordinate = coordinateOfX.nextInt();
30 yCoordinate = lineSlope * xCoordinate + yIntercept;
31 //line of slope = rise vertically/run horizontally
32 //yCoordinate = (lineSlope * xCoordinate) + yIntercept;
33 System.out.println("The y-coordinate is: " + yCoordinate + ". When the slope\
34 of line is: "
35 + lineSlope + ". Intercept of y-axis is: " + yIntercept + ". X coord\
36 inate is: " + xCoordinate);
37
38 }
39
40 }
In the above code, with the help of line-slope and y-intercept, we find the y-coordinate. The value of x-coordinate is given.
A line-slope is the ratio of vertical rise and horizontal run of the line. The y-intercept is a given point on the y axis. If we run the program and provide the values, the output comes out as:
1 //output of code 1.3
2 Enter the value of the line-slope in positive integer:
3 6
4 Enter the intercept of y-axis:
5 2
6 Enter the value of x-coordinate:
7 2
8 The y-coordinate is: 14. When the slope of line is: 6. Intercept of y-axis is: 2. X \
9 coordinate is: 2
In the above output it is evident that every number is discrete and computing them is easier with the help of a formula. Here the value of y-coordinate is 14, when x-coordinate is 2.
What makes discrete mathematics different from the continuous mathematical proceedings is its capacity of getting counted, discrete structures are always either countable, or distinct. In the above code, we have seen that each vertical rise and horizontal run are discrete, distinct from others. Each time you run the code, providing distinct values will give you values that are separable from the previous ones.
Introducing necessary conceptions
In the following chapters, we will see plenty of examples where discrete mathematical computations will be used.
To name a few, we will discuss set theory and its implementations in data structures. We will see how permutation and combination work together in algorithm. The role of logical statement or truth table will play a great role in our discussion.
We will see how finite collections of discrete objects are implemented in the data structures. They can not only be counted, but also arranged and placed into sets. Studying Euclidean algorithm, along with finding the GCD and LCM, will be a major part in our discussion.
There are many interesting topics to come. So stay tuned and keep reading on.