1. Introduction to the Discourse
As you know from the title, this book covers a wide range of three topics, in fact, too wide range of three topics, on which you will find books separately. You will find many good books on Discrete Mathematics, you will find many good books on Algorithm and Data Structures, as well.
Keeping that fact in mind, we are writing a book which tries to discover the relations between three well known topics, and, moreover, how they influence each other.
We can compare this relationship, such as, a relation between the writer and readers. Readers always reconstruct a book while reading, and they write it in a new way in their mind. Each time a book is read, it is actually written again.
We can consider this book as a confluence of the three distinct topics, such as Discrete Mathematics, Algorithm and Data Structures.
Let us start with Discrete Mathematics first.
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, such as Algorithm and Data Structures.
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!
Data Structures are most fundamental and building blocks of computer science. Understanding Data Structures is an essential thing to design and build efficient software. At the same way, we can say, that knowing Algorithm is also compulsory to understand these fundamental blocks 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. However, before starting the book, there is an important question.
Is Discrete Mathematics enough to study Computer Science?
Our answer is – NO.
There are some other topics that we must know – now, simultaneously, or later, to get a proper understanding of Computer Science. If we love our subject, then we will try to understand how Calculus, Linear Algebra and as a whole, Mathematics is related to Computer Science.
We are not pushing ourselves to become a mathematician. That we are not going to suggest.
We want to study computer science.
Nevertheless, we also want to know all the necessary concepts that are related to computer science.
Before moving on to our real discourse, let us know what the word – Mathematics – means to us. Mathematics includes the topics, such as quantity (number theory), structure (algebra), space (geometry), and change (mathematical analysis).
As we see, as a programmer, we also deal with such topics. We deal with numbers, all types of numbers, so an introduction to number theory should be included in our study. We need to study structures (remember data structures); therefore, a knowledge of algebra is important where calculus and linear algebraic equations might play a vital role.
Therefore we need to know how to find area and volume of two moving objects, how to find the slope of a line, or need to know about linear algebraic concepts like matrices and vectors.
On the other hand, Computer Programming involves tasks like data analysis, generating algorithms, making algorithms more accurate with less resource consumption, and finally we need to implement algorithms in a chosen programming language. These processes, as a whole, are known as coding. Knowledge of specialized algorithms and formal logic may be enough to be a good programmer.
However, if we want to change the word – good – to another word – great – then we must equip ourselves with some mathematical knowledge that are not directly related to Discrete Mathematics.
Although they are not directly related, they are indirectly related. The study of calculus starts with the relationship between velocity and distance; and, they are ordered pair of sets, which is very much a discrete mathematical conceptions.
Calculus is a mathematical study of continuous change; however, computer scientific study is severely discrete, it deals with distinct objects.
Besides, linear algebraic conceptions are fundamental in many areas where line, plane and spaces are involved. We need to know them as well. If not now, then we should know them later, of course.
We should always remember that different branches of mathematical conceptions are key components in computation. We should not forget that truth as long as we think ourselves as a student of computer science.
A short 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.
I write regularly on Algorithm and Data Structure in
QUIZZ and Challenge on Chapter One
Question 1: Which part of Mathematics we need to implement in Computer Science?
Option 1: The quantity (number theory) and structure (algebra) only.
Option 2: Only space (geometry)
Option 3: The change (mathematical analysis) and structure (algebra) only.
Option 4: All of the four.
Answer: Option 4.
=======================
Question 2: Which fields of algebra is important for Computer Science?
Option 1: Calculus
Option 2: Linear algebraic equations
Option 3: Both
Option 4: None of them
Answer: Option 4
=======================
Question 3: In which area of Mathematics line, plane and spaces are involved?
Option 1: Matrices and vectors
Option 2: Number theory
Option 3: Linear algebraic equations
Option 4: None of the above
Answer: Option 3
=======================
Question 4: Is a number line falls under the category of Discrete Mathematics?
Option 1: Yes
Option 2: No
Answer: Option 2
=======================
Question 5: Give example of Discrete Mathematics
Option 1: GCD and LCM, Greatest common divisor and least common multiple.
Option 2: Set theory
Option 3: None of the above
Option 4: Both
Answer: Option 4
=======================
Challenge 1 : Write down a program in any language where you can prove that discrete structures are always either countable, or distinct.
Solution to Challenge 1 : Language used Java
package fun.sanjibsinha;
1 import java.util.Scanner;
2
3 /*
4 Finding the y-coordinate of a point on a line
5 where x-coordinate is given
6 */
7 public class FindingYCoordinate {
8
9 static int lineSlope = 0;
10 static int yIntercept = 0;
11 static int xCoordinate = 0;
12 static int yCoordinate = 0;
13
14 public static void main(String[] args) {
15
16 System.out.println("Enter the value of the line-slope in positive integer: "\
17 );
18 Scanner slopeOfLine = new Scanner(System.in);
19 lineSlope = slopeOfLine.nextInt();
20 System.out.println("Enter the intercept of y-axis: ");
21 Scanner interceptOfY = new Scanner(System.in);
22 yIntercept = interceptOfY.nextInt();
23 System.out.println("Enter the value of x-coordinate: ");
24 Scanner coordinateOfX = new Scanner(System.in);
25 xCoordinate = coordinateOfX.nextInt();
26 yCoordinate = lineSlope * xCoordinate + yIntercept;
27 //line of slope = rise vertically/run horizontally
28 //yCoordinate = (lineSlope * xCoordinate) + yIntercept;
29 System.out.println("The y-coordinate is: " + yCoordinate + ". When the slope\
30 of line is: "
31 + lineSlope + ". Intercept of y-axis is: " + yIntercept + ". X coord\
32 inate is: " + xCoordinate);
33
34 }
35
36 }
//output of code Enter the value of the line-slope in positive integer: 6 Enter the intercept of y-axis: 2 Enter the value of x-coordinate: 2 The y-coordinate is: 14. When the slope of line is: 6. Intercept of y-axis is: 2. X coordinate is: 2
Challenge 2 : Can you prove using a programming language how the Set theory is widely used in Computer Science.
Solution to Challenge 2 : Language used SQL.
In order to demonstrate and explain the set operators in SQL effectively, we will be using the following tables.
These sample tables are “customers_of_jan” and “customers_of_dec”. These tables contain 5 records each with the customer’s id, name, city. Let’s have a look at the records in two tables. So that later, we can understand how set operations are helpful.
1 //first table
2
3 “customers_of_jan”
4
5 customer_id name city
6
7 1 John New York
8
9 2 Json California
10
11 3 Ankit Delhi
12
13 4 Mary Sanghai
14
15 5 Keka Kolkata
16
17 //second table
18
19 “customers_of_dec”
20
21 customer_id name city
22
23 1 Henrik Berlin
24
25 2 Json Munich
26
27 3 John London
28
29 4 Allen Sanghai
30
31 5 Mary Paris
If we use the following code, it will create problems.
1 //code
2
3 SELECT name FROM customers_of_dec
4 UNION
5 SELECT name FROM customers_of_jan;
Because, there are two John and two Mary combining both tables. As a rule of thumb, the above SQL atatement will choose only one John and one Mary.
However, implementing the concept of SET Theory in Computer Science, we can use UNION in the following way.
1 // code
2
3 SELECT name FROM customers_of_dec
4 UNION ALL
5 SELECT name FROM customers_of_jan;
Union ALL operator will take two John and two Mary into consideration and returned John twice. The same is the case for Mary.
Conclusion: The above challenge and solution proves that without the Set Theory, which belongs to the Discrete Mathematics, we could not build any kind of Relational Database.