Table of Contents
- 1. Introduction to the Discourse
- 2. Introduction to Programming Language and Boolean Algebra
- 3. De Morgan’s Laws on Boolean Algebra, Logical Expression, and Algorithm
- 4. Data Structures in different Programming languages
- printing result
- 5. Data Structures: Abstractions and Implementation
-
6. Data Structures in Detail
- Frequently Asked Questions about Data Structures
- Abstract Data Type (ADT)
- Linear Data Structures
- Modeling of a Structure
- ArrayList to overcome limitations of Array
- ArrayList or LinkedList, which is faster?
- Collection Framework in programming languages
- Stack and Queue in Java
- Deque, a high-performance Abstract Data Type
- QUIZZ and Challenge on Chapter Six
- Challenge 1 : Can we test in a program whether the Stack has been overflowed or not?
- Challenge 2 : Can you convert an array to a queue and use all the queue methods to manipulate that array?
- Challenge 3 : Why LinkedList consumes less memory than ArrayList. Write a program and explain why it happens.
- Challenge 4 : Can you give examples of hybrid linear data structure that provides all the capabilities of stacks and queues under one roof?
-
7. Algorithm, Data Structure, Collection Framework and Standard Template Library (STL)
- Introducing Algorithm Library
- Different types of Algorithms
- Binary Tree and Data Structure
- Collection Framework in Java
- Discrete Mathematical Abstractions and Implementation through Java Collection
- Comparator, Comparable and Iterator
- Standard Template Library in C++
- QUIZZ on Chapter Seven
- Challenge 1 : Standard Template Library (STL) provides many generic versions of standard algorithms that replace our low-level plumbing. Can you show the difference by writing code.
- Challenge 2 : Can you prove with an example how the STL makes a difference when we want to sort a list of data.
- Challenge 3 : Using recursion in programing is closer to our discrete mathematical definitions. Can you prove it?
- Challenge 4 : Recursive algorithm should have a base case. Write a program where we can proceed towards the base case and a condition to stop the recursion.
- Challenge 5 : Can you prove that Discrete Mathematics, data structure and algorithm are inter-connected?
- Challenge 6 : Can you create a general template class and method that will allow to pass any data of your choice.
-
8. Time Complexity
- Order of n, or O(n)
- Big O Notation
- QUIZZ on Chapter Eight
- Challenge 1 : Data structures are discrete structures and hence, the algorithms are all about discrete structures. Write a program to establish a relationship between algorithms and discrete mathematics
- Challenge 2 : How we can get the total of a series of positive integers that starts from 0 and ends at 5. Can it be done recursive way?
- Challenge 3 : Detect the main problem in the code below and rewrite it in proper way.
-
9. Set, Symmetric Difference and Propositional Logic
- Why Set is important in Data Structures
- How Symmetric Difference and Propositional Logic combine
- QUIZZ on Chapter Nine
- Challenge 1 : Why the Set implementation ‘HashSet’ is better than the general-purpose Set implementation ‘TreeSet’? Can you compare and prove that?
- Challenge 2 : Can you combine Symmetric Difference and Propositional Logic in one program? You can write it in any programming language.
- Challenge 3 : In discrete mathematical paradigms, Set abstraction is basically chaotic, and unordered. However, no duplicate element is allowed in the world of Set. Can you prove it?
-
10. Combinatorics and Counting, Permutation and Combinations
- Permutation and Combination
- QUIZZ on Chapter ten
- Challenge 1 : How many ways we can rearrange 5 balls.
- Challenge 2 : Suppose you have a string “abcd”. You are aked to rearrange the String. How many ways could you rearrange the String when repetition is allowed? Here repetition means, you can rearrange this way: bacd, cdba, dbac, etc.
- Challenge 3 : Can you show the difference between two types of permutation,where repetition is not allowed and allowed.
- What Next
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.
2. Introduction to Programming Language and Boolean Algebra
Programming language is a formal language that contains set of instructions, which produce various kind of output. It can either be imperative or declarative.
Imperative means it has sequence of operations to perform. On the other hand, declarative stands for the specification of desired results, it does not comprise of how to achieve it.
There are thousands of programming languages, many are being created everyday, probably! However, most of them are imperative. They comprise of certain commands or instructions for computers to perform certain tasks, producing various outputs. Let us try to understand this part very clearly.
In natural language, such as in English, we have encountered imperative mood where a verb is used to form a command or request. Consider this example: “do it”, or “Leave” and many more. Mostly it is directed towards a second person, but in some certain contexts, it can involve first ot third persons, such as, “Let’s do it”.
The same way, an imperative programming also comprises of certain commands, set of instructions that focus on how a program should operate. Consider a simple procedural imperative programming example in C programming language.
1 //code 2.1
2 //C
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 void doSomething(void){
7 printf("Do something.");
8 }
9
10 int main(int argc, char** argv) {
11
12 doSomething();
13
14 return (EXIT_SUCCESS);
15 }
In the above code, we have seen the function (method) declaration that gives us a standard output when the function is invoked. In the main() function area, the compiled code will run the code as we invoke the function doSomething(). It gives us the following output.
Quite simple and straightforward.
1 //output of code 2.1
2 Do something.
3 RUN FINISHED; exit value 0; real time: 0ms; user: 0ms; system: 0ms
The above code snippet gives us an idea of how procedural programming works. It is a part of imperative programming paradigm. It is called procedural, because, the program is built on one or more procedures or functions. It is sometimes also called subroutines.
Now question is, where does discrete mathematical conceptions stand here? What is the relationship between a procedural programming and discrete mathematics?
The simple answer is, a program should build either successfully or failed miserably. It cannot go on continuously. So a program must be either true or false, 1 or 0, to be more precise.
It should be discrete. We need to compile the code successfully, that is discrete. We give the instructions, that should be discrete. And, finally, we need the output, that should also be discrete. Now, imperative programming does not end with only procedural programming. There is object-oriented-programming paradigms. A C++ program could be a good example.
Let us see the code first.
1 //code 2.2
2 //C++
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13
14 using namespace std;
15
16 class DoSomething {
17
18 public:
19 string giveInstruction = "Do something";
20
21 void givingInstruction(){
22 cout << giveInstruction << "\n";
23 }
24
25 };
26
27 int main(int argc, char** argv) {
28
29 DoSomething firstObject;
30
31 firstObject.givingInstruction ();
32
33 return 0;
34 }
The above guy does the same thing, giving us the same type of output, only in a different manner. This C++ guy does the same thing discretely. In a distinct way. We cannot let it run continuously.
I hope, now it is clear to you why we need to understand discrete mathematical conceptions; it is needed to understand our code in a better way. Discrete mathematics is a part of mathematical conceptions that are not continuous. We cannot let our code run continuously. So we need to understand discrete mathematical conceptions.
I am not going to elaborate this section anymore. There are several other types of imperative programming. There are several other types of declarative programming languages. This is not the place to discuss them.
It is only imperative to know that our code cannot run continuously. Either it should build successfully or fail miserably; whatever the outcome, it should be discrete.
Logic, Mathematics, and Programming Language
Does logic come before mathematics? As long as humans are concerned, the answer is “Yes”. A child without knowing any mathematical conceptions, knows that what is hot and what is cold. She develops her logical experience by observation and actions. Is it hot or cold? The answer is yes or no. Accordingly, her actions take place.
Latter in life, she applies her sense of logic in understanding mathematical conceptions. Logic comes before mathematics and after that comes algorithm or steps; finally we write code based on that algorithm.
In programming language, logic plays the greatest role; because it leads to the acceptance of one proposition, the conclusion, on the basis of other propositions or premises. Moreover, the conclusion is discrete. That is why, in programming language, the truth table plays an important role. In programming language, if, if-else, or else conditionals lead us to one inference.
In ordinary life we also apply the same logic by observation.
Let us see a very simple program in Java, to see how this logical inference matters.
1 //code 2.3
2 //Java
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 public class IfAndElse {
8
9 static int age = 0;
10
11 public static void main(String[] args) {
12 System.out.println("Enter your age: ");
13 Scanner yourAge = new Scanner(System.in);
14 age = yourAge.nextInt();
15
16 if (age >= 1 && age <= 18){
17 System.out.println("Happy birthday!");
18 } else if(age == 21 || age == 50){
19 System.out.println("Important birthday!");
20 } else if(age >= 60){
21 System.out.println("Don't retire. Keep working!");
22 } else {
23 System.out.println("Keep living and help others!");
24 }
25 }
26 }
We have entered three different number and got the following output:
1 //output of code 2.3
2 //output 1
3
4 Enter your age:
5 45
6 Keep living and help others!
7
8 //output 2
9 Enter your age:
10 18
11 Happy birthday!
12
13 //output 3
14 Enter your age:
15 61
16 Don't retire. Keep working!
The above Java code, is based on a few principles that we can call ‘truth table’, based on which we build our algorithm. These logical steps are universal. It is not only true for the Java guy, but also applicable to every single programming paradigm. What is that?
There are three logical operators; they are ‘&&’ symbol that stands for ‘and’; ‘||’ symbol that stands for ‘or’; finally, we have a ‘!’ symbol that just converts true into false and vice versa.
In case of ‘&&’ symbol, if both statements are true, it comes out as TRUE. For the ‘||’ symbol, if any one of the statement is true, it comes out as TRUE. And you have already known about the nature of ‘!’ symbol.
These logical operations are dependent on conditional operators; they also have different symbols, such as ‘==’, ‘!=’, ‘<’, ‘>’, ‘>=’, and ‘<=’; when two conditions are ‘==’, (equal), we perform some operations and so on.
We can conclude that, logic, mathematics, algorithm and code are inter-dependent; and, they should be discrete, as well.
Introduction to Boolean Algebra
George Boole, the founder of Boolean algebra, is considered to be one of the founder of Computer Science also. In 1847, when he wrote his famous book “The Mathematical Analysis of Logic”, he had not thought about PC, mobile or tabs. I don’t want to say that. But in his second book, “An Investigation of the Laws of Thought” that he wrote in 1854, he clearly set the path for future computations. His great idea started a new branch of algebra, Boolean algebra, where the values of the variables are the truth values: true or false. They are usually denoted by 1 and 0 respectively. In elementary algebra the values of variables are numbers. There are several operations we can do on that like addition or multiplication.
In Boolean algebra, there are only three operations we can do: conjunction (and), disjunction (or) and negation (not). Now we are able to the logical operations as we use to do the numerical operations in elementary algebra.
Moreover, it helps programmers to create a formal description of logical operations with the help of conditionals like “if, else if and else”, and in some cases using “switch-cases”.
Now it adds great impetus to every modern programming language.
Not only that, with the help of this ‘truth table’, we can build a very complex decision trees. Let us start with a simple example.
Let us see the code first.
1 //code 2.4
2 //Java
3 package fun.sanjibsinha;
4
5 public class IfAndElseSimple {
6 static boolean isTrue = true;
7 static boolean isFalse;
8 public static void main(String[] args) {
9
10 if(isTrue){
11 System.out.println("It's true.");
12 isTrue = false;
13 if(isTrue && isTrue){
14 System.out.println("It's again true.");
15 } else if(isTrue || isFalse){
16 System.out.println("It's very much true.");
17 } else {
18 System.out.println("True is false, so it's false now.");
19 }
20 } else {
21 System.out.println("It's false.");
22 }
23
24 }
25 }
Watch the output:
1 //output of code 2.4
2 It's true.
3 True is false, so it's false now.
Globally we have made the boolean variable ‘isTrue’ true. Therefore, the first ‘if’ block allows us to enter into the block. Next, we have made the ‘isTrue’ false.
Now according to the boolean algebra and truth table, ‘false and false’ is ‘false’; and, ‘false or false’ is also ‘false.’ For that reason, we get the above output.
Now, we would like to change this code a little bit.
1 //code 2.5
2 //Java
3 package fun.sanjibsinha;
4
5 public class IfAndElseSimple {
6 static boolean isTrue = true;
7 static boolean isFalse;
8
9 public static void main(String[] args) {
10
11 if(isTrue){
12 System.out.println("It's true.");
13 if(isTrue && isTrue){
14 System.out.println("It's again true.");
15 } else if(isTrue || isFalse){
16 System.out.println("It's very much true.");
17 } else {
18 System.out.println("True is false, so it's false now.");
19 }
20 } else {
21 System.out.println("It's false.");
22 }
23
24 }
25 }
Watch the output now:
1 //output of code 2.5
2 It's true.
3 It's again true.
Now, in the second conditional, ‘true and true’ is ‘true’. So, we get the above output.
Let us see more examples and watch the output one after another to comprehend how this truth table works.
1 //code 2.6
2 //Java
3 package fun.sanjibsinha;
4
5 public class IfAndElseSimple {
6 static boolean isTrue = true;
7 static boolean isFalse;
8
9 public static void main(String[] args) {
10
11 if(isTrue){
12 System.out.println("It's true.");
13 if(((isTrue && isTrue) || isFalse) && isFalse){
14 System.out.println("It's not true any more true.");
15 } else if(((isTrue && isTrue) || isFalse) || isFalse){
16 System.out.println("It's very much true because we check between tru\
17 e or false.");
18 } else {
19 System.out.println("True is false, so it's false now.");
20 }
21 } else {
22 System.out.println("It's false.");
23 }
24
25 }
26 }
It’s quite obvious that very first conditional is true, so we enter the block. However, the next conditional comes out as false, because in the truth table ‘true and false’ will come out as false. Therefore, the code will check the next conditional, which is true.
So the output will be as the following:
1 //output of code 2.6
2 It's true.
3 It's very much true because because we check between true or false.
As the above code snippets, we can apply the same truth table on other data types using the logical operators. Here is an example:
1 //code 2.7
2 //Java
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 public class IfAndElse {
8
9 static int age = 0;
10
11 public static void main(String[] args) {
12 System.out.println("Enter your age: ");
13 Scanner yourAge = new Scanner(System.in);
14 age = yourAge.nextInt();
15
16 if (age >= 1 && age <= 18){
17 System.out.println("Happy birthday!");
18 } else if(age == 21 || age == 50){
19 System.out.println("Important birthday!");
20 } else if(age >= 60){
21 System.out.println("Don't retire. Keep working!");
22 } else {
23 System.out.println("Keep living and help others!");
24 }
25 }
26 }
Let us give different types of ‘age’ to check how our code works.
1 //output of code 2.7
2 //output 1
3
4 Enter your age:
5 45
6 Keep living and help others!
7
8 //output 2
9 Enter your age:
10 18
11 Happy birthday!
12
13 //output 3
14 Enter your age:
15 61
16 Don't retire. Keep working!
Let us make this example a little bit complex, so we can have an idea about how complicated this combinations might become.
1 //code 2.8
2 //Java
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 public class MoreIfAndElse {
8
9 static boolean isCold = false;
10 static boolean isRaining = false;
11 static boolean isTakingCar = false;
12
13 public static void main(String[] args) {
14
15 System.out.println("When asked, enter only true or false.");
16 System.out.println("Is it cold outside?");
17 Scanner cold = new Scanner(System.in);
18 isCold = cold.nextBoolean();
19 System.out.println("Is it raining?");
20 Scanner raining = new Scanner(System.in);
21 isRaining = raining.nextBoolean();
22 System.out.println("Are you taking car?");
23 Scanner takingCar = new Scanner(System.in);
24 isTakingCar = takingCar.nextBoolean();
25
26 if((isCold == true && isRaining == true) || isTakingCar == false){
27 System.out.println("I wear Windcheater jacket with hood.");
28 } else if((isCold == true && isRaining == false) || isTakingCar == true){
29 System.out.println("I wear Windcheater jacket without hood.");
30 } else {
31 System.out.println("I won't wear Windcheater of any kind!");
32 }
33
34 }
35 }
Let us give some different types of input as ‘true’ or ‘false’ and see how our code responds.
1 //output of code 2.8
2
3 //output 1
4
5 When asked, enter only true or false.
6 Is it cold outside?
7 true
8 Is it raining?
9 true
10 Are you taking car?
11 false
12 I wear Windcheater jacket with hood.
13
14 //output 2
15
16 When asked, enter only true or false.
17 Is it cold outside?
18 true
19 Is it raining?
20 true
21 Are you taking car?
22 true
23 I wear Windcheater jacket with hood.
24
25 //output 3
26
27 When asked, enter only true or false.
28 Is it cold outside?
29 true
30 Is it raining?
31 false
32 Are you taking car?
33 true
34 I wear Windcheater jacket without hood.
Like to make the combinations more complex? Well, we can try the following code snippets.
1 //code 2.9
2 //Java
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 public class AnotherIfAndElse {
8
9 static int age = 0;
10 static boolean isAllowed = false;
11
12 public static void main(String[] args) {
13
14 System.out.println("When asked, enter only true or false.");
15 System.out.println("Enter your age");
16 Scanner yourAge = new Scanner(System.in);
17 age = yourAge.nextInt();
18 System.out.println("Is allowed? Answer either true or false!");
19 Scanner allowed = new Scanner(System.in);
20 isAllowed = allowed.nextBoolean();
21
22 if(age <= 10 || age >= 70){
23 if(isAllowed == true){
24 System.out.println("You can go free!");
25 } else {
26 System.out.println("You can go free!");
27 }
28 } else {
29 System.out.println("Your entrance fee is 10 Euro.");
30 }
31 }
32 }
As usual, we will give different types of age to test how this combination works by maintaining the truth table rules.
1 //output of code 2.9
2 // output 1
3
4 When asked, enter only true or false.
5 Enter your age
6 80
7 Is allowed? Answer either true or false!
8 true
9 You can go free!
10
11 // output 2
12
13 When asked, enter only true or false.
14 Enter your age
15 56
16 Is allowed? Answer either true or false!
17 true
18 Your entrance fee is 10 Euro.
19
20 // output 3
21
22 When asked, enter only true or false.
23 Enter your age
24 2
25 Is allowed? Answer either true or false!
26 false
27 You can go free!
28
29 // output 4
30
31 When asked, enter only true or false.
32 Enter your age
33 85
34 Is allowed? Answer either true or false!
35 false
36 You can go free!
The above code establishes one thing, by implementing the proper usage of the truth table, we can stop the middle conditional to override the basic rule that has been defined earlier. The above code snippets check the entry to some places. In between there is a boolean value called ‘isAllowed’; you may think this guy as the gatekeeper who can override the entry with a special power. In fact that happens in the real life.
However, through the proper usage of the truth table we have limited his power to override the main conditional that says, for the age range of less than equal to 10 and greater than equal to 70, the entrance fee is zero.
Now if the gatekeeper wants to take price from that age range, he cannot do that.
As we progress, we will see more examples of boolean algebra in the future course of our book. So stay tuned and keep reading.
I write regularly on Algorithm and Data Structure in
QUIZZ and Challenge on on Chapter Two
Question One: In Boolean algebra, how many operations we can do?
Option 1: One
Option 2: Two
Option 3: Three
Answer: Option Three. (In Boolean algebra, there are only three operations we can do: conjunction (and), disjunction (or) and negation (not).)
Question Two: Will ‘true and false’ come out as false in the truth table?
Option 1: Yes.
Option 2: No.
Answer: Option 1.
Question 3: What is the imperative programming language?
Option 1: The programming langauge that deals with Discrete Mathematics.
Option 2: The programming language that comprises of certain commands or instructions for computers to perform certain tasks, producing various outputs.
Option 3: None of the above is true.
Option 4: Both statements are true
Answer: Option 4
=======================
Question 4: What is the relationship between a procedural programming and discrete mathematics?
Option 1: The common relationship is that they both deal with Boolean Algebra.
Option 2: A program should build either successfully or failed miserably.
Option 3: Both cannot go on continuously.
Option 4: All of the above.
Answer: Option 4
=======================
Question 5: A child develops her logical experience by observation and actions. Is that true for Mathematics?
Option 1: Yes
Option 2: No
Answer: Option 1
=======================
Challenge 1: Can you write a program based on the <<Truth Table>>
Solution to Challenge 1: Language used Java
1 //code
2
3 package fun.sanjibsinha;
4
5 import java.util.Scanner;
6
7 public class IfAndElse {
8
9 static int age = 0;
10
11 public static void main(String[] args) {
12 System.out.println("Enter your age: ");
13 Scanner yourAge = new Scanner(System.in);
14 age = yourAge.nextInt();
15
16 if (age >= 1 && age <= 18){
17 System.out.println("Happy birthday!");
18 } else if(age == 21 || age == 50){
19 System.out.println("Important birthday!");
20 } else if(age >= 60){
21 System.out.println("Don't retire. Keep working!");
22 } else {
23 System.out.println("Keep living and help others!");
24 }
25 }
26 }
27
28 //output 1
29
30 Enter your age:
31 45
32 Keep living and help others!
33
34 //output 2
35 Enter your age:
36 18
37 Happy birthday!
38
39 //output 3
40 Enter your age:
41 61
42 Don't retire. Keep working!
Challenge 2: Write an algorithm in natural language that builds a very complex decision trees.
Solution to Challenge 2: Language used Java
1 //code
2
3 package fun.sanjibsinha;
4
5 public class IfAndElseSimple {
6 static boolean isTrue = true;
7 static boolean isFalse;
8 public static void main(String[] args) {
9
10 if(isTrue){
11 System.out.println("It's true.");
12 isTrue = false;
13 if(isTrue && isTrue){
14 System.out.println("It's again true.");
15 } else if(isTrue || isFalse){
16 System.out.println("It's very much true.");
17 } else {
18 System.out.println("True is false, so it's false now.");
19 }
20 } else {
21 System.out.println("It's false.");
22 }
23
24 }
25 }
26
27
28 //output
29
30 It's true.
31 True is false, so it's false now.
Challenge 3: In Boolean algebra, there are only three operations we can do: conjunction (and), disjunction (or) and negation (not). Can you prove this paradigm in a complex “Truth Table” that uses conditional logic.
Solution to Challenge 2: Language used Java
1 //code
2
3
4 package fun.sanjibsinha;
5
6 import java.util.Scanner;
7
8 public class MoreIfAndElse {
9
10 static boolean isCold = false;
11 static boolean isRaining = false;
12 static boolean isTakingCar = false;
13
14 public static void main(String[] args) {
15
16 System.out.println("When asked, enter only true or false.");
17 System.out.println("Is it cold outside?");
18 Scanner cold = new Scanner(System.in);
19 isCold = cold.nextBoolean();
20 System.out.println("Is it raining?");
21 Scanner raining = new Scanner(System.in);
22 isRaining = raining.nextBoolean();
23 System.out.println("Are you taking car?");
24 Scanner takingCar = new Scanner(System.in);
25 isTakingCar = takingCar.nextBoolean();
26
27 if((isCold == true && isRaining == true) || isTakingCar == false){
28 System.out.println("I wear Windcheater jacket with hood.");
29 } else if((isCold == true && isRaining == false) || isTakingCar == true){
30 System.out.println("I wear Windcheater jacket without hood.");
31 } else {
32 System.out.println("I won't wear Windcheater of any kind!");
33 }
34
35 }
36 }
37
38
39 //We have three outputs that prove the above paradigm
40
41 //output 1
42
43 When asked, enter only true or false.
44 Is it cold outside?
45 true
46 Is it raining?
47 true
48 Are you taking car?
49 false
50 I wear Windcheater jacket with hood.
51
52 //output 2
53
54 When asked, enter only true or false.
55 Is it cold outside?
56 true
57 Is it raining?
58 true
59 Are you taking car?
60 true
61 I wear Windcheater jacket with hood.
62
63 //output 3
64
65 When asked, enter only true or false.
66 Is it cold outside?
67 true
68 Is it raining?
69 false
70 Are you taking car?
71 true
72 I wear Windcheater jacket without hood.
Challenge 3: Can you write a program in any langauge that will charge money if the user’s age is between 10 and 70.
Solution to Challenge 2: Language used Java
1 //code
2
3
4 package fun.sanjibsinha;
5
6 import java.util.Scanner;
7
8 public class AnotherIfAndElse {
9
10 static int age = 0;
11 static boolean isAllowed = false;
12
13 public static void main(String[] args) {
14
15 System.out.println("When asked, enter only true or false.");
16 System.out.println("Enter your age");
17 Scanner yourAge = new Scanner(System.in);
18 age = yourAge.nextInt();
19 System.out.println("Is allowed? Answer either true or false!");
20 Scanner allowed = new Scanner(System.in);
21 isAllowed = allowed.nextBoolean();
22
23 if(age <= 10 || age >= 70){
24 if(isAllowed == true){
25 System.out.println("You can go free!");
26 } else {
27 System.out.println("You can go free!");
28 }
29 } else {
30 System.out.println("Your entrance fee is 10 Euro.");
31 }
32 }
33 }
34
35
36 //We can test this program various way and make it impregnable.
37
38 // output 1
39
40 When asked, enter only true or false.
41 Enter your age
42 80
43 Is allowed? Answer either true or false!
44 true
45 You can go free!
46
47 // output 2
48
49 When asked, enter only true or false.
50 Enter your age
51 56
52 Is allowed? Answer either true or false!
53 true
54 Your entrance fee is 10 Euro.
55
56 // output 3
57
58 When asked, enter only true or false.
59 Enter your age
60 2
61 Is allowed? Answer either true or false!
62 false
63 You can go free!
64
65 // output 4
66
67 When asked, enter only true or false.
68 Enter your age
69 85
70 Is allowed? Answer either true or false!
71 false
72 You can go free!
3. De Morgan’s Laws on Boolean Algebra, Logical Expression, and Algorithm
In this chapter we will learn about basic algorithm, which has its roots in De Morgan’s laws on Boolean algebra, and logical expression. After learning about basic algorithmic steps and sequences, we will discuss data structures in the next chapter.
To build complex algorithm, we need to understand the core concepts about data structures (chapter 4); we will come back to more advanced concepts of algorithm again in chapter five.
Let us start this chapter with Boolean algebra.
Augustus De Morgan was a contemporary mathematician of George Boole. Although he did not create the laws using his name, yet it is credited to him, since he was the creator.
De Morgan’s laws are based on Boolean algebra, and in every programming language, it is widely applied and equally true.
What the rule states, we can write this way, where ‘a’ and ‘b’ are two boolean values (true or false):
1 1. not (a and b) is the same as (not a) or (not b)
2 2. not (a or b) is the same as (not a) and (not b)
Let us apply this laws in PHP. We have stored the first law in ‘DeMorganOne.php’ file. Let us see the code first:
1 // code 3.1
2 // DeMorganOne.php
3 <?php
4
5 /*
6 * not (a and b) is the same as (not a) or (not b)
7 */
8
9 class DeMorganOne {
10
11 public $numOne;
12 public $numTwo;
13
14 public function notAandB($paramOne, $paramTwo) {
15
16 $this->numOne = $paramOne;
17 $this->numTwo = $paramTwo;
18 $additionOfTwoNumbers = $paramOne + $paramTwo;
19
20 //not(paramOne and paramTwo)
21 if(!($paramOne >= 10 && $paramTwo <= 15)){
22 echo "Addition of two numbers : $additionOfTwoNumbers";
23 } else {
24 echo "The number is neither less than equal to 10 nor greater than equal\
25 to 15";
26 }
27 }
28
29 public function notAORnotB($paramOne, $paramTwo) {
30
31 $this->numOne = $paramOne;
32 $this->numTwo = $paramTwo;
33 $additionOfTwoNumbers = $paramOne + $paramTwo;
34
35 //(not paramOne) or (not paramTwo)
36 if(!($paramOne >= 10) || !($paramTwo <= 15)){
37 echo "Addition of two numbers : $additionOfTwoNumbers";
38 } else {
39 echo "The number is neither less than equal to 10 nor greater than equal\
40 to 15";
41 }
42 }
43 }
44
45 $firstCase = new DeMorganOne();
46 $secondCase = new DeMorganOne();
47
48 $firstCase->notAandB(11, 14);
49 echo '<br>';
50 $firstCase->notAandB(1, 140);
51 echo '<br>';
52 $secondCase->notAORnotB(11, 14);
53 echo '<br>';
54 $secondCase->notAORnotB(1, 140);
We have tested the first law by passing the same value through two class variables and methods; we have obtained the same result.
1 // output of code 3.1
2 The number is neither less than equal to 10 nor greater than equal to 15
3 Addition of two numbers : 141
4 The number is neither less than equal to 10 nor greater than equal to 15
5 Addition of two numbers : 141
Now, you can play around by passing different types of value to see how this law works. Whatever the values you pass, they must be same for two member methods and you will get the same result.
To test the second law, we have created another PHP file ‘DeMorganTwo.php’, where we have done the same thing, except that the logical expressions have been changed.
1 // code 3.2
2
3 // DeMorganTwo.php
4
5 <?php
6
7 /*
8 * not (a or b) is the same as (not a) and (not b)
9 */
10
11 class DeMorganOne {
12
13 public $numOne;
14 public $numTwo;
15
16 public function notAandB($paramOne, $paramTwo) {
17
18 $this->numOne = $paramOne;
19 $this->numTwo = $paramTwo;
20 $additionOfTwoNumbers = $paramOne + $paramTwo;
21
22 //not(paramOne and paramTwo)
23 if(!($paramOne >= 10 || $paramTwo <= 15)){
24 echo "Addition of two numbers : $additionOfTwoNumbers";
25 } else {
26 echo "The number is neither less than equal to 10 nor greater than equal\
27 to 15";
28 }
29 }
30
31 public function notAORnotB($paramOne, $paramTwo) {
32
33 $this->numOne = $paramOne;
34 $this->numTwo = $paramTwo;
35 $additionOfTwoNumbers = $paramOne + $paramTwo;
36
37 //(not paramOne) or (not paramTwo)
38 if(!($paramOne >= 10) && !($paramTwo <= 15)){
39 echo "Addition of two numbers : $additionOfTwoNumbers";
40 } else {
41 echo "The number is neither less than equal to 10 nor greater than equal\
42 to 15";
43 }
44 }
45 }
46
47 $firstCase = new DeMorganOne();
48 $secondCase = new DeMorganOne();
49
50 $firstCase->notAandB(11, 14);
51 echo '<br>';
52 $firstCase->notAandB(1, 140);
53 echo '<br>';
54 $secondCase->notAORnotB(11, 14);
55 echo '<br>';
56 $secondCase->notAORnotB(1, 140);
We have tested the second law by passing the same value through the class variables and methods. Watch the output, it gives us the same value for two different methods.
1 // output of code 3.2
2
3 The number is neither less than equal to 10 nor greater than equal to 15
4 Addition of two numbers : 141
5 The number is neither less than equal to 10 nor greater than equal to 15
6 Addition of two numbers : 141
In Java, or C++, you can apply the same logic to test that the laws work. Consider the following Java file where we can comment out the entire process, because we need to test the same code separately.
1 // code 3.3
2 //Java
3
4 package fun.sanjibsinha;
5
6 /*
7 not (a and b) is the same as (not a) or (not b)
8 not (a or b) is the same as (not a) and (not b)
9 */
10
11 import java.util.Scanner;
12
13 public class DeMorganslaw {
14 static int numOne = 0;
15 static int numTwo = 0;
16 static int additionOfTwoNumbers = 0;
17 public static void main(String[] args) {
18 System.out.println("Enter a positive number: ");
19 Scanner one = new Scanner(System.in);
20 numOne = one.nextInt();
21 System.out.println("Enter another positive number: ");
22 Scanner two = new Scanner(System.in);
23 numTwo = two.nextInt();
24 /*
25 These two are same:
26 not (a and b) is the same as (not a) or (not b)
27
28 if(!(numOne >= 10 && numTwo <= 15)){
29 additionOfTwoNumbers = numOne + numTwo;
30 System.out.println("Addition of two numbers is : " + additionOfTwoNumber\
31 s);
32 } else {
33 System.out.println("The number is neither less than equal to 10 " +
34 "nor greater than equal to 15");
35 }
36
37 Enter a positive number:
38 11
39 Enter another positive number:
40 14
41 The number is neither less than equal to 10 nor greater than equal to 15
42
43 Enter a positive number:
44 1
45 Enter another positive number:
46 140
47 Addition of two numbers is : 141
48
49
50 if(!(numOne >= 10) || !(numTwo <= 15)){
51 additionOfTwoNumbers = numOne + numTwo;
52 System.out.println("Addition of two numbers is : " + additionOfTwoNumber\
53 s);
54 } else {
55 System.out.println("The number is neither less than equal to 10 " +
56 "nor greater than equal to 15");
57 }
58 Enter a positive number:
59 11
60 Enter another positive number:
61 14
62 The number is neither less than equal to 10 nor greater than equal to 15
63
64 Enter a positive number:
65 1
66 Enter another positive number:
67 140
68 Addition of two numbers is : 141
69
70 */
71
72 /*
73 These two are same:
74 not (a or b) is the same as (not a) and (not b)
75
76 if(!(numOne >= 10 || numTwo <= 15)){
77 additionOfTwoNumbers = numOne + numTwo;
78 System.out.println("Addition of two numbers is : " + additionOfTwoNumber\
79 s);
80 } else {
81 System.out.println("The number is neither less than equal to 10 " +
82 "nor greater than equal to 15");
83 }
84 Enter a positive number:
85 11
86 Enter another positive number:
87 14
88 The number is neither less than equal to 10 nor greater than equal to 15
89
90 Enter a positive number:
91 1
92 Enter another positive number:
93 140
94 Addition of two numbers is : 141
95
96
97 if(!(numOne >= 10) && !(numTwo <= 15)){
98 additionOfTwoNumbers = numOne + numTwo;
99 System.out.println("Addition of two numbers is : " + additionOfTwoNumber\
100 s);
101 } else {
102 System.out.println("The number is neither less than equal to 10 " +
103 "nor greater than equal to 15");
104 }
105
106 Enter a positive number:
107 11
108 Enter another positive number:
109 14
110 The number is neither less than equal to 10 nor greater than equal to 15
111
112 Enter a positive number:
113 1
114 Enter another positive number:
115 140
116 Addition of two numbers is : 141
117
118
119 */
120
121 }
122 }
Inside the commented out sections we have kept the code and output together. In Java, you need to test each law separately. In PHP, we could have used a form inputs to build a web application where we can pass two values to see the result dynamically.
Logical Expression
We can create compound expression by combining logical operations. De Morgan’s laws are based on this paradigm. Consider the following expression:
1 not(a or b)
Whether the above compound expression is ‘true’ or ‘false’,depends on different types of combinations. If ‘a’ and ‘b’ are both false, the negation of sub-expression (a or b) is true. If any one of them is ‘true’, then the value will be ‘false’, and this combination may take different shapes according to the ‘truth table’, which we have seen before.
A major part of Discrete Mathematical operations is based on Boolean Algebra and the associated logical expressions. Just to recapitulate, we need to remember that there are three logical operators; they are ‘&&’ (and), ‘||’ (or), and ‘!’ (negation). The ‘truth table’ is based on them.
Logical operators manipulate the logical values. The same way, ‘relational operators’ also manipulate the logical values.
There are two kinds of relational operators: equality and ordering.
The two equality operators are: ‘==’ and ‘!=’. The ‘==’ operation is true when the two operands have the same value. The same way, ‘!=’ operation is true when two operands have different values.
The ordering operators test the relative size of two values. They are: ‘<’ (less than), ‘>’ (greater than), ‘>=’ (greater than or equal to) and ‘<=’ (less than or equal to).
1 Tips: For complicated expressions, operator precedence is important. Arithmetic oper\
2 ators have greater precedence than the relational and logical operators. However, re\
3 lational and logical operators have greater precedence than assignment operators. Ag\
4 ain, relational operators have greater precedence than logical operators.
Short Circuit Evaluation
Before all the operands have been considered in the evaluation of any logical expression, we sometimes know the value of the expression. Consider a situation, where two operands are using ‘and’ operation. If any one of the operands is known to be false, we instantly know that the result is ‘false’. On the other hand, when two operands use the ‘or’ operation and any one of the operands is known to be true, then we know that the value of the expression is true.
A programming language requires that the left operand (the first one) be evaluated before the right (the second one) operand. If the value of the logical expression is determined from the first operand, the second operand is not evaluated.
This type of evaluation is known as short circuit evaluation and bot ‘and’ and ‘or’ operations use this kind of special evaluation. To make long story short, the second condition is not checked, depending on what type of operations take place, whether you are using ‘and’ or ‘or’; moreover, what is the value of the first condition. We will check the both cases, using Python. We are going to use Python 3.6.
1 // code 3.4
2 // Python 3.6
3
4 print("hello")
5
6 numOne = 10
7 numTwo = 0
8
9 if(numTwo == 10 and (numOne / numTwo == 3)):
10 print("It won't give any error!")
11 # since the first condition is false, it won't execute the second one
12 # it goes to the else bock
13 else:
14 print("It didn't give any error because of short circuit evaluation!")
15
16 if(numTwo == 0 or (numOne / numTwo == 3)):
17 print("It won't give any error!")
18 # since the first condition is true, it won't execute the second one
19 else:
20 print("It didn't give any error because of short circuit evaluation!")
Read the comment section. Besides, we can get the idea from the output:
1 // output of code 3.4
2
3 hello
4 It didn't give any error becuase of short circuit evaluation!
5 It won't give any error!
Syntax, Semantics and Conditional Execution
So far we have seen many usages of ‘if’ statement. In a program, when the ‘if’ statement is reached, it first checks whether the operation is true or not. If it is true,it is executed, the code between the ‘if block’ is acted upon. Otherwise, if the ‘action’ is not acted upon inside the ‘if block’, program execution continues with the next statement in the program.
The description of the execution part of any ‘if’ statement, is called ‘semantic’ definition.
Syntax and Semantics
We need to take a very quick look at these two guys – syntax and semantics. They are very essential in every programming language.
Here the rule of natural language follows. Syntax describes the rules by which the words can be combined into sentences. On the other hand, semantics describes what they mean.
Consider a simple example.
1 Here is my friend, Emilia.
In the above sentence, the syntax and semantics are both flawless. There is no syntactical error and the semantic definition is meaningful.
However, what about the next sentence?
1 Here is my chair, Emilia.
It is also syntactically correct. There is no syntax error. But, is that sentence meaningful? Semantics describes what the sentence means, and it means nothing. We neither give name to our chairs, nor we introduce them like this.
In a programming language, syntactical rules are important. We should not miss a semicolon after an expression in many languages like C++, Java, PHP, etc. But we should not use semicolon in Python, in the same situation. That is syntax. We should maintain those rules.
We cannot use the keywords or reserved words as variable or function name. That part is OK. But what about the semantics?
That is equally important. If our logical expression is wrong, the program is not meaningful anymore, it takes inputs and gives us erratic output.
In the next two programs, we will see how this syntax and semantics work together in two different programming languages.
We have used Python to create a base of calculation using the ‘if-else’ logic.
1 // code 3.5
2 // python 3.6
3
4 # base of calculation with the help of if-else logic
5
6 print("Enter a number: ")
7 left = int(input())
8 print("Enter another number: ")
9 right = int(input())
10 result = 0
11 print("Enter any arithmetic operator like +, -, * and / for "
12 "addition, subtraction, multiplication and division respecti\
13 vely: ")
14 arithmeticOperator = str(input())
15
16 if(arithmeticOperator == '+'):
17 result = left + right
18 elif(arithmeticOperator == '-'):
19 result = left - right
20 elif(arithmeticOperator == '*'):
21 result = left * right
22 elif(arithmeticOperator == '/'):
23 if(right != 0):
24 result = left / right
25 else:
26 print("Denominator is zero.")
27 else:
28 print(arithmeticOperator + " is not recognized!")
29
30 if(arithmeticOperator == '/' and right == 0):
31 print("The result is undefined.")
32 else:
33 print(str(left) + " " + str(arithmeticOperator) + " " + str(right) + " = " + str\
34 (result))
We have only used one option to test that the program runs fine, when the denominator is zero.
1 // output of code 3.5
2
3 Enter a number:
4 2
5 Enter another number:
6 0
7 Enter any arithmetic operator like +, -, * and / for addition, subtraction, multipli\
8 cation and division respectively:
9 /
10 Denominator is zero.
11 The result is undefined.
In the next program, we have used the same logic for base of calculation, in a slight different way, in C++, using the ‘switch-case’ statement. Compare the syntax between these two programs, semantically they are equal, rather meaningful.
1 // code 3.6
2 // C++
3
4 /*
5 * Creating a base calculator with the help of switch-case logic
6 */
7
8 #include <iostream>
9 #include <string>
10 #include <cmath>
11 #include <cstdlib>
12 #include <sstream>
13 #include <numeric>
14 #include <string>
15 #include <vector>
16 #include <cstddef>
17 #include <limits>
18
19 int main(){
20
21 std::cout << "Enter a number: " << "\n";
22 int left = 0;
23 std::cin >> left;
24 std::cout << "Enter another number: " << "\n";
25 int right = 0;
26 std::cin >> right;
27 std::cout << "Enter any arithmetic operator like +, -, * and / for "
28 << "addition, subtraction, multiplication and division respectively:: " \
29 << "\n";
30 char arithmeticOperator;
31 std::cin >> arithmeticOperator;
32
33 int result = 0;
34
35 switch(arithmeticOperator){
36 case '+':
37 result = left + right;
38 break;
39 case '-':
40 result = left - right;
41 break;
42 case '*':
43 result = left * right;
44 break;
45 case '/':
46 if(right != 0){
47 result = left / right;
48 } else {
49 std::cout << "The denominator is zero. The value is undefined." << "\
50 \n";
51 return 1;
52 }
53 break;
54 default:
55 std::cout << arithmeticOperator << " is not recognized." << "\n";
56 return 1;
57
58 }
59 std::cout << left << " " << arithmeticOperator << " " << right << " = "
60 << result << "\n" ;
61
62 return 0;
63 }
We have tested the code in various ways, to find out the semantics is meaningful and the code runs in every possible situation.
1 // output of code 3.6
2
3 Enter a number:
4 12
5 Enter another number:
6 12
7 Enter any arithmetic operator like +, -, * and / for addition, subtraction, multipli\
8 cation and division respectively::
9 *
10 12 * 12 = 144
11
12 RUN FINISHED; exit value 0; real time: 5s; user: 0ms; system: 0ms
13
14
15 Enter a number:
16 12
17 Enter another number:
18 0
19 Enter any arithmetic operator like +, -, * and / for addition, subtraction, multipli\
20 cation and division respectively::
21 /
22 The denominator is zero. The value is undefined.
23
24 RUN FINISHED; exit value 1; real time: 8s; user: 0ms; system: 0ms
25
26
27 Enter a number:
28 12
29 Enter another number:
30 2
31 Enter any arithmetic operator like +, -, * and / for addition, subtraction, multipli\
32 cation and division respectively::
33 ===
34 = is not recognized.
35
36 RUN FINISHED; exit value 1; real time: 10s; user: 0ms; system: 0ms
From previous code snippets we have learned two important lessons. A program should be syntactically correct, as well as semantically correct. If we write a same program in two different languages, their syntax may be different but semantics is same. There are also two types of semantics – one is known as ‘static semantics’ and another known simply as ‘semantics’.
By the term static semantics, we mean program runs well, gives us no errors, but at the end of the day it is not meaningful. It gives us outputs that were not intended while we wrote the code.
Full semantics, on the other hand, may run the loop for ever or simple crash the program, while we try to run it. In the next program, we are going to sort three numbers in ascending order. Here semantics plays a very vital role.
Why? We will see in a minute.
1 // code 3.7
2 //Python 3.6
3
4 # take three numbers and sort them in ascending order
5
6 print("Enter first number: ")
7 first = int(input())
8 print("Enter second number: ")
9 second = int(input())
10 print("Enter third number: ")
11 third = int(input())
12 outputOne = 0
13 outputTwo = 0
14 outputThree = 0
15
16 if((first <= second) and (second <= third)):
17 outputOne = first
18 outputTwo = second
19 outputThree = third
20 elif((first <= third) and (third <= second)):
21 outputOne = first
22 outputTwo = third
23 outputThree = second
24 elif((second <= first) and (first <= third)):
25 outputOne = second
26 outputTwo = first
27 outputThree = third
28 elif((second <= third) and (third <= first)):
29 outputOne = second
30 outputTwo = third
31 outputThree = first
32 elif((third <= first) and (first <= second)):
33 outputOne = third
34 outputTwo = first
35 outputThree = second
36 else:
37 outputOne = third
38 outputTwo = second
39 outputThree = first
40
41 print("The numbers in ascending order: " + str(outputOne) + ", "
42 + str(outputTwo) + ", and " + str(outputThree))
Syntactically and semantically this program is clean and it reflects in the output:
1 // output of code 3.7
2
3 Enter first number:
4 200
5 Enter second number:
6 1
7 Enter third number:
8 500
9 The numbers in ascending order: 1, 200, and 500
In the above program, you can change the static semantics just by changing the positions of the variables; in that case, your code snippets is syntactically correct, and it is built successfully and runs correctly without crashing the program. However, the output will be erratic, because the static semantics is incorrect.
The role of semantics as a whole becomes increasingly important as the logical expressions get complicated. Not only that we always write code with the help of ‘if-else’ or ‘switch-case’; we need control constructs, different types of looping, we need to write complex algorithm, etc.
While write our program that way, we need to keep one thing in mind, what we write should make sense, it should be meaningful. The concept of semantics need to be understood for that reason.
Why we need Control Constructs
We need it because computational thinking gives us enough power to write sequence of steps or recipe for doing any repetitive job. Suppose we need to find out average of a finite set of different numbers. We might imagine doing this for 5, 6 or 10. However, when the list grows and reaches 100000, it becomes impossible.
We need to find out some solution to do that. Suppose our application is programmed to take 100000 inputs from a file where the numbers are stored. Can we enter them manually and see what would be the output?
Consider a program like the following one:
1 // code of 3.8
2 // python 3.6
3
4 # we will compute average of six numbers by manual addition
5
6 print("Enter first number: ")
7 first = int(input())
8 print("Enter second number: ")
9 second = int(input())
10 print("Enter third number: ")
11 third = int(input())
12 print("Enter fourth number: ")
13 fourth = int(input())
14 print("Enter fifth number: ")
15 fifth = int(input())
16 print("Enter sixth number: ")
17 sixth = int(input())
18 result = 0.00
19 result = (first + second + third + fourth + fifth + sixth) / 6
20 print("The average of six numbers is : " + str(result))
For 6 numbers it is OK. The output gives us the proper value.
1 // output of code 3.8
2
3 Enter first number:
4 1
5 Enter second number:
6 2
7 Enter third number:
8 3
9 Enter fourth number:
10 4
11 Enter fifth number:
12 5
13 Enter sixth number:
14 6
15 The average of six numbers is : 3.5
However, this type of operations is better handled by iteration using the ‘while’ statement. What we have seen in the above code makes us believe that we need an action that should be repeatedly executed. We add two numbers and get a total. Next, we add the third number with the running total. It will go on as long as the number of values processed is less than the finite set of numbers that we want to add and then divide by that number to find the average.
Now we need to map that problem to our program domain with the help of ‘while’ statement. Because the ‘while’ statement deals execution of any repetitive action better than any other statement, we can write it using ‘natural language’ this way:
1 while(the number of values processed is less than the number of finite set of number\
2 s)
3
4 we take input
5
6 the running total is adding more input numbers as long as the loop continues
7
8 after each cycle the number of values processed is increased by 1
9
10 the loop ends as the number of values processed is equal to the number of finite se\
11 t of numbers
12
13 now we have the grand total of all the numbers belonging to the finite set of numbers
14
15 to get the average we divide the total by the the number of finite set of numbers
Now the time has come to map this problem on our program domain, this way:
1 // code of 3.9
2 // python 3.6
3
4 # we will compute average of six numbers by iteration using while loop
5
6 totalNumberToCompute = 6
7
8 # since number of iteration yet to be taken
9 numberOfIteration = 0
10 # we have not got the total addition of all numbers
11 total = 0.00
12 print("Please enter " + str(totalNumberToCompute) + " numbers : ")
13 print()
14
15 while(numberOfIteration < totalNumberToCompute):
16 value = 0.00
17 value = float(input())
18 total += value
19 numberOfIteration += 1
20
21 averageOfSixNumbers = 0.00
22 averageOfSixNumbers = total / numberOfIteration
23 print("The average of six numbers is : " + str(averageOfSixNumbers))
And here goes the same output that we have seen in the previous code (3.8).
1 // output of code 3.9
2
3 Please enter 6 numbers :
4
5 1
6 2
7 3
8 4
9 5
10 6
11 The average of six numbers is : 3.5
In this section, we have learned many important concepts. You have probably noticed that we are handling with discrete numbers. We are also talking about a finite set of numbers. It is an integral part of discrete mathematical operations.
In discrete mathematics, we almost always quantify. We always check the ‘existential’ logical expression like ‘if there is’ or ‘if there exists’, etc. Moreover, we also check for ‘global’ values that is meant ‘for all’. For all the numbers inside the finite set of numbers, we are adding them one after another; that leads us to a grand total. We also count how many numbers are there and divide the grand total by the total numbers present inside the finite set.
As we progress, we will see how these concepts come handy for the functions. How set theory is pertinent for collections or data structure, etc. There are a lot of things to cover and we are afraid that we won’t be able to cover everything. However, we will try our best to learn a few things, so that in future we can take that knowledge forward.
And by the way, we have also learned what algorithm means actually! To make the long story short, it is a sequence of instructions to solve a problem.
In the next section, we will cut into the subject and turn over the topic to learn more!
Discrete Mathematical Notations and Algorithm
One of the main branches of computer science is algorithm. One of the main branches of discrete mathematics is also algorithm. That is why we use concepts and notations from discrete mathematics in computational algorithm. We can map any problem from the mathematical domain to program domain with the help of same algorithm.
When you combine mathematics and computation, algorithm means a well-defined instructions that are computer-implementable. Yet, mathematics is a separate domain, when we try to map one mathematical problem into computational domain, we need a sequence of instructions that should be unequivocal, which means the algorithm should exhibit a single clearly defined meaning. A distinct meaningful output should come out from the inputs.
Now, we have learned, what algorithm is, however, we must know why we need it.
The question is why we needed algorithm four thousand five hundred years ago in Babylon? Why we needed it three thousand five hundred years ago in Egypt, or later in Greece?
The answer is: to decide something. When we travel by one car and come to a road-divider that indicates two ways, we cannot go to two ways simultaneously. Our decision should be discrete. 1 or 0. True or false.
In contrast, if we have two or more cars, the decision might be something else.
Although ancient Babylonian, Egyptian or Greek mathematicians started using the concepts of algorithm since antiquity, the very term ‘algorithm’ is derived from the name of the ninth century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī. Much before that, Greek mathematicians used sieve of Eratosthenes to find prime numbers; they also used Euclidean algorithm to find greatest common divisors (GCD).
Decision making very heavily depends on effective calculation. In the last century, many renowned mathematicians worked on that and still it goes on. High level programming languages have to come to terms with that. They have to do that, because as time passes by, the size of data has increased, and it will increase with the passage of the time.
We have enough theoretical discussion, let us plunge into code to understand how we can map our problems from mathematical domain to our computational domain. Let us start with prime numbers. In ancient time, Greek mathematicians used sieve of Eratosthenes to find prime numbers. We have plenty of other solutions at our hand now. Still, we need to know what does a prime number actually mean.
A prime number is a natural number that has exactly two discrete natural divisors. Consider this example: 2 is a prime number, because there are exactly two divisors: 1 and 2. The same way, 11 is a prime number, because there are exactly two divisors: 1 and 11.
Based on that concept, we can write our algorithm in natural language, this way:
1 take input of any natural number
2
3 process to find how many factors are there
4
5 count the number of factors
6
7 if the number of factors is equal to two, then the number is prime
8
9 if the number is greater than two, then the number is not prime
Let us tale that algorithm to our computational domain using Java programming language.
1 // code 3.10
2 // Java
3
4 package fun.sanjibsinha;
5
6 import java.util.*;
7 import java.math.*;
8 public class TryingToFindPrime {
9
10 private static Scanner sc;
11
12 public static void main(String[] args) {
13
14 int numOne, integerOne;
15 sc = new Scanner(System.in);
16
17 System.out.println("Please Enter any number to Find Factors: ");
18 numOne = sc.nextInt();
19
20 int controOne = 0;
21 for (integerOne = 1; integerOne <= Math.sqrt(numOne); integerOne++)
22 {
23 if (numOne % integerOne == 0) {
24 if (numOne / integerOne == integerOne){
25 controOne++;
26 } else {
27 controOne = controOne + 2;
28 }
29 }
30 }
31 if(controOne == 2){
32 System.out.println(numOne + " is prime.");
33 } else {
34 System.out.println(numOne + " is not prime.");
35 }
36 }
37 }
We can test the program by giving two inputs like 49 and 47.
1 // output of code 3.10
2
3 Please Enter any number to Find Factors:
4 49
5 49 is not prime.
6
7 Please Enter any number to Find Factors:
8 47
9 47 is prime.
Here, in the above code, the algorithm is one of the simplest. We have counted the number of factors of any number and test the condition, whether that number crosses 2 or not.
Let us solve the same problem with the help of a different algorithm.
First, we see the code, then we will discuss the algorithm used in it.
1 //code 3.11
2 // Java
3
4 package fun.sanjibsinha;
5 import java.util.*;
6 import java.math.*;
7 public class FindingPrime {
8
9 private static Scanner sc;
10 static int input = 0;
11
12 static boolean isPrime(int num)
13 {
14 if (num <= 1)
15 return false;
16 if (num <= 3)
17 return true;
18 if (num % 2 == 0 || num % 3 == 0)
19 return false;
20 for (int i = 5; i * i <= num; i = i + 6)
21 if (num % i == 0 || num % (i + 2) == 0)
22 return false;
23 return true;
24 }
25
26 public static void main(String[] args) {
27
28 System.out.println("Enter a number to test whether it is prime or not? ");
29 sc = new Scanner(System.in);
30 input = sc.nextInt();
31 if(isPrime(input)){
32 System.out.println(input + " is prime.");
33 } else {
34 System.out.println(input + " is not prime.");
35 }
36 }
37 }
In the above code, we have used a boolean method that uses one parameter; now we can pass any number to test whether that number is prime or not.
We have used the trial and division method to find out whether the output is true or false.
1 // output of code 3.11
2
3 Enter a number to test whether it is prime or not?
4 47
5 47 is prime.
6
7 Enter a number to test whether it is prime or not?
8 49
9 49 is not prime.
The sieve of Eratosthenes algorithm works on a different type of algorithm. Let us first write the algorithm in natural language. By the way, we should remember that the sieve of Eratosthenes algorithm is used to find out prime numbers in a range of numbers, such as we can test how many primes are there between 2 and 30. Usually the end number is denoted by ‘n’; for the sake of simplicity, we consider an integer. The algorithm goes like the following:
1 1. First we need to create a list of consecutive integers from 2 through a certain n\
2 umber like 30, as we have seen in the above statement: (2, 3, 4, …, 30); we do this,\
3 because 2 is the smallest prime number
4
5 2. Therefore, we can initialize a variable like this: startingNUmber = 2
6
7 3. Now, we can specify the multiples of the ‘startingNUmber’ by counting in incremen\
8 ts of ‘startingNUmber’ from (2 * startingNUmber) to 30, and mark them in the list, \
9 like this:
10 (2 * startingNUmber), (3 * startingNUmber), (4 * startingNUmber), and so on.
11
12 4. It is not to be mentioned that multiples of 2 will never be the primes, because t\
13 he number of factors becomes greater than 2.
14
15 5. Next, we will find the first number that is greater than the ‘startingNUmber’; if\
16 there is no such number, then we stop. Otherwise, let ‘startingNUmber’ equal the ne\
17 w number, which is the next prime and repeat from the step 3.
18
19 6. When the algorithm ends, the numbers not marked in the list below 30, are all pri\
20 mes.
Let us build our program based on this algorithm. This time we have used python 3.6, to get the result. Each step is mentioned inside the comments, we have used in this case.
1 // code 3.12
2 // python 3.6
3
4 # Sieve Of Eratosthenes
5
6 def SieveOfEratosthenes(rangeOfNumbers):
7 # let us create a boolean array "primeArray[...]" that takes a range of any numb\
8 ers
9 # next we initialize the array with the entries as true
10 # now if primeArray[anyNUmber] is false if it is not prime, else the number is p\
11 rime
12 # the startingNumber is 2, because 1 is not prime
13 primeArray = [True for anyNumber in range(rangeOfNumbers + 1)]
14 # we have added 1 with the rangeOfNumbers, so that the endNumber is included
15 startingNUmber = 2
16 while (startingNUmber * startingNUmber <= rangeOfNumbers):
17 # logically if primeArray[startingNumber] is not changed, then it is a prime
18 # in fact, 2 is prime
19 if (primeArray[startingNUmber] == True):
20 # all multiples of startingNumber is not prime
21 # the factors of the multiples are greater than 2
22 for anyNumber in range(startingNUmber * 2, rangeOfNumbers + 1, startingN\
23 Umber):
24 # in such cases, those numbers are not prime
25 primeArray[anyNumber] = False
26 startingNUmber += 1
27 primeArray[0] = False
28 primeArray[1] = False
29 # now we can print all prime numbers belonging to that range of numbers
30 for startingNUmber in range(rangeOfNumbers + 1):
31 if primeArray[startingNUmber]:
32 print(startingNUmber)
33
34 SieveOfEratosthenes(20)
Here is the output of the above code where we have passed 20, to get all the primes below 20.
1 // output of code 3.12
2
3 2
4 3
5 5
6 7
7 11
8 13
9 17
10 19
In this algorithm some numbers are marked more than once, like 8, for 2 and 4, both. The main idea is when the number is composite, that is, when it is a multiple of some prime numbers, it is marked.
Since, every even integers are marked out we list odd numbers only (3, 5, …, n), and count in increments of (2 * startingNUmber), thus marking out only odd multiples of ‘startingNUmber’.
After that, multiple of primes becomes composite, having more than two factors, making them composite.
The same way, thousand years ago Greek mathematicians used Euclidean algorithm to find the greatest common divisors of two numbers. Originally it was subtraction based, later the same algorithm had been written numerous way, re-modeling the original one.
We will see those versions later when we will discuss Euclidean algorithm in detail. However, we can take a quick look at the original Euclidean algorithm in a Java program, as shown in the following code snippets.
1 // code 3.13
2 // Java
3
4 package fun.sanjibsinha.gcd;
5
6 import java.util.Scanner;
7
8 public class EuclidAlgorithm {
9
10 static int numOne = 0;
11 static int numTwo = 0;
12
13 //this is Euclid's original version
14 static int subtractionBased(int numOne, int numTwo){
15 while (numOne != numTwo){
16 if(numOne > numTwo)
17 numOne = numOne - numTwo;
18 else
19 numTwo = numTwo - numOne;
20 }
21 return numOne;
22 }
23
24 public static void main(String[] args) {
25 System.out.println("Enter a number: ");
26 Scanner num1 = new Scanner(System.in);
27 numOne = num1.nextInt();
28 System.out.println("Enter another number: ");
29 Scanner num2 = new Scanner(System.in);
30 numTwo = num2.nextInt();
31 System.out.println("You have entered " + numOne + " and " + numTwo);
32 System.out.println("The GCD is: " + subtractionBased(numOne, numTwo));
33 }
34 }
We can take any two numbers and see how this algorithm works.
1 // output of code 3.13
2
3 Enter a number:
4 1071
5 Enter another number:
6 462
7 You have entered 1071 and 462
8 The GCD is: 21
The Euclid’s Algorithm is one of the oldest algorithms that is still relevant to, not only discrete mathematical conceptions, but also in the computational world of 1 and 0.
In the above program, we have seen that the effectiveness of the algorithm has been proved by the correct output from given inputs.
Now, many things depend on algorithm. Like hardware, algorithm is also considered to be technology for one reason. Every algorithm has its own time-complexity. When an algorithm takes higher time to produce an intended result, it is considered to be non-optimal. On the contrary, less the time-complexity, higher is the desirability.
Therefore, these two parts are very critical while we consider an algorithm. How much time it takes to perform the algorithm, is a big issue. On the other hand, adaptability of the algorithm to computers is another big issue.
As far as Euclidean algorithm is concerned, we can make this algorithm faster by making it recursive based. We can also write the same program in different ways, using Python 3.6 in this case.
1 // code 3.14
2 // python 3.6
3
4 # finding greatest common divisor by two different methods
5
6 def GCDOne(numOne, numTwo):
7 if(numTwo == 0):
8 return numOne
9 else:
10 temp = numOne % numTwo
11 return GCDOne(numTwo, temp)
12
13
14 def GCDTwo(num1, num2):
15 if(num2 == 0):
16 return num1
17 elif(num1 > num2):
18 return GCDTwo((num1 - num2), num2)
19 else:
20 return GCDTwo((num2 - num1), num1)
21
22
23 print(GCDOne(1071, 462))
24 print(GCDTwo(1071, 462))
The output is quite expected:
1 // output of code 3.14
2
3 21
4 21
We always face a trade-off between elegance and speed. Some computer scientists feel, the smallest possible program for producing the output is the most ‘elegant’. The most optimal algorithm is the most desirable. Speed matters.
One criterion is definitely the time taken to perform the algorithm, another is its simplicity, which is also termed as elegance.
While we write any kind of program, we need to keep those things in mind.
We have learned that the time taken for running an algorithm is important. It is measured by the ‘Time Complexity’. Our final goal is to improve the performance of any algorithm. To do that, we need to count the number of elementary operations performed by the algorithm. ‘Time Complexity’ does the same thing.
We will cover these concepts in great detail in chapter 5, after understanding data structures. Understanding data structures is needed for one reason: for building complex algorithm, we use various types of data structures. To understand basic algorithm, we have used array, a basic collection of a definite set of elements. Before concluding this chapter, we will take a look at three code snippets, where we have sorted a definite set of discrete integers and arrange them in ascending order.
To make this operation successful, we have used Quicksort algorithm.
The Quicksort algorithm is a popular sorting algorithm that is often used not only for sorting numbers, but also objects from any custom class. Furthermore, there are many other sorting algorithm, which are complex, and we will learn them in the coming chapters.
Before we present the first code snippet, using Python 3.6,we need to know one more thing about Quicksort algorithm. It is of an average ‘Time Complexity’ and it is represented by Big O notation, as O(nlogn).
For the beginners, it may appear intimidating at first, yet it is not, when you understand the principles behind this Asymptotic notations. Again, to remind you, we will cover this in great detail in chapter 5.
Let us see the first Quicksort algorithm example.
1 // code 3.15
2 // python 3.6
3
4 # Quick Sort Algorithm
5
6 def smallerToGreater(array, startingNUmber, endingNUmber):
7 searchingIndex = array[startingNUmber]
8 lowIndex = startingNUmber + 1
9 highIndex = endingNUmber
10
11 while True:
12 # we have a collection of numbers; we need to place those numbers in ascendi\
13 ng order
14 # in that collection there should be a low index number and high index number
15 # we need to find the numbers that are larger than the rest amd send it to t\
16 he right
17 # first we need a searching index number that will check the current value
18 # if the current value is larger than the searching index,
19 # then we should send to the right side of the searching index and we can mo\
20 ve left
21 # to the next element.
22 # the low index number should remain always lower than others,
23 # and the numbers larger than the searching index should remain on the right\
24 side
25 while lowIndex <= highIndex and array[highIndex] >= searchingIndex:
26 highIndex = highIndex - 1
27
28 # we also need to traverse the collection in the opposite process
29 while lowIndex <= highIndex and array[lowIndex] <= searchingIndex:
30 lowIndex = lowIndex + 1
31
32 # if our above algorithm does not work, we exit the loop
33 if lowIndex <= highIndex:
34 array[lowIndex], array[highIndex] = array[highIndex], array[lowIndex]
35 # else the loop continues
36 else:
37 # and we exit out of the loop
38 break
39
40 array[startingNUmber], array[highIndex] = array[highIndex], array[startingNUmber]
41
42 return highIndex
43
44 def quickSort(arrayOfNumbers, startingNumber, endingNumber):
45 if startingNumber >= endingNumber:
46 return
47
48 partitioningIndex = smallerToGreater(arrayOfNumbers, startingNumber, endingNumbe\
49 r)
50 quickSort(arrayOfNumbers, startingNumber, partitioningIndex - 1)
51 quickSort(arrayOfNumbers, partitioningIndex + 1, endingNumber)
52
53 arrayOfNUmbers = [100, 45, 1, 8, 47895, 5, 56, 23, 0, 89]
54
55 quickSort(arrayOfNUmbers, 0, len(arrayOfNUmbers) - 1)
56 print("The above random array of numbers in ascending order: " + str(arrayOfNUmbers))
Let us first see the output first, after that we will discuss the Quicksort algorithm.
1 // output of code 3.15
2
3 /home/ss/IdeaProjects/discretemathsdatastructures/PythonDiscrete/venv/bin/python /ho\
4 me/ss/IdeaProjects/discretemathsdatastructures/PythonDiscrete/QuickSort/QucikSortExa\
5 mpleOne.py
6
7 The above random array of numbers in ascending order: [0, 1, 5, 8, 23, 45, 56, 89, 1\
8 00, 47895]
9
10 Process finished with exit code 0
In the above code snippets, if you go through the comments,you will get the idea. We need a collection that has a definite set of elements, here integers. We can think it as ‘input’ or ‘n’, which is a variable. Now as the value of ‘n’ increases, the ‘Time Complexity’ varies.
In the above algorithm, we keep testing the value of the integer with respect to the search index number, and keep the larger number on the right side. It arranges the collection in an ascending order.
Now, almost same thing we are going to do using C language. In the first case, we will have a definite set of integers, just like above. In the second case, we will take input from the users and apply the Quicksort algorithm.
Let us see the first code snippet that handles definite set of integers.
1 // code 3.16
2 //C
3
4 #include<stdio.h>
5
6 // we need an utility function to swap two numbers
7 // we will use this function later
8 void swappingNumber(int* numOne, int* numTwo){
9 int temp = *numOne;
10 *numOne = *numTwo;
11 *numTwo = temp;
12 }
13 /*
14 * this function will place a random collection of numbers
15 * in an ascending order
16 * first we assume the last element of an array is the pivot index,
17 * such that all the smaller numbers will be on the left side
18 * of pivot index, and all the higher numbers will be on
19 * the right side of the pivot index
20 */
21 int arrangeNumbers (int arrayOfNumbers[], int lowIndex, int highIndex){
22 int pivotIndex = arrayOfNumbers[highIndex];
23 int indexNumber = (lowIndex - 1);
24 for (int initialNUmber = lowIndex; initialNUmber <= highIndex - 1; initialNUmber\
25 ++){
26 if (arrayOfNumbers[initialNUmber] <= pivotIndex){
27 indexNumber++;
28 swappingNumber(&arrayOfNumbers[indexNumber], &arrayOfNumbers[initialNUmb\
29 er]);
30 }
31 }
32 swappingNumber(&arrayOfNumbers[indexNumber + 1], &arrayOfNumbers[highIndex]);
33 return (indexNumber + 1);
34 }
35
36 void quickSortTheCollection(int arrayOfNumbers[], int lowIndex, int highIndex){
37 if (lowIndex < highIndex){
38 int pivotIndex = arrangeNumbers(arrayOfNumbers, lowIndex, highIndex);
39 quickSortTheCollection(arrayOfNumbers, lowIndex, pivotIndex - 1);
40 quickSortTheCollection(arrayOfNumbers, pivotIndex + 1, highIndex);
41 }
42 }
43
44 void displayInAscendingOrder(int arrayOfNumbers[], int sizeOfCollection){
45 int initialNUmber;
46 for (initialNUmber = 0; initialNUmber < sizeOfCollection; initialNUmber++)
47 printf("%d ", arrayOfNumbers[initialNUmber]);
48 printf("\n");
49 }
50
51
52 int main(int argc, char** argv){
53
54 int arrayOfNumbers[] = {22, 17, -8, 9, 11, 5};
55 int numberOfNUmbers = sizeof(arrayOfNumbers)/sizeof(arrayOfNumbers[0]);
56 quickSortTheCollection(arrayOfNumbers, 0, numberOfNUmbers - 1);
57 printf("The sorted array is: ");
58 displayInAscendingOrder(arrayOfNumbers, numberOfNUmbers);
59
60 return 0;
61 }
Again, we have written our sequence of steps in the comments. Just go through it and you will get the idea. We have solved the same problem, only in a different way.
The next Quicksort algorithm will take inputs from the users. However, there is a limit that we can control. Crossing that limit will give you an error, although a simple ‘if-else’ statement will solve the problem for us. The four different output shows how we have changed the program to fit the Quicksort algorithm.
1 // code 3.17
2 // C
3
4 #include<stdio.h>
5
6 void quicksortInOneFunction(int arrayOfNumbers[25], int firstIndex, int lastIndex){
7 int firstStorage, secondStorage, pivotIndex, temporaryStorage;
8 if(firstIndex < lastIndex){
9 pivotIndex = firstIndex;
10 firstStorage = firstIndex;
11 secondStorage = lastIndex;
12 while(firstStorage < secondStorage){
13 while(arrayOfNumbers[firstStorage] <= arrayOfNumbers[pivotIndex]
14 && firstStorage < lastIndex)
15 firstStorage++;
16 while(arrayOfNumbers[secondStorage] > arrayOfNumbers[pivotIndex])
17 secondStorage--;
18 if(firstStorage < secondStorage){
19 temporaryStorage = arrayOfNumbers[firstStorage];
20 arrayOfNumbers[firstStorage] = arrayOfNumbers[secondStorage];
21 arrayOfNumbers[secondStorage] = temporaryStorage;
22 }
23 }
24 temporaryStorage = arrayOfNumbers[pivotIndex];
25 arrayOfNumbers[pivotIndex] = arrayOfNumbers[secondStorage];
26 arrayOfNumbers[secondStorage] = temporaryStorage;
27 quicksortInOneFunction(arrayOfNumbers, firstIndex, secondStorage - 1);
28 quicksortInOneFunction(arrayOfNumbers, secondStorage + 1, lastIndex);
29 }
30 }
31
32 int main(){
33 int initialNumber, countingLimit, collectionOfNumber[6];
34 printf("How many integers you want for for quick sorting?"
35 " (Maximum value you can enter: 6): ");
36 scanf("%d", &countingLimit);
37 printf("Enter %d elements: ", countingLimit);
38 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
39 scanf("%d", &collectionOfNumber[initialNumber]);
40 quicksortInOneFunction(collectionOfNumber, 0, countingLimit - 1);
41 printf("The Sorted Order is: ");
42 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
43 printf(" %d", collectionOfNumber[initialNumber]);
44 return 0;
45 }
First we will take a look at the output, that will explain why we need to change this code a little bit to get it done perfectly.
1 // output of code 3.17
2
3 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 6
4 Enter 6 elements:
5 478
6 2
7 0
8 365894
9 25478
10 12
11 The Sorted Order is: 0 2 12 478 25478 365894
12 RUN FINISHED; exit value 0; real time: 16s; user: 0ms; system: 0ms
Here in the above code, we have set the limit of inputs to 6. Initially we have followed the rule and entered 6 integer value and we have got the perfect ascending order.
However, what happens, if someone breaks that limit and decides to enter 8 elements?
Here is the output:
1 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 8
2 Enter 8 elements:
3 1
4 2
5 3
6 6
7 5
8 4
9 89
10 78
11 *** stack smashing detected ***: <unknown> terminated
12
13 RUN FINISHED; Aborted; core dumped; real time: 17s; user: 0ms; system: 0ms
We have entered 8 elements and it breaks the code. The code is not working anymore.
To avoid such incidents, we need to change the algorithm a little bit.
1 // code 3.18
2 // C
3
4 #include<stdio.h>
5
6 void quicksortInOneFunction(int arrayOfNumbers[25], int firstIndex, int lastIndex){
7 int firstStorage, secondStorage, pivotIndex, temporaryStorage;
8 if(firstIndex < lastIndex){
9 pivotIndex = firstIndex;
10 firstStorage = firstIndex;
11 secondStorage = lastIndex;
12 while(firstStorage < secondStorage){
13 while(arrayOfNumbers[firstStorage] <= arrayOfNumbers[pivotIndex]
14 && firstStorage < lastIndex)
15 firstStorage++;
16 while(arrayOfNumbers[secondStorage] > arrayOfNumbers[pivotIndex])
17 secondStorage--;
18 if(firstStorage < secondStorage){
19 temporaryStorage = arrayOfNumbers[firstStorage];
20 arrayOfNumbers[firstStorage] = arrayOfNumbers[secondStorage];
21 arrayOfNumbers[secondStorage] = temporaryStorage;
22 }
23 }
24 temporaryStorage = arrayOfNumbers[pivotIndex];
25 arrayOfNumbers[pivotIndex] = arrayOfNumbers[secondStorage];
26 arrayOfNumbers[secondStorage] = temporaryStorage;
27 quicksortInOneFunction(arrayOfNumbers, firstIndex, secondStorage - 1);
28 quicksortInOneFunction(arrayOfNumbers, secondStorage + 1, lastIndex);
29 }
30 }
31
32 int main(){
33 int initialNumber, countingLimit, collectionOfNumber[6];
34 printf("How many integers you want for for quick sorting?"
35 " (Maximum value you can enter: 6): ");
36 scanf("%d", &countingLimit);
37
38 if(countingLimit <= 6){
39 printf("Enter %d elements: ", countingLimit);
40 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
41 scanf("%d", &collectionOfNumber[initialNumber]);
42 quicksortInOneFunction(collectionOfNumber, 0, countingLimit - 1);
43 printf("The Sorted Order is: ");
44 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
45 printf(" %d", collectionOfNumber[initialNumber]);
46 } else {
47 printf("You crossed the maximum value limit, try again!");
48 }
49
50 return 0;
51 }
Now, we are ready to face the worst case, where users will cross the limit of inputs and get the warning.
1 // output of code 3.18
2
3 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 8
4 You crossed the maximum value limit, try again!
5 RUN FINISHED; exit value 0; real time: 3s; user: 0ms; system: 0ms
Now, once the user crosses the limit, the warning gets displayed on the screen.
If the user follows the rule, it works perfectly again.
1 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 5
2 Enter 5 elements:
3 45
4 56
5 36
6 23
7 12
8 The Sorted Order is: 12 23 36 45 56
9 RUN FINISHED; exit value 0; real time: 8s; user: 0ms; system: 0ms
In this chapter, we won’t go any further about algorithm. In the next chapter,we will learn about data structures.
After that, in the following chapter, we will follow up complex types of algorithm using data structures.
I write regularly on Algorithm and Data Structure in
QUIZZ and Challenge on Chapter Three
Question 1: In De Morgan’s laws this statement is true: not (a and b) is the same as (not a) or (not b)
Option 1: No.
Option 2: Yes.
Answer: Option 2
===================
Question 2: A programming language always checks that the left operand (the first one) be evaluated before the right (the second one) operand.
Option 1: True.
Option 2: False.
Answer: Option 1
===================
Question 3: How many logical operators are there?
Option 1: Two
Option 2: Three
Option 3: Four
Option 4: None of the above is true
Answer: Option 2
=======================
Question 4: What is known as short circuit evaluation?
Option 1: A programming language always checks that the left operand (the first one) be evaluated before the right (the second one) operand.
Option 2: Both ‘and’, ‘or’ operations use this kind of special evaluation.
Option 3: the second condition is not checked, depending on what type of operations take place.
Option 4: All of the above.
Answer: Option 4
=======================
Question 5: Find a flaw in this sentence - “Here is my chair, Emilia.”
Option 1: It is syntactically wrong, but semantically correct.
Option 2: It is semantically wrong, but syntactically correct.
Option 3: It is semantically wrong, and syntactically wrong.
Option 4: None of the above is true.
Answer: Option 2
=======================
Challenge 1: De Morgan’s Laws on Boolean Algebra states the following rule:
One of the rule states, we can write this way, where ‘a’ and ‘b’ are two boolean values (true or false):
1 1. not (a and b) is the same as (not a) or (not b)
Based on this pribciple can you write any program in any programming language?Remember, in every programming language, the steps or algorithm will be the same.
Language used: PHP 8
Solution to Challenge 1:
1 // code
2
3
4 <?php
5
6 /*
7 * not (a and b) is the same as (not a) or (not b)
8 */
9
10 class DeMorganOne {
11
12 public $numOne;
13 public $numTwo;
14
15 public function notAandB($paramOne, $paramTwo) {
16
17 $this->numOne = $paramOne;
18 $this->numTwo = $paramTwo;
19 $additionOfTwoNumbers = $paramOne + $paramTwo;
20
21 //not(paramOne and paramTwo)
22 if(!($paramOne >= 10 && $paramTwo <= 15)){
23 echo "Addition of two numbers : $additionOfTwoNumbers";
24 } else {
25 echo "The number is neither less than equal to 10 nor greater than equal\
26 to 15";
27 }
28 }
29
30 public function notAORnotB($paramOne, $paramTwo) {
31
32 $this->numOne = $paramOne;
33 $this->numTwo = $paramTwo;
34 $additionOfTwoNumbers = $paramOne + $paramTwo;
35
36 //(not paramOne) or (not paramTwo)
37 if(!($paramOne >= 10) || !($paramTwo <= 15)){
38 echo "Addition of two numbers : $additionOfTwoNumbers";
39 } else {
40 echo "The number is neither less than equal to 10 nor greater than equal\
41 to 15";
42 }
43 }
44 }
45
46 $firstCase = new DeMorganOne();
47 $secondCase = new DeMorganOne();
48
49 $firstCase->notAandB(11, 14);
50 echo '<br>';
51 $firstCase->notAandB(1, 140);
52 echo '<br>';
53 $secondCase->notAORnotB(11, 14);
54 echo '<br>';
55 $secondCase->notAORnotB(1, 140);
// output
1 The number is neither less than equal to 10 nor greater than equal to 15
2 Addition of two numbers : 141
3 The number is neither less than equal to 10 nor greater than equal to 15
4 Addition of two numbers : 141
Challenge 2: Can you write a program where the semantics (meaningful program) plays a very vital role.
Clue: If we write a same program in two different languages, their syntax may be different but semantics is same.
Language used: Python 3.10.0
Solution to Challenge 2:
1 // code
2
3 # take three numbers and sort them in ascending order
4
5 print("Enter first number: ")
6 first = int(input())
7 print("Enter second number: ")
8 second = int(input())
9 print("Enter third number: ")
10 third = int(input())
11 outputOne = 0
12 outputTwo = 0
13 outputThree = 0
14
15 if((first <= second) and (second <= third)):
16 outputOne = first
17 outputTwo = second
18 outputThree = third
19 elif((first <= third) and (third <= second)):
20 outputOne = first
21 outputTwo = third
22 outputThree = second
23 elif((second <= first) and (first <= third)):
24 outputOne = second
25 outputTwo = first
26 outputThree = third
27 elif((second <= third) and (third <= first)):
28 outputOne = second
29 outputTwo = third
30 outputThree = first
31 elif((third <= first) and (first <= second)):
32 outputOne = third
33 outputTwo = first
34 outputThree = second
35 else:
36 outputOne = third
37 outputTwo = second
38 outputThree = first
39
40 print("The numbers in ascending order: " + str(outputOne) + ", "
41 + str(outputTwo) + ", and " + str(outputThree))
// output
1 Enter first number:
2 200
3 Enter second number:
4 1
5 Enter third number:
6 500
7 The numbers in ascending order: 1, 200, and 500
Challenge 3: The ‘while’ statement deals execution of any repetitive action better than any other statement. Can you write it using ‘natural language’ first? After that translate that into any programming language.
Language used: Python 3.10.0
Solution to Challenge 3:
The steps in Natural Language first:
1 while(the number of values processed is less than the number of finite set of number\
2 s)
3
4 we take input
5
6 the running total is adding more input numbers as long as the loop continues
7
8 after each cycle the number of values processed is increased by 1
9
10 the loop ends as the number of values processed is equal to the number of finite se\
11 t of numbers
12
13 now we have the grand total of all the numbers belonging to the finite set of numbers
14
15 to get the average we divide the total by the the number of finite set of numbers
16
17
18 // code
19 # we will compute average of six numbers by iteration using while loop
20
21 totalNumberToCompute = 6
22
23 # since number of iteration yet to be taken
24 numberOfIteration = 0
25 # we have not got the total addition of all numbers
26 total = 0.00
27 print("Please enter " + str(totalNumberToCompute) + " numbers : ")
28 print()
29
30 while(numberOfIteration < totalNumberToCompute):
31 value = 0.00
32 value = float(input())
33 total += value
34 numberOfIteration += 1
35
36 averageOfSixNumbers = 0.00
37 averageOfSixNumbers = total / numberOfIteration
38 print("The average of six numbers is : " + str(averageOfSixNumbers))
// output
1 Please enter 6 numbers :
2
3 1
4 2
5 3
6 4
7 5
8 6
9 The average of six numbers is : 3.5
Challenge 4: Greek mathematicians used Sieve of Eratosthenes to find prime numbers. Can you translate Sieve of Eratosthenes in any programming language where you need to prove that a prime number has exact two divisors. (An example: 11 has two divisors: 1 and 11.)
Language used: Java
First Solution to Challenge 4:
Steps or Algorithm in Natural Language:
1 take input of any natural number
2
3 process to find how many factors are there
4
5 count the number of factors
6
7 if the number of factors is equal to two, then the number is prime
8
9 if the number is greater than two, then the number is not prime
The program:
// code
1 package fun.sanjibsinha;
2
3 import java.util.*;
4 import java.math.*;
5 public class TryingToFindPrime {
6
7 private static Scanner sc;
8
9 public static void main(String[] args) {
10
11 int numOne, integerOne;
12 sc = new Scanner(System.in);
13
14 System.out.println("Please Enter any number to Find Factors: ");
15 numOne = sc.nextInt();
16
17 int controOne = 0;
18 for (integerOne = 1; integerOne <= Math.sqrt(numOne); integerOne++)
19 {
20 if (numOne % integerOne == 0) {
21 if (numOne / integerOne == integerOne){
22 controOne++;
23 } else {
24 controOne = controOne + 2;
25 }
26 }
27 }
28 if(controOne == 2){
29 System.out.println(numOne + " is prime.");
30 } else {
31 System.out.println(numOne + " is not prime.");
32 }
33 }
34 }
// output
1 Please Enter any number to Find Factors:
2 49
3 49 is not prime.
4
5 Please Enter any number to Find Factors:
6 47
7 47 is prime.
===========================
Second solution to Challenge 4
Language used: Python 3.10.0
The algorithm in Natural Language goes like the following:
1 1. First we need to create a list of consecutive integers from 2 through a certain n\
2 umber like 30, as we have seen in the above statement: (2, 3, 4, …, 30); we do this,\
3 because 2 is the smallest prime number
4
5 2. Therefore, we can initialize a variable like this: startingNUmber = 2
6
7 3. Now, we can specify the multiples of the ‘startingNUmber’ by counting in incremen\
8 ts of ‘startingNUmber’ from (2 * startingNUmber) to 30, and mark them in the list, \
9 like this:
10 (2 * startingNUmber), (3 * startingNUmber), (4 * startingNUmber), and so on.
11
12 4. It is not to be mentioned that multiples of 2 will never be the primes, because t\
13 he number of factors becomes greater than 2.
14
15 5. Next, we will find the first number that is greater than the ‘startingNUmber’; if\
16 there is no such number, then we stop. Otherwise, let ‘startingNUmber’ equal the ne\
17 w number, which is the next prime and repeat from the step 3.
18
19 6. When the algorithm ends, the numbers not marked in the list below 30, are all pri\
20 mes.
The program:
// code
1 # Sieve Of Eratosthenes
2
3 def SieveOfEratosthenes(rangeOfNumbers):
4 # let us create a boolean array "primeArray[...]" that takes a range of any numb\
5 ers
6 # next we initialize the array with the entries as true
7 # now if primeArray[anyNUmber] is false if it is not prime, else the number is p\
8 rime
9 # the startingNumber is 2, because 1 is not prime
10 primeArray = [True for anyNumber in range(rangeOfNumbers + 1)]
11 # we have added 1 with the rangeOfNumbers, so that the endNumber is included
12 startingNUmber = 2
13 while (startingNUmber * startingNUmber <= rangeOfNumbers):
14 # logically if primeArray[startingNumber] is not changed, then it is a prime
15 # in fact, 2 is prime
16 if (primeArray[startingNUmber] == True):
17 # all multiples of startingNumber is not prime
18 # the factors of the multiples are greater than 2
19 for anyNumber in range(startingNUmber * 2, rangeOfNumbers + 1, startingN\
20 Umber):
21 # in such cases, those numbers are not prime
22 primeArray[anyNumber] = False
23 startingNUmber += 1
24 primeArray[0] = False
25 primeArray[1] = False
26 # now we can print all prime numbers belonging to that range of numbers
27 for startingNUmber in range(rangeOfNumbers + 1):
28 if primeArray[startingNUmber]:
29 print(startingNUmber)
30
31 SieveOfEratosthenes(20)
// output: all the prime numbers below 20.
1 2
2 3
3 5
4 7
5 11
6 13
7 17
8 19
Challenge 5: As the value of ‘input’ or ‘n’ increases, the ‘Time Complexity’ varies. Prove it using any programming language.
Solution to Challenge 5:
Language used: C
// code
1 #include<stdio.h>
2
3 void quicksortInOneFunction(int arrayOfNumbers[25], int firstIndex, int lastIndex){
4 int firstStorage, secondStorage, pivotIndex, temporaryStorage;
5 if(firstIndex < lastIndex){
6 pivotIndex = firstIndex;
7 firstStorage = firstIndex;
8 secondStorage = lastIndex;
9 while(firstStorage < secondStorage){
10 while(arrayOfNumbers[firstStorage] <= arrayOfNumbers[pivotIndex]
11 && firstStorage < lastIndex)
12 firstStorage++;
13 while(arrayOfNumbers[secondStorage] > arrayOfNumbers[pivotIndex])
14 secondStorage--;
15 if(firstStorage < secondStorage){
16 temporaryStorage = arrayOfNumbers[firstStorage];
17 arrayOfNumbers[firstStorage] = arrayOfNumbers[secondStorage];
18 arrayOfNumbers[secondStorage] = temporaryStorage;
19 }
20 }
21 temporaryStorage = arrayOfNumbers[pivotIndex];
22 arrayOfNumbers[pivotIndex] = arrayOfNumbers[secondStorage];
23 arrayOfNumbers[secondStorage] = temporaryStorage;
24 quicksortInOneFunction(arrayOfNumbers, firstIndex, secondStorage - 1);
25 quicksortInOneFunction(arrayOfNumbers, secondStorage + 1, lastIndex);
26 }
27 }
28
29 int main(){
30 int initialNumber, countingLimit, collectionOfNumber[6];
31 printf("How many integers you want for for quick sorting?"
32 " (Maximum value you can enter: 6): ");
33 scanf("%d", &countingLimit);
34 printf("Enter %d elements: ", countingLimit);
35 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
36 scanf("%d", &collectionOfNumber[initialNumber]);
37 quicksortInOneFunction(collectionOfNumber, 0, countingLimit - 1);
38 printf("The Sorted Order is: ");
39 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
40 printf(" %d", collectionOfNumber[initialNumber]);
41 return 0;
42 }
First we will take a look at the output, that will explain why we need to change this code a little bit to get it done perfectly.
1 // output
2
3 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 6
4 Enter 6 elements:
5 478
6 2
7 0
8 365894
9 25478
10 12
11 The Sorted Order is: 0 2 12 478 25478 365894
12 RUN FINISHED; exit value 0; real time: 16s; user: 0ms; system: 0ms
As the ‘inputs’ increase, it breaks the code as the time complexity varies. We cannot enter more than 6 values. However, we can solve this problem the follwoing way.
Language used: C
// code
1 #include<stdio.h>
2
3 void quicksortInOneFunction(int arrayOfNumbers[25], int firstIndex, int lastIndex){
4 int firstStorage, secondStorage, pivotIndex, temporaryStorage;
5 if(firstIndex < lastIndex){
6 pivotIndex = firstIndex;
7 firstStorage = firstIndex;
8 secondStorage = lastIndex;
9 while(firstStorage < secondStorage){
10 while(arrayOfNumbers[firstStorage] <= arrayOfNumbers[pivotIndex]
11 && firstStorage < lastIndex)
12 firstStorage++;
13 while(arrayOfNumbers[secondStorage] > arrayOfNumbers[pivotIndex])
14 secondStorage--;
15 if(firstStorage < secondStorage){
16 temporaryStorage = arrayOfNumbers[firstStorage];
17 arrayOfNumbers[firstStorage] = arrayOfNumbers[secondStorage];
18 arrayOfNumbers[secondStorage] = temporaryStorage;
19 }
20 }
21 temporaryStorage = arrayOfNumbers[pivotIndex];
22 arrayOfNumbers[pivotIndex] = arrayOfNumbers[secondStorage];
23 arrayOfNumbers[secondStorage] = temporaryStorage;
24 quicksortInOneFunction(arrayOfNumbers, firstIndex, secondStorage - 1);
25 quicksortInOneFunction(arrayOfNumbers, secondStorage + 1, lastIndex);
26 }
27 }
28
29 int main(){
30 int initialNumber, countingLimit, collectionOfNumber[6];
31 printf("How many integers you want for for quick sorting?"
32 " (Maximum value you can enter: 6): ");
33 scanf("%d", &countingLimit);
34
35 if(countingLimit <= 6){
36 printf("Enter %d elements: ", countingLimit);
37 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
38 scanf("%d", &collectionOfNumber[initialNumber]);
39 quicksortInOneFunction(collectionOfNumber, 0, countingLimit - 1);
40 printf("The Sorted Order is: ");
41 for(initialNumber = 0; initialNumber < countingLimit; initialNumber++)
42 printf(" %d", collectionOfNumber[initialNumber]);
43 } else {
44 printf("You crossed the maximum value limit, try again!");
45 }
46
47 return 0;
48 }
// output
1 How many integers you want for for quick sorting? (Maximum value you can enter: 6): 8
2 You crossed the maximum value limit, try again!
3 RUN FINISHED; exit value 0; real time: 3s; user: 0ms; system: 0ms
4. Data Structures in different Programming languages
The core concepts of data structures in different programming languages are almost same, although the implementation varies syntactically.
Moreover, algorithm or sequence of instructions is deeply associated with the core concepts of data structures. We will see to that in a minute. Before that we need to know a few elementary discrete mathematical algebraic concepts, which are also associated with data structures.
Before cutting into the core concepts of data structures, theoretically we need to understand one key concept. The concepts of data structures in various programming language inherit its roots largely from discrete mathematical algebraic conceptions that are known as date set.
What is data set? A collection of integers.
We can write it like this:
1 {14, 1, 58, 3, 85} or {1, 2, 2, 4, 5, 6}
We started storing data and started doing operations on them much before any programming languages’ forays into data structures. In that sense, we have implemented those old concepts of algebraic data set quite recently into programming languages.
We are, rather forced to do that. The volume of data is increasing faster than ever. Effective means of algorithm to sort those big data is getting more attention than ever.
In programming languages, we had thought of ‘array’ first; then, we found ‘array’ was not enough. Therefore, we implemented conceptions like Stack, Queue, Linked List, Trees, Hashing, etc. Data structures are now used in in every programming language to to store data in an organized and efficient manner. And to do that, we need efficient algorithm. That is the basic concept. Moreover, discrete mathematical algebraic data set, algorithm and data structures are twisted and entwined into a meaningful entity.
Let us clear some algebraic concepts about data set. After that, slowly we will enter into the world of complex data structures.
Stay tuned and read on.
Mean, Median and Mode
You have probably noticed that in discrete mathematics, there are always two conceptions go together. One is ‘order of operation’, and the other is ‘distributive property’.
Consider some factors like this:
1 x = 3 * (4 + 6)
2 x = 3 * 10
3 x = 30
Now, we can rearrange the same factors like this:
1 x = 3 * (4 + 6)
2 x = 3*4 + 3*6
3 x = 12 + 18
4 x = 30
Therefore, order of operations and distributive property works pretty well with addition and subtraction. However, this will not work with multiplication and division. Just try it.
Any algebraic operation is nothing but a kind of algorithm. In the above case, our algorithm fails for two separate cases. Our algorithm works very well with addition and subtraction; but, it does not work with multiplication and division.
The same thing might happen for a data set. In a collection of numbers, we might try to apply the same algorithm. Consider a data set like this:
1 {14, 5, {78, 1, 56}, 8, 96, 0, 6}
A data set inside a data set. We cannot apply our algorithm here as well. We need to use of ‘order of operation’ rule to get the addition done inside the sub-data set first.
Now, we understand one thing, what we can do with discrete integers, we cannot always do with a collection of integers. We need to invent some different algorithm.
In any algebraic data set, there is always an average of the collection. Consider this data set:
1 {6, 2, 3, 8, 1}
The average of this data set is : (6 + 2 + 3 + 8 + 1) / 5, or 20.
This is also called ‘Mean’ of a data set. In mathematics there is other ‘mean’ as well. The geometric mean, we may have heard of that.
The word ‘mean’ means many things in our natural language also; but, in algebraic data set, it means the average. No lexical disambiguation, please.
On the other hand, in any algebraic data set, the Median represents the middle value of the data set. In any collection of integers, which is odd in numbers, finding the Median is quite easy.
In the above data set, 3 is the Median or middle value. But it is not true when the number of integers in a collection is even.
Consider the following data set:
1 {1, 2, 3, 4}
Finding the Mean is quite easy. It is not related to the odd or even numbers of the collection. But, in the above data set, finding the Median is not that easy. To find the Median we need to find the middle value of 2 and 3; because they are in the middle.
The middle value of 2 and 3 is 2.5. Therefore, that is the Median of the above data set.
Another important thing of a data set is the Mode. In some data sets, one value or more than one values most often appear. Consider this data set:
1 {1, 56, 7, 89, 7, 3, 56, 2, 1, 7, 8, 9, 3, 45, 3, 96, 3, 78, 5, 3}
In the above data set, there are more than one values that repeatedly appear. Right? We can see that 1 and 56 repeatedly appear two times, 7 appears three times; moreover, the integer 3 repeats five times. Therefore, the most often appeared integer is 3. It is the Mode of the data set.
Reading so far, we may ask ourselves, why we need to know this before studying data structures?
Well, there is an answer.
The sum of a collection of numbers divided by the count of numbers in the collection means the arithmetic mean; it is true for mathematics and statistics, as well. So the ‘Mean’ of a data set is often referenced as ‘arithmetic mean’ for lexical disambiguation. As we have learned before there are ‘geometric mean’ or ‘harmonic mean’.
As far as programming language is concerned, sometimes we need to find out the arithmetic average income of a nation’s population, which is known as per capita income.
Now, we can logically guess that by using ‘Mean’ of a data set, we cannot represent the central tendencies of a data set. Consider a data set, where a people’s income is much, much greater than most people’s income. Theoretically, the nation’s per capita income shows a very good central tendencies, which is a false statement; in reality, in that country, 70 percent of people live under poverty line.
In such situation, the ‘Median’ may be a better description of central tendencies.
Why? Because, the ‘Median’ separates the higher half from the lower half of a data sample. For a data set, we have seen that it represents the middle value.
Whereas the ‘Mean’ can be skewed and twisted to give a false representation of central tendencies, here is the basic advantage of the ‘Mean’. It may give a better idea of a typical central tendencies. It cannot be skewed using a small portions of extremely large values, compared to a large portions of extremely small values. If only more than half the data are represented by false, and extremely large values, the ‘Median’ will give an arbitrarily large or small result.
Array, the First Step to Data Structure
We know that an array is a sequential collection of elements. These elements are of same type. They are stored in memory sequentially. An element of an array can be obtained through its respective index. An array element in Java is treated as an object, that is not true in C.
As a definition, we can say that an array is a data structure that holds a similar type of elements. On the other hand, it can represent a large collection of algebraic data set. We can generate a random set of elements in an array like this:
1 //code 4.1
2 //Java
3 package fun.sanjibsinha.datastructures;
4
5 public class ManipulatingArray {
6
7 private int arrayOfRandomNumbers[] = new int[20];
8
9 private int sizeOfArray = 5;
10
11 public void getRandomElements(){
12 for (int i = 0; i <= sizeOfArray; i++){
13 arrayOfRandomNumbers[i] = (int)(Math.random()*121)+121;
14 System.out.println(arrayOfRandomNumbers[i]);
15 }
16 }
17
18 public static void main(String[] args) {
19 ManipulatingArray manArray = new ManipulatingArray();
20 manArray.getRandomElements();
21 }
22
23 }
The above code is a sample of code snippets that can generate a random data set of big integers. Here we have produced only five specimens.
1 // output of code 4.1
2
3 185
4 198
5 158
6 146
7 139
8 132
We have an idea of how we can manipulate data in a big way. It is just a very small sample.
We can search any value in the random output, like this:
1 // code 4.2
2 // Java
3
4 package fun.sanjibsinha.datastructures;
5
6 public class ManipulatingArray {
7
8 private int arrayOfRandomNumbers[] = new int[20];
9
10 private int sizeOfArray = 5;
11
12 public void getRandomElements(){
13 for (int i = 0; i <= sizeOfArray; i++){
14 arrayOfRandomNumbers[i] = (int)(Math.random()*121)+121;
15 System.out.println(arrayOfRandomNumbers[i]);
16 }
17 }
18
19 public boolean getValueInArray(int findTheValue){
20 boolean theValue = false;
21 for(int i = 0; i < sizeOfArray; i++){
22 if(arrayOfRandomNumbers[i] == findTheValue){
23 theValue = true;
24 }
25 }
26 return theValue;
27 }
28
29 public static void main(String[] args) {
30 ManipulatingArray manArray = new ManipulatingArray();
31 manArray.getRandomElements();
32 System.out.println("**********");
33 System.out.println(manArray.getValueInArray(121));
34 }
35 }
We are trying to find whether 121 belongs to the randomly generated array of integers. The answer will come out as ‘false’. You have probably noticed that we have used this line in our code while generating the random integers.
1 arrayOfRandomNumbers[i] = (int)(Math.random()*121)+121;
Because ‘Math.random()’ method produces ‘double’ data type,we have to cast it to a round figure by using ‘int’ data type. Each time you run the code, you will get the same output. If you change the value from 121 to a higher value,the output will be higher.
Therefore, the output is quite expected.
1 // output of code 4.2
2
3 136
4 227
5 157
6 143
7 233
8 195
9 **********
10 false
The element 121 does not belong to the randomly generated collection of integers.
As an object-oriented-programming language, Java treats this type of collection differently than C. In Java an array is a container object that holds a fixed number of values of a single type. Whenever we create an array, the length of the array is established. After creation, the length of an array is fixed.
In Java, whenever we want to create an array object, we write something like this:
1 private int arrayOfRandomNumbers[] = new int[20];
However, in C, this is different. According to some computer scientists, C stands between problem oriented high level languages like Fortran, Basic and Pascal, and the low level machine languages like Assembly language or Machine language.
Any C programs consists of one or more distinct units called ‘functions’.
In C, like in the above code, we declare array, this way:
1 // declaring array
2 int individualMarks[10];
Whatever be the language type, function based or object-oriented-programming based, the accessing of an array element is the same. This is done with ‘subscript’; all the array elements are numbered, starting with 0. In C,what is known as subscript, in Java the same is known as numerical index. In Java each item in an array is called an element. In C it is also known as ‘dimension’.
The Mean, Median and Mode of algebraic data set is widely used while we manipulate any array. Consider the following example where we have calculated the average marks of 10 students. The user is asked to give inputs and the program calculates the Mean of the data set.
1 // code 4.3
2 // C
3
4 /*
5 * an array is a collective name given to a group of similar quantities
6 * find average marks obtained by a class of 10 students
7 */
8
9 int main(int argc, char** argv) {
10
11 float averageNumber, sumOfNumbers = 0;
12
13 int indexNumber;
14
15 // declaring array
16 int individualMarks[10];
17
18 for(indexNumber = 0; indexNumber <= 9; indexNumber++){
19
20 printf("Enter marks: ");
21 // storing data in array
22 scanf("%d", &individualMarks[indexNumber]);
23
24 }
25
26 for(indexNumber = 0; indexNumber <= 9; indexNumber++){
27 sumOfNumbers = sumOfNumbers + individualMarks[indexNumber];
28 }
29
30 averageNumber = sumOfNumbers / 10;
31
32 printf("Average number = %f", averageNumber);
33
34
35 return 0;
36 }
Let us see the output of the above code.
1 // output of code 4.3
2
3 Enter marks: 35
4 Enter marks: 65
5 Enter marks: 98
6 Enter marks: 99
7 Enter marks: 48
8 Enter marks: 75
9 Enter marks: 67
10 Enter marks: 54
11 Enter marks: 89
12 Enter marks: 36
13 Average number = 66.599998
14 RUN FINISHED; exit value 0; real time: 33s; user: 0ms; system: 0ms
In the above code, this line is important:
1 printf("Average number = %f", averageNumber);
We have expected that the output would be a floating point value. In every language, we use all types of primitive data types to declare the type of the array.
In Java, we can declare arrays of many types, this way:
1 byte[] anArrayOfBytes;
2 int[] anArray;
3 short[] anArrayOfShorts;
4 long[] anArrayOfLongs;
5 float[] anArrayOfFloats;
6 double[] anArrayOfDoubles;
7 boolean[] anArrayOfBooleans;
8 char[] anArrayOfChars;
9 String[] anArrayOfStrings;
We can use the shortcut syntax to create and initialize an array, almost the same way.
In Java, we use the shortcut syntax this way:
1 int[] anArrayDeclaration = {
2 100, 200, 300,
3 400, 500, 600,
4 700, 800, 900, 1000
5 };
In C, we can use the shortcut syntax almost the same way. Sometimes, if the array is initialized where it is declared, we need not mention the dimension.
1 int numArray[] = {1, 21, 3, 45, 7};
Whatever language we use, the main advantage of array is it helps us to save the memory of the system. We can allocate memory dynamically; when the memory allocation is not dynamic, it stores the data in contiguous memory locations. This process makes the program faster than other data structures.
The idea of algebraic data set and the conceptions regarding the Mean, Median and Mode will also help us understanding the manipulations of complex arrays. Before going to that section, let us understand some simple features of arrays. To do that we will use Java language, as it is one of the easiest languages to learn.
Let us understand some Array features
In Java, array is an object. However, we also need the help of primitive data types to declare and initialize an array object.
As we have seen earlier, whenever we create an array object with the help of ‘new’ keyword, the memory is allocated.
Inside the comments in the following code snippet, we will see the relation between the numerical index and the element of an array.
1 // code 4.4
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5 /*
6 Introduction to array object
7 Primitive data types are not objects created from a class. They are special data typ\
8 es built into the language.
9 To build an array object we need to take help from primitive data types.
10 The only exception is String
11 What features will distinguish array from primitive data types?
12 Let us see to that problem
13 */
14
15 public class ArrayExampleOne {
16
17 public static void main(String[] args){
18 //an example of primitive data type
19 //a variable is a container that contains a value or a primitive data types
20 int myAge = 54;
21 System.out.println("An example of primitive data type : " + myAge);
22 //in case of array we declare and allocate memory with a new keyword
23 //the following array container holds a fixed number of value of data type i\
24 nt
25 //the length of the array is established
26 //here the length is 2, this container has 2 elements
27 int[] myBasket = new int[2];
28 //each item or element has a corresponding numerical index that starts with 0
29 myBasket[0] = 2;
30 myBasket[1] = 3;
31 //each element can be accessed by its corresponding numerical index
32 System.out.println("The first element of my basket : " + myBasket[0]);
33 System.out.println("The second element of my basket : " + myBasket[1]);
34 }
35
36 }
37
38 OUTPUT:
39 -------
40
41 An example of primitive data type : 54
42 The first element of my basket : 2
43 The second element of my basket : 3
In this section we will give the output along with the code snippet to understand how the program works.
In Java, while we declare an array we usually take help from the primitive data types. That sounds logical as we need to tell the compiler what type of array we are going to create. According to our declaration, the memory will be allocated. One single exception is the non-primitive data type ‘String’. The following example will show you how we can handle that.
1 // code 4.5
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5 /*
6 How to declare a variable to refer to an array
7 */
8
9 public class ArrayExampleTwo {
10
11 public static void main(String[] args){
12 //to declare and create an array of integer type
13 int[] studentClasses = new int[2];
14 //to declare an array of String, a non-primitive data type
15 String[] studentNames = new String[4];
16 //the brackets after the data type indicate it's an array
17 //an array has two parts : data type and name
18 //the data type also indicates what type of elements the array will contain
19 //the next line will give an error of incompatible type
20 /*
21 studentNames[0] = 12;
22 */
23 studentNames[0] = "John"; //this is OK with the compiler
24 System.out.println("The name of the student who has come out first : " + stu\
25 dentNames[0]);
26 }
27 }
28
29 OUTPUT
30 ------
31
32 The name of the student who has come out first : John
Read the comments carefully, we will learn many interesting things about an array. The proper initialization of an array varies from one programming language to another.
Java allows two types of initialization. However, one type is strongly discouraged by the official documentation.
Watch the next example, it will show you the proper way of initialization in Java.
1 // code 4.6
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5 /*
6 The proper initialization of an array
7 */
8
9 public class ArrayExampleThree {
10
11 public static void main(String[] args){
12 //we can also create and initialize an array like this
13 int schoolSections[] = new int[4];
14 schoolSections[0] = 1;
15 schoolSections[1] = 2;
16 schoolSections[2] = 3;
17 schoolSections[3] = 4;
18 System.out.println("We want section 1 : " + schoolSections[0]);
19 /*
20 However this above type of initialization is highly discouraged
21 */
22 int[] schoolSection = new int[4]; // it is OK
23
24 }
25 }
26
27
28 OUTPUT:
29 -------
30
31 We want section 1 : 1
We have compiled and run the code successfully with the help of improper initialization. However, the proper initialization is shown below:
1 int[] schoolSection = new int[4]; // it is OK
As long as we use the Java, we will keep using the proper initialization of array.
In C language, we have seen the shortcut syntax before, the next Java program has used the shortcut syntax to create and initialize the array.
1 // code 4.7
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5 /*
6 The shortcut syntax to create and initialize an array
7 */
8
9 public class ArrayExampleFour {
10
11 public static void main(String[] args){
12
13 String[] nameCollection = {
14 "John Smith", "Chicago", "good gunner."
15 };
16 System.out.println("He is " + nameCollection[0] + ", from " + nameCollection\
17 [1]
18 + ". And he is a " + nameCollection[2]);
19 }
20 }
21
22
23 OUTPUT
24 ------
25
26 He is John Smith, from Chicago. And he is a good gunner.
An array can contain another array, or sometimes, in some special cases, multiple arrays. We call them multidimensional array. The components of a multidimensional array are themselves arrays. The following example will show you how we can use multidimensional array.
1 // code 4.8
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6 /*
7 In multidimensional array components are themselves arrays
8 The rows can vary in length
9 */
10 public class ArrayExampleFive {
11
12 public static void main(String[] args){
13 //you may imagine it as columns and rows
14 String[][] nameCollections = {
15 {"Name", "Location", "Occupation"}, //[0][0] => Name
16 {"John Smith", "Chicago", "Gunner"}, //[1][0] => John ...
17 {"Ernest Hemingway", "Writer"}, //[2][0] => Ernest...
18 {"Don Juan", "Paris", "Artist"} //[3][0] => Don...
19 };
20 //the first column name represents the first index as [0][0], and moves on
21
22 System.out.println(nameCollections[0][0] + " : " + nameCollections[1][0]);
23 System.out.println(nameCollections[0][1] + " : " + nameCollections[1][1]);
24 System.out.println(nameCollections[0][2] + " : " + nameCollections[1][2]);
25 System.out.println("+++++++++++++++");
26 System.out.println(nameCollections[0][0] + " : " + nameCollections[2][0]);
27 System.out.println(nameCollections[0][2] + " : " + nameCollections[2][1]);
28 System.out.println("+++++++++++++++");
29 System.out.println(nameCollections[0][0] + " : " + nameCollections[3][0]);
30 System.out.println(nameCollections[0][2] + " : " + nameCollections[3][1]);
31 System.out.println(nameCollections[0][2] + " : " + nameCollections[3][2]);
32 }
33 }
34
35 OUTPUT:
36 -------
37
38 Name : John Smith
39 Location : Chicago
40 Occupation : Gunner
41 +++++++++++++++
42 Name : Ernest Hemingway
43 Occupation : Writer
44 +++++++++++++++
45 Name : Don Juan
46 Occupation : Paris
47 Occupation : Artist
When we work with multidimensional arrays, the built-in length property helps us to determine the size of an insider array component. In that case, the numerical index points to the built-in array like the following code snippet.
1 // code 4.9
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6 /*
7 The built-in length property helps us to determine the size of any array
8 */
9 public class ArrayExampleSix {
10
11 public static void main(String[] args){
12
13 String[][] nameCollections = {
14 {"Name", "Location", "Occupation"}, //[0][0] => Name
15 {"John Smith", "Chicago", "Gunner"}, //[1][0] => John ...
16 {"Ernest Hemingway", "Writer"}, //[2][0] => Ernest...
17 {"Don Juan", "Paris", "Artist"} //[3][0] => Don...
18 };
19 System.out.println("The length of the first array is : " + nameCollections.l\
20 ength);
21 System.out.println("The length of the index 2 of the first array is : " + na\
22 meCollections[2].length);
23 }
24 }
25
26
27 OUTPUT
28 ------
29
30 The length of the first array is : 4
31 The length of the index 2 of the first array is : 2
The arrays with numerical indexes 0 and 1 have length 3, while the array having numerical index 3, is of length 2. In case of multidimensional arrays, we can easily point them out and do any kind of operations.
Java allows us to copy all or a part of components of any array to another array. In the following example we can clearly see that the first ‘String’ type array has components that do not mean anything. We can rearrange the components of that array to another array, so that it becomes a meaningful sentence while we give an output.
1 // code 4.10
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6 /*
7 System class has a method called 'arraycopy()' that has five parameters
8 arraycopy(Object source, int source-position, Object destination, int destination po\
9 sition, int length)
10 */
11
12 import java.util.Arrays;
13
14 public class ArrayExampleSeven {
15
16 public static void main(String[] args){
17
18 String[] notAMeaningfulSentence = {"My ", "I ", "am ", "not ", "a ", "Robot"\
19 };
20 String[] aMeaningfulSentence = new String[5];
21 System.arraycopy(notAMeaningfulSentence, 1, aMeaningfulSentence, 0, 5);
22 System.out.println(aMeaningfulSentence[0]
23 + aMeaningfulSentence[1] + aMeaningfulSentence[2] + aMeaningfulSente\
24 nce[3]
25 + aMeaningfulSentence[4]);
26 }
27 }
28
29 OUTPUT
30 ------
31
32 I am not a Robot
While we give an output, we can do the same operation in a completely different way. In the above code we have used the numerical indices to get the individual elements. The following example has used ‘for’ loop to iterate through the same numerical indices and extract the string output.
1 // code 4.11
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6
7 public class ArrayExampleEight {
8
9 public static void main(String[] args){
10
11 String[] notAMeaningfulSentence = {"My ", "I ", "am ", "not ", "a ", "Robot"\
12 };
13 String[] aMeaningfulSentence = new String[5];
14 System.arraycopy(notAMeaningfulSentence, 1, aMeaningfulSentence, 0, 5);
15 for (int i = 0; i<=4; i++){
16 System.out.print(aMeaningfulSentence[i]);
17 }
18 }
19 }
20
21
22 OUTPUT
23 ------
24
25 I am not a Robot
One of the most common advantages of any array is we can iterate through that array and the process of iteration helps us to get all the components out of any type of array.
1 // code 4.12
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6 /*
7 We can perform some of the most common manipulations related to arrays
8 */
9
10 public class ArrayExampleNine {
11
12 public static void main(String[] args){
13
14 String[] notAMeaningfulSentence = {"My ", "I ", "am ", "not ", "a ", "Robot"\
15 };
16 String[] aMeaningfulSentence = java.util.Arrays.copyOfRange(notAMeaningfulSe\
17 ntence, 1, 6);
18 for (int i = 0; i <= (aMeaningfulSentence.length - 1); i++){
19 System.out.print(aMeaningfulSentence[i]);
20 }
21 }
22 }
23
24 OUTPUT
25 ------
26
27 I am not a Robot
So far we have learned one key concept of array. The elements of any array should belong to the same data type. On that principle, the multidimensional array also works.
Inside an array we have components that also contain one or more arrays. However, the components of multidimensional array should be of the same data type for one reason. We need to declare the data type well before the initialization.
Whatever be the nature of any array, it always works on the same principle: we get the element through the numerical index.
1 // code 4.13
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6
7 /*
8 How array works : index=>element
9 */
10
11 public class ArrayExampleTen {
12 public static void main (String[] args)
13 {
14 //declaring a certain type of array, we choose data type int
15 int[] ageCollection;
16
17 //the next step deals with allocating memory for elements, we choose 5
18 ageCollection = new int[5];
19
20 //the initialization process begins with the first element
21 for (int i = 0; i <= 4; i ++){
22 int j = 18;
23 j = j + i;
24 ageCollection[i] = j;
25 System.out.println("Element at index " + i + " => " + ageCollection[i]);
26 }
27 }
28 }
29
30
31 OUTPUT
32 ------
33 Element at index 0 => 18
34 Element at index 1 => 19
35 Element at index 2 => 20
36 Element at index 3 => 21
37 Element at index 4 => 22
Another important factor we should always keep in our mind. According to the depth of the multidimensional array,we can always use the nested ‘for’ loop. Consider the following example, where we have a two dimensional arrays.
According to its dimension, we have used one nested ‘for’ loop.
1 // code 4.14
2 // Java
3
4
5 package fun.sanjibsinha.arrayexamples;
6
7 /*
8 Multidimensional array using nested for loop
9 */
10
11 public class ArrayExampleEleven {
12
13 public static void main(String[] args){
14
15 int[][] myArray = {
16 {1, 2, 3},
17 {4, 5, 6},
18 {7, 8, 9}
19 };
20
21 for (int i = 0; i < 3; i++){
22 System.out.print(i + " => ");
23 for (int j = 0; j < 3; j++){
24 System.out.print(myArray[i][j] + " ");
25 }
26 System.out.println();
27 }
28
29 }
30 }
31
32
33 OUTPUT
34 ------
35
36 0 => 1 2 3
37 1 => 4 5 6
38 2 => 7 8 9
In Java, we have many built-in array methods. We can import those class methods and use them to manipulate any type of arrays.
1 // code 4.15
2 // Java
3
4 package fun.sanjibsinha;
5
6 import java.util.Arrays;
7
8 /*
9 Testing a few built-in array methods
10 */
11 public class Array12 {
12
13 public static void main(String[] args){
14 //array declaration
15 int[] myNumber = new int[5];
16 //now we need to add elements
17 myNumber[0] = 50;
18 myNumber[1] = 60;
19 myNumber[2] = 70;
20 //etc
21 int[] anotherNumber = {1, 2, 3};
22 //we can print any array value this way
23 System.out.println(Arrays.toString(myNumber));
24 System.out.println(Arrays.toString(anotherNumber));
25 }
26 }
27
28 OUTPUT
29 ------
30 [50, 60, 70, 0, 0]
31 [1, 2, 3]
In Java, an array object is created by using a ‘new’ keyword; it is needless to say that each array object creates a reference value along with it. We can easily get that reference value just by printing it out. The next code snippet shows us the same example.
1 // code 4.16
2 // Java
3
4 package fun.sanjibsinha;
5 /*
6 There are few basic rules we should remember about an array
7 */
8
9 public class A13 {
10
11 public static void main(String[] args){
12 //array declaration
13 int[] myNumber = new int[5];
14 //now we need to add elements
15 myNumber[0] = 50;
16 myNumber[1] = 60;
17 myNumber[2] = 70;
18 //etc
19 int[] anotherNumber = {1, 2, 3};
20 //printing the value of an array like this
21 //gives us reference value : [I@5ba23b66
22 System.out.println(myNumber);
23 //we can print out the individual value of element by index
24 System.out.println(myNumber[0] + " => " + anotherNumber[0]);
25 //we can also use for loop
26 for (int i = 0; i <= 2; i++){
27 System.out.println(myNumber[i]);
28 }
29 }
30 }
31
32 OUTPUT
33 ------
34
35 [I@5ba23b66
36 50 => 1
37 50
38 60
39 70
We can check whether an array has a certain value or not. We can create our own method, or we can use the built-in methods like the following code snippet.
1 // code 4.17
2 // Java
3
4 package fun.sanjibsinha;
5
6 import java.util.Arrays;
7
8 /*
9 We can check if any array has a certain value
10 */
11 public class A14 {
12
13 public static void main(String[] args){
14 //array declaration
15 int[] myNumber = new int[3];
16 //now we need to add elements
17 myNumber[0] = 50;
18 myNumber[1] = 60;
19 myNumber[2] = 70;
20 //etc
21 int[] anotherNumber = {1, 2, 3};
22 String[] nameColection = {"John", "Bob", "Mary"};
23
24 System.out.println("Does array nameCollection contains this element? "
25 + Arrays.asList(nameColection).contains(2));
26 System.out.println("Does array nameCollection contains this element? "
27 + Arrays.asList(nameColection).contains("John"));
28
29 }
30 }
31
32
33 OUTPUT
34 ------
35 Does array nameCollection contains this element? false
36 Does array nameCollection contains this element? true
When we pass an array as a parameter of a method, it adds a lot of flexibility in our code. It also reduces the excess code baggage. Manipulations of array by passing it as a parameter lets us do many types of operations.
1 // code 4.18
2 // Java
3
4 package fun.sanjibsinha;
5 /*
6 We can pass array as parameter and we can manipulate that feature in many ways
7 In this problem we have solved how to add a collection of numbers
8 */
9
10 import java.util.*;
11
12 import java.util.Arrays;
13
14 public class A15 {
15
16 public static void main(String[] args){
17
18 int[] anotherNumber = {10, 25, 300};
19 addingAColectionOfNUmbers(anotherNumber);
20 }
21 public static void addingAColectionOfNUmbers(int[] aCollectionOfNumbers){
22 int sum = 0;
23 for (int i = 0; i < aCollectionOfNumbers.length; i++){
24 sum += aCollectionOfNumbers[i];
25 }
26 System.out.println(sum);
27 }
28 }
29
30
31 OUTPUT
32 ------
33 335
Like any primitive data type, we can return any array object using a method. As always, we need to use the ‘new’ keyword.
1 // code 4.19
2 // Java
3
4 package fun.sanjibsinha;
5 /*
6 we can return any array value using a method
7 */
8
9 public class A16 {
10
11 public static void main(String args[]){
12 int newArray[] = returningArrayMethod();
13
14 for (int i = 0; i < newArray.length; i++){
15 System.out.print(newArray[i] + " ");
16 }
17 }
18
19 public static int[] returningArrayMethod(){
20 //returning any array from a method
21 return new int[] {111,222,3333, 456897};
22 }
23 }
24
25
26 OUTPUT
27 ------
28 111 222 3333 456897
We have given the output by accessing each numerical index.
Not only internal libraries, there are extremely useful external libraries too, Apache commons is such external libraries that help us to manipulate any array.
1 // code 4.20
2 // Java
3
4 package fun.sanjibsinha;
5 /*
6 In this problem we will see how we can manipulate different type of
7 Array methods using internal and external libraries
8 */
9
10 import org.apache.commons.lang3.ArrayUtils;
11
12 import java.lang.reflect.Array;
13 import java.util.Arrays;
14
15 public class A17 {
16
17 public static void main(String[] args){
18
19 int[] numberCollection = {1, 2};
20 //we can get a particular value through index
21 System.out.println(Array.get(numberCollection, 1));
22 //we can get the length of the array
23 System.out.println(Array.getLength(numberCollection));
24
25 /*
26 Using external libraries is required in some situations where we want to
27 manipulate array values. Please consult the related texts and associated lin\
28 ks
29 written in the book
30 */
31 //using apache commons lang3 external library
32 int[] cartOne = {1, 2, 3, 4};
33 System.out.println("The length of the first cart : " + cartOne.length);
34 int[] cartTwo = {5, 200, 36, 4, 78, 123};
35 System.out.println("The length of the second cart : " + cartTwo.length);
36 int[] addingCart = ArrayUtils.addAll(cartOne, cartTwo);
37 System.out.println("Combining two carts the length has changed : " + addingC\
38 art.length);
39 //we can also see the final output
40 System.out.println("The adding cart looks like this : " + Arrays.toString(ad\
41 dingCart));
42
43 }
44 }
45
46 OUTPUT
47 ------
48
49 2
50 2
51 The length of the first cart : 4
52 The length of the second cart : 6
53 Combining two carts the length has changed : 10
54 The adding cart looks like this : [1, 2, 3, 4, 5, 200, 36, 4, 78, 123]
With the help of these external libraries we can reverse any array components; in usual case, we need to write extra code to get the same result.
1 // code 4.21
2 // Java
3
4 package fun.sanjibsinha;
5 /*
6 Some more Array methods using external apache commons lang3
7 */
8
9 import org.apache.commons.lang3.ArrayUtils;
10
11 public class A18 {
12
13 public static void main(String[] args){
14 //we can reverse an Array
15 char[] myName = {'s', 'a', 'n', 'j', 'i', 'b'};
16 //now we can just add this characters to get my name
17 System.out.println("My name : " + new String(myName));
18 //let us reverse thsi character to see how my name looks in the mirror
19 ArrayUtils.reverse(myName);
20 System.out.println("My name on the mirror : " + new String(myName));
21 }
22 }
23
24 OUTPUT
25 ------
26
27 My name : sanjib
28 My name on the mirror : bijnas
The Apache commons array utility libraries have many other features, which help us to get other benefits; we can remove any array element using the external libraries.
1 // code 4.22
2 // Java
3
4
5 package fun.sanjibsinha;
6
7 /*
8 We can remove any element of an array using apache commons lang library
9 */
10
11 import org.apache.commons.lang3.ArrayUtils;
12
13 import java.util.Arrays;
14
15 public class A19 {
16
17 public static void main(String[] args){
18 //declaring an array
19 int[] myNumber = {1, 58, 23, 45, 47, 13, 35};
20 //the length of the array and the output
21 System.out.println("The length of the array : " + myNumber.length);
22 System.out.println("The array before removing any element : " + Arrays.toStr\
23 ing(myNumber));
24 //removing an element in the array
25 int[] newArrayOfMyNumber = ArrayUtils.remove(myNumber, 2);
26 System.out.println("The length of the new array after removel of index 2 : "\
27 + newArrayOfMyNumber.length);
28 System.out.println("The array after removing element 3, index 2 : "
29 + Arrays.toString(newArrayOfMyNumber));
30 System.out.println("The index 2 and element 3, that is number " + myNumber[2\
31 ] + " is missing in the new array.");
32 }
33 }
34
35
36 OUTPUT
37 ------
38
39 The length of the array : 7
40 The array before removing any element : [1, 58, 23, 45, 47, 13, 35]
41 The length of the new array after removel of index 2 : 6
42 The array after removing element 3, index 2 : [1, 58, 45, 47, 13, 35]
43 The index 2 and element 3, that is number 23 is missing in the new array.
In Java, the data type of any array may be user defined. Not only primitive or non-primitive data types, but we can also use the user defined data type like the following code snippet.
1 // code 4.23
2 // Java
3
4
5 package fun.sanjibsinha;
6
7 class Person{
8 int age;
9 }
10
11
12 public class A20 {
13
14 public static void main(String[] args){
15
16 Person onePerson = new Person();
17 onePerson.age = 10;
18 Person twoPerson = new Person();
19 twoPerson.age = 20;
20 Person threePerson = new Person();
21 threePerson.age = 30;
22 Person[] persons = new Person[3];
23 persons[0] = onePerson;
24 persons[1] = twoPerson;
25 persons[2] = threePerson;
26 System.out.println("The age of three Persons : " + persons[0].age +
27 ", " + persons[1].age + ", " + persons[2].age);
28
29 }
30
31 }
32
33
34 OUTPUT
35 -------
36
37 The age of three Persons : 10, 20, 30
We can create and initialize more user defined array objects to make our program more robust. Consider the next problem.
1 // code 4.24
2 // Java
3
4 package fun.sanjibsinha;
5
6 class Mobile{
7 int modelNumber;
8 String modelName;
9 public void displayModels(int model, String name){
10 this.modelName = name;
11 this.modelNumber = model;
12 System.out.println("The model number : " + model + ". The model name : " + \
13 name);
14 }
15
16 }
17
18 public class A21 {
19
20 public static void main(String[] args) {
21 //we are creating three mobile objects in heap
22 //three reference variables from stack point to the heap
23 Mobile sam = new Mobile();
24 Mobile red = new Mobile();
25 Mobile zen = new Mobile();
26 //an array of objects can be created just like any primitive data type
27 Mobile[] mobiles = {sam, red, zen};
28 for (int i = 0; i < mobiles.length; i ++){
29 //we want model number starts from 10
30 int j = 10;
31 j += i;
32 if(i == 0){
33 mobiles[i].displayModels(j, "Sam");
34 }
35 else if(i == 1){
36 mobiles[i].displayModels(j, "Red");
37 }
38 else {
39 mobiles[i].displayModels(j, "Zen");
40 }
41 }
42 }
43 }
44
45 OUTPUT
46 ------
47
48 The model number : 10. The model name : Sam
49 The model number : 11. The model name : Red
50 The model number : 12. The model name : Zen
Finally, we are going to conclude this section with a special Java feature. We can take out the elements directly from the array like the following code.
1 // code 4.25
2 // Java
3
4
5 package fun.sanjibsinha;
6
7 public class A22 {
8
9 public static void main(String[] args) {
10
11 int[] myNUmbers = {12, 18, 36, 6, 24};
12 //enhanced for loop
13 //it takes out the value directly from the array
14 for (int i : myNUmbers){
15 System.out.println(i);
16 }
17
18 }
19 }
20
21
22 OUTPUT
23 -------
24
25 12
26 18
27 36
28 6
29 24
In this section, we have learned many simple features of array using Java language. We can use the same algorithm for any other language as long as we use the iteration or numerical indices.
In the coming sections we will see how we can relate algebraic data set properties like the Mean, Median and Mode with arrays. We will also see how we can connect discrete mathematical conceptions like Set theory, Probability and programming conceptions arrays in our mind.
Let us start with Set theory and Probability.
Set Theory, Probability and Array
In discrete mathematics studying ‘Sets’ is mandatory. Have you ever thought why? It is because Set theory is only concerned about distinct numbers. Quite naturally it has widespread applications in Computer Science.
Literally we can translate every single property of Set theory into computer programming. And, yes, with the help of simple arrays. We don’t need complex data structures, algorithm, classes, or any collection hierarchy.
Set theory conceptions are distributed over a considerable amount in computer science as a whole. We will see that later, in detail, how Set theoretical conceptions are applied in Declarative programming language like SQL. With all types of set operations we can make declarative statements in any SQL query. You will find typical ‘union’,‘intersection’, ‘difference’, ‘complementary’, and many more.
Moreover, we can do the same thing in our array world, also.
A Set in discrete mathematics is a list of well defined collection of unique integers. Do you find any similarity with an Array? An array is also a well defined collection of similar quantities. It could be integers, any kind of decimal values, or even Strings, characters. The main difference is an array does not always contain unique items.
As a result we can manipulate arrays in some diverse ways, and that was intended when the conceptions of arrays had been incorporated in programming languages. An array allows duplicate values, and that is important when Probability comes into pictures. We will see to that in a minute.
We can say an Array is basically a Set with indexes. Both are data structures and both contain a list of items. In particular, both have similar types of operations that can be performed, such as Union, Intersection, etc.
Before going to connect them we need to have a clear conceptions about the differences. A Set does not allow duplicate items, but an Array does. A Set does not have any index attached with its items, but an Array does. In an Array we can take out a specific item and traverse the whole Array structure until it is found. In a Set, we cannot do that.
The major advantage of an Array is we can take out any value with the help of the index.
As a matter of fact, we can conclude that they have more similarities than differences. Therefore let us immerse briefly into some code snippets that will show how we can connect them in reality.
According to the Set theory, the Union occurs between two Sets and the output omits the common value. Let us do the same with a PHP code.
1 // code 4.26
2 // PHP
3
4 <?php
5
6 /*
7 * They have similarities and differences
8 * Set theory of Discrete mathematics and PHP has many similarities
9 * Both represent data sets
10 Both hold a list of similar elements
11 We can operate on both by performing union, intersection etc
12 */
13
14 // consider two separate arrays
15
16 $arrayOne = [11, 12, 13];
17 $arrayTwo = [11, 12, 13, 14, 15];
18
19 // consider one universal array that contain elements of both arrays
20
21 $universalArray = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
22
23 /*
24 * According to the set theory, the union occurs as
25 * $arrayOne + $arrayTwo
26 * the output omits the common value
27 * we can do the same using PHP
28 */
29
30 $unionOfTwoArrays = $arrayOne + $arrayTwo;
31
32 echo "Union of two arrays : [" . implode(", ", $unionOfTwoArrays) . "]<br>";
33
34 /*
35 * We can do the difference operation using the same technique
36 * we can use the PHP default methods
37 */
38
39 $differenceOfTwoArrays = array_diff($arrayTwo, $arrayOne);
40
41 echo "Difference of two arrays : [" . implode(", ", $differenceOfTwoArrays) . "]<br>\
42 ";
43
44
45 /*
46 * We can do the intersection operation using the same technique
47 * it keeps the same elements
48 * we can use the PHP default methods
49 */
50
51 $intersectionOfTwoArrays = array_intersect($arrayOne, $arrayTwo);
52
53 echo "Intersection of two arrays : [" . implode(", ", $intersectionOfTwoArrays) . "]\
54 <br>";
55
56 /*
57 * We can do the complement operation on two arrays
58 * we can use the PHP default methods
59 */
60
61 $arrayOneComplement = array_diff($universalArray, $arrayOne);
62
63 echo "Complement of arrayOne : [" . implode(", ", $arrayOneComplement) . "]<br>";
64
65 $arrayTwoComplement = array_diff($universalArray, $arrayTwo);
66
67 echo "Complement of arrayTwo : [" . implode(", ", $arrayTwoComplement) . "]<br>";
In the above code, we have done most common Set operations,such as Union, Differences, Intersection, and Complement.
1 // output of code 4.26
2
3 Union of two arrays : [11, 12, 13, 14, 15]
4 Difference of two arrays : [14, 15]
5 Intersection of two arrays : [11, 12, 13]
6 Complement of arrayOne : [14, 15, 16, 17, 18, 19, 20]
7 Complement of arrayTwo : [16, 17, 18, 19, 20]
We can use the language of set theory to define nearly all mathematical objects, as well as every kind of possible programming operations. The major reason behind that is the Set theory deals with a diverse collection of topics, ranging from the structure of the real number line to the study of the consistency of large cardinals. We will discuss those topics, in great detail, later.
After a brief display of Set theory in programming, we will switch over to Probability, another important concept of discrete mathematical operations. Just like the Set theoretical conceptions, the Probability concepts are also applied diversely into computer science and programming world.
Before dipping our toes into code, let us discuss what exactly probability means. Consider heads and tails. If you throw it up, there is 50-50 probability to either get heads or tails. But the equation changes when you throw a ‘dice’ or ‘die’ up in the air.
What is the probability of getting a ‘2’ when you throw a dice? The favorable outcome is 1, as the dice has one ‘2’. On the contrary, the possible outcome is 6. Because there are 6 sides in a dice. Although a dice is a three dimensional object, we can write the 6 elements in a data set. To speak more frankly, we can create and initialize an array with the 6 integers and calculate all the probabilities.
The Probability theory is not limited to dice only, we can explore a range of huge data and calculate all types of probabilities.
Let us check the next code snippet.
1 // code 4.27
2 // Python 3.6
3
4 # we are to find the probability of finding an element in an array
5 # it depends on two factors
6
7 # Probability = number of favorable outcome / number of possible outcomes
8 # number of possible outcomes is the length of the array
9 # number of favourable outcome is the total number of the element in the list
10 # Probability = total number of the element present / size or length of the array.
11
12 # define the function to find the probability
13 def findTheProbability(theArray, theLenghtOfArray, theElement):
14 count = theArray.count(theElement)
15
16 # find probability up to 4 decimal places
17 return round(count / theLenghtOfArray, 4)
18
19 theArrayVariable = [22, 22, 22, 22, 22, 22, 22]
20 theElementToFind = 22
21 theLenghtOfTheArrayVariable = len(theArrayVariable)
22
23 print(findTheProbability(theArrayVariable, theLenghtOfTheArrayVariable, theElementTo\
24 Find))
In the above code, you can guess what will be the outcome. Since every element of the array is the same, the probability is 100 percent.
1 // output of code 4.27
2
3 1.0
The Probability goes down extensively with the reduction in the numbers. When the total number of a particular integer reduces, and the number of other integers increases, the Probability plunges. Watch the next code snippet, where we have used the same code as above, but we have changed the elements of the array.
1 // code 4.28
2 // python 3.6
3
4 # we are to find the probability of finding an element in an array
5 # it depends on two factors
6
7 # Probability = number of favorable outcome / number of possible outcomes
8 # number of possible outcomes is the length of the array
9 # number of favourable outcome is the total number of the element in the list
10 # Probability = total number of the element present / size or length of the array.
11
12 # define the function to find the probability
13 def findTheProbability(theArray, theLenghtOfArray, theElement):
14 count = theArray.count(theElement)
15
16 # find probability up to 4 decimal places
17 return round(count / theLenghtOfArray, 4)
18
19 theArrayVariable = [45, 22, 62, 72, 82, 92, 122]
20 theElementToFind = 22
21 theLenghtOfTheArrayVariable = len(theArrayVariable)
22
23 print(findTheProbability(theArrayVariable, theLenghtOfTheArrayVariable, theElementTo\
24 Find))
Look at the output, the Probability dips drastically compared to the before code snippets.
1 // output of code 4.28
2 0.1429
While calculating the Probability, we have used the Python default class methods that makes our life simpler to calculate the Probability. In other languages, we are not that lucky. Take Java for instance, we need to build some function using control constructs to calculate the same Probability.
1 // code 4.29
2 // Java
3
4 package fun.sanjibsinha.setprobability;
5
6 import java.util.Arrays;
7 public class ProbabilityAndArray {
8
9 static float totalNumberOfTheElement;
10 static float theProbability;
11
12 static float findTheProbableElementInArray(int[] theArray, int theLengthOfArray,\
13 int theElement){
14
15 for(int i = 0; i < theLengthOfArray; i ++){
16 if(theArray[i] == theElement){
17 totalNumberOfTheElement++;
18 }
19 }
20 theProbability = totalNumberOfTheElement / theLengthOfArray;
21 return theProbability;
22
23 }
24
25 public static void main(String[] args) {
26 int[] theArray = {25, 25, 25, 25, 25, 25};
27 int theElement = 25;
28 int lengthOfArray = theArray.length;
29 theProbability = findTheProbableElementInArray(theArray, lengthOfArray, theE\
30 lement);
31 System.out.println(theProbability);
32 }
33
34 }
Yet, that is interesting side of programming; we can explore many possibilities. We can find solutions to given set of a problem in many different ways.
In the above code, you can guess the outcome.
1 // output of code 4.29
2 1.0
Let us change the above code a little bit by rearranging the array elements, we will get a different outcome.
1 // code 4.30
2 // Java
3
4 package fun.sanjibsinha.setprobability;
5
6 import java.util.Arrays;
7 public class ProbabilityAndArray {
8
9 static float totalNumberOfTheElement;
10 static float theProbability;
11
12 static float findTheProbableElementInArray(int[] theArray, int theLengthOfArray,\
13 int theElement){
14
15 for(int i = 0; i < theLengthOfArray; i ++){
16 if(theArray[i] == theElement){
17 totalNumberOfTheElement++;
18 }
19 }
20 theProbability = totalNumberOfTheElement / theLengthOfArray;
21 return theProbability;
22
23 }
24
25 public static void main(String[] args) {
26 int[] theArray = {255, 2523, 25, 725, 7825, 245};
27 int theElement = 25;
28 int lengthOfArray = theArray.length;
29 theProbability = findTheProbableElementInArray(theArray, lengthOfArray, theE\
30 lement);
31 System.out.println(theProbability);
32 }
33
34 }
The Probability plunges drastically.
1 // output of code 4.30
2 0.16666667
The same code semantically changes when we write it in PHP 7. We can use some default class methods and try some other tricks, as well.
1 // code 4.31
2 // PHP 7.3
3
4 <?php
5
6 /*
7 * how much probability is there to find an element in a given array
8 */
9
10 class ProbabilityClass {
11
12 public function countNumberOfValuesInArray($theArray, $matchTheElement){
13 $countNumbers = 0;
14 foreach ($theArray as $key => $value){
15 if ($value == $matchTheElement){
16 $countNumbers++;
17 }
18 }
19 return $countNumbers;
20 }
21
22 }
23
24 $theProbable = new ProbabilityClass();
25
26 $theDice = [1, 2, 3, 4, 5, 6];
27 $theElement = 2;
28 $theLength = sizeof($theDice);
29 $totalNumbersOfValues = $theProbable->countNumberOfValuesInArray($theDice, $theEleme\
30 nt);
31 $theProbability = (floatval($totalNumbersOfValues / $theLength));
32 echo "The probability is: " . $theProbability;
We have tried to calculate the Probability of outcomes using the example of a dice, theoretically we have discussed it earlier.
You can watch the outcome.
1 // output of code 4.31
2 The probability is: 0.16666666666667
Now, just for fun, we can play around the same algorithm using a more object-oriented-programming approach. We have tried to rewrite the above code in a different way to get the same result.
1 // code 4.32
2 // PHP 7.3
3
4 <?php
5
6 class Dice{
7
8 public $sidesOfDice = [1, 2, 3, 4, 5, 6];
9
10 // Probability = total number of the element present / size or length of the arr\
11 ay.
12 public function throwDice($sidesOfDice, $totalSides) {
13 $this->sidesOfDice = $sidesOfDice;
14 $lengthOfDice = sizeof($sidesOfDice);
15 $theProbability = $totalSides / $lengthOfDice;
16 return $theProbability;
17 }
18 }
19
20 class TotalSides{
21
22 public function getSide($sidesOfDice, $theSide) {
23 $count = 0;
24 foreach ($sidesOfDice as $value) {
25 if($value == $theSide){
26 $count++;
27 }
28 }
29 return $count;
30 }
31 }
32
33 $numberOfSides = new TotalSides();
34 $theProbability = new Dice();
35 echo "The probability of getting 2 when you throw the dice is: " . $theProbability->\
36 throwDice($theProbability->sidesOfDice,
37 $numberOfSides->getSide($theProbability->sidesOfDice, 2));
The possibilities are endless and the Probability is the same.
1 // output of code 4.32
2 The probability of getting 2 when you throw the dice is: 0.16666666666667
We have seen some connections between discrete mathematical conceptions and programming algorithm. We will see more. In the next section we will explore the relation between the algebraic data set conceptions, such as the Mean, Median and Mode and complex array algorithm.
Skewed Mean, Maximized Median
The idea that National per Capita Income of a country can be manipulated, is not not new to us now. Because it is calculated on the basis of the Mean of a Set of income-inputs, one can skew it quite easily. Keeping that fact in mind, we always think that the Median is more trustworthy.
In one sense, it is true. In another, it is false.
We may think of a natural algorithm where we take income of 10 people and make a set out of it. Of those ten people,eight persons have income less than 5 dollar. But, the other two earn more than 150 dollar. The definition of a Mean of a Set says us that calculating the average of those ten inputs give us an idea of the National per Capita Income.
As a result, the average income of the country becomes nearly 45 dollar; and, we know that the truth has been crucified. Where 80 percent of people earn less than 5 dollar, it cannot be true that the average income of the citizens of that country could be nearly 45 dollar.
Theoretically, choosing the Median is more trustworthy, because the middle value comes around 4 dollar, which is more close to truth value.
Our question is how trustworthy is the Median? Can it not be skewed or manipulated at all?
In this section we will turn over the myths to find out the real truth.
Usually, in a Set of positive integers where the numbers are increasing in an ascending order, it comes out that the Mean and the Median stays close.
Consider a Set of unique and distinct positive integers, like the following one.
In the above Set of values, the Mean and the Median is almost same. In a simple Java program we can check that.
1 // code 4.33
2 // Java
3 // when the number of elements in the array is odd
4
5 package fun.sanjibsinha.arrayexamples;
6 import java.util.Arrays;
7
8 public class A23 {
9
10 static double mean;
11 static double median;
12
13 // get the mean
14 public static double getMean(int[] theArray, int num)
15 {
16 int sum = 0;
17 for (int i = 0; i < num; i++)
18 sum += theArray[i];
19
20 mean = (double)sum / (double)num;
21 return mean;
22 }
23
24 // get the median
25 public static double getMedian(int[] theArray, int num)
26 {
27 //we know that median varies due to the odd and even numbers
28 // let us sort the array first
29 Arrays.sort(theArray);
30 // next check for the even case
31 if (num % 2 != 0){
32 median = (double)theArray[(num / 2)];
33 return median;
34 } else {
35 // check for the odd case
36 median = (double)(theArray[(num - 1) / 2] + theArray[num / 2]) / 2.0;
37 return median;
38 }
39 }
40
41 public static void main(String[] args) {
42 int theArray[] = { 1, 3, 4, 2, 6, 5, 7 };
43 int num = theArray.length;
44 System.out.println("Mean = " + getMean(theArray, num));
45 System.out.println("Median = " + getMedian(theArray, num));
46 }
47 }
Running the code will give us this output:
1 // output of code 4.33
2 Mean = 4.0
3 Median = 4.0
In the above code, the given array was like the following:
1 int theArray[] = { 1, 3, 4, 2, 6, 5, 7 };
First, we have sorted that array in an ascending order; second, we have counted the array or the set of integers as odd. For that reason, the Mean and the Median has become a whole number, not a fraction.
If the number of the values, which a set contains, is even,the outcome would be in fraction.
We can check that in another Java program.
1 //code 4.34
2 // Java
3 // when the number of elements in the array is even
4
5 package fun.sanjibsinha.arrayexamples;
6 import java.util.Arrays;
7
8 public class A23 {
9
10 static double mean;
11 static double median;
12
13 // get the mean
14 public static double getMean(int[] theArray, int num)
15 {
16 int sum = 0;
17 for (int i = 0; i < num; i++)
18 sum += theArray[i];
19
20 mean = (double)sum / (double)num;
21 return mean;
22 }
23
24 // get the median
25 public static double getMedian(int[] theArray, int num)
26 {
27 //we know that median varies due to the odd and even numbers
28 // let us sort the array first
29 Arrays.sort(theArray);
30 // next check for the even case
31 if (num % 2 != 0){
32 median = (double)theArray[(num / 2)];
33 return median;
34 } else {
35 // check for the odd case
36 median = (double)(theArray[(num - 1) / 2] + theArray[num / 2]) / 2.0;
37 return median;
38 }
39 }
40
41 public static void main(String[] args) {
42 int theArray[] = { 1, 3, 4, 2, 6, 5};
43 int num = theArray.length;
44 System.out.println("Mean = " + getMean(theArray, num));
45 System.out.println("Median = " + getMedian(theArray, num));
46 }
47 }
The outcome is expected, as we have been told.
1 // output of code 4.34
2 Mean = 3.5
3 Median = 3.5
Now, we can conclude one truth value from the above observation. If the values belonging to a Set is balanced and in an ascending order, there is no difference between the Mean and the Median.
Unfortunately, the reality bites and it does not come out like this.
Consider a situation where the majority of the values belonging to a Set is increasing in an ordered fashion up to a limit. After that, as it closes to the end, it suddenly behaves in an unordered fashion; the last two numbers are fairly bigger than the rest of the numbers. What will happen?
There will be a huge difference between the Mean and the Median.
In the beginning of this section, we were discussing about the nation’s per capita income. We were told that we could not depend on the Mean. Right? We were also told that the Median is more trustworthy, in such cases.
True.
The next Java program will show you the same example that we were told in the beginning of this section.
1 //code 4.35
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class A23 {
9
10 static double mean;
11 static double median;
12
13 // get the mean
14 public static double getMean(int[] theArray, int num)
15 {
16 int sum = 0;
17 for (int i = 0; i < num; i++)
18 sum += theArray[i];
19
20 mean = (double)sum / (double)num;
21 return mean;
22 }
23
24 // get the median
25 public static double getMedian(int[] theArray, int num)
26 {
27 //we know that median varies due to the odd and even numbers
28 // let us sort the array first
29 Arrays.sort(theArray);
30 if (num % 2 != 0){
31 median = (double)theArray[(num / 2)];
32 return median;
33 } else {
34 median = (double)(theArray[(num - 1) / 2] + theArray[num / 2]) / 2.0;
35 return median;
36 }
37 }
38
39 public static void main(String[] args) {
40 int theArray[] = { 1, 3, 4, 2, 5, 4, 3, 5, 155, 265};
41 int num = theArray.length;
42 System.out.println("Mean or National Per Capita Income = " + getMean(theArra\
43 y, num));
44 System.out.println("Median = " + getMedian(theArray, num));
45 // the mean or national per capita income is skewed and shows us a wrong imp\
46 ression
47 // about a nation's per capita income, or average citizen's income
48 // here median is more accurate, as 80% of people earn less than or equal to\
49 5 dollar
50 // where the result shows 44.7 dollar
51 }
52 }
Watch the outcome, you will be amazed to find how different they are – the Mean and the Median. From this experience, we will tend to believe that we can have our confidence or faith in the Median.
1 // output of code 4.35
2 Mean = 44.7
3 Median = 4.0
In a country where 80 percent of people have less than or equal to 5 dollars income, calculating the nation’s per capita income using the Median is more trustworthy.
At least the above program tells us so, isn’t it?
To believe this as ‘truth’ or a ‘proof of a concept’, we need to cut into the Median. This guy ‘Median’ is not an easy guy. Apparently this fellow seems to be normal and we can think, OK, the guy Median is trustworthy.
In the series of finding the true nature of the Median, we need to start with a simple program.
1 //code 4.36
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class FindMedian {
9
10 static double median;
11 // get the median
12 public static double getMedian(int[] theArray, int num){
13 //we know that median varies due to the odd and even numbers
14 // let us sort the array first
15 Arrays.sort(theArray);
16 // checking whether size is even
17 if (num % 2 == 0){
18 median = (double) (theArray[(num / 2) - 1] + theArray[num / 2]) / 2;
19 return median;
20 } else{
21 // else the size is odd
22 median = (double) theArray[num / 2];
23 return median;
24 }
25 }
26
27 public static void main(String[] args) {
28 int theArray[] = {3, 2, 3, 4, 2};
29 int num = theArray.length + 3;
30 System.out.println();
31 System.out.println("Median = " + getMedian(theArray, num));
32 // 2 2 3 3 4 -> 4 4 4
33 }
34 }
As an input array or set of values we have taken an unordered numbers. We know that the value of the Median varies according to the length of the array. If the length is even, we get a Median value. If it is odd, then the Median value changes.
Therefore, we have sorted our array and check it whether that array length is even or odd.
After the sorting has been done, the larger values go the right half section of the array. In the above array, the largest value was 4, so it goes to the far right corner of the array.
Now, in the runtime, we have increased the length of the array by 3 and we call the function to find the Median. What happens? Watch the outcome.
1 // output of code 4.36
2 Median = 3.5
The Median has become larger than the usual one. It has not increased in a large way, but, we have been able to skew the Median value.
Why?
If you run the code without increasing the length of the array, and calling the function to find the Median, the Median will come out as 3. On the contrary, the Median value has become 3.5.
We are nearing to a bitter truth, the Median is not trustworthy anymore. We can skew it as we have done the same thing to the Mean before.
One thing is certain, we cannot add any number to the length of the array. It depends on the original array length. If the array length is 5, then the number we add, should be less than 5. That is, up to 4 we can add. If it crosses the limit, the Median value goes out of range. Watch the next code:
1 //code 4.37
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class FindMedian {
9
10 static double median;
11 // get the median
12 public static double getMedian(int[] theArray, int num){
13 //we know that median varies due to the odd and even numbers
14 // let us sort the array first
15 Arrays.sort(theArray);
16 // checking whether size is even
17 if (num % 2 == 0){
18 median = (double) (theArray[(num / 2) - 1] + theArray[num / 2]) / 2;
19 return median;
20 } else{
21 // else the size is odd
22 median = (double) theArray[num / 2];
23 return median;
24 }
25 }
26
27 public static void main(String[] args) {
28 int theArray[] = {3, 2, 3, 4, 2};
29 int num = theArray.length + 5;
30 System.out.println();
31 System.out.println("Median = " + getMedian(theArray, num));
32 // 2 2 3 3 4 -> 4 4 4
33 // when 5 is added, the array length becomes 10
34 // 2 2 3 3 4 -> 4 4 4 4 4
35 }
36 }
Running the code gives us error like the following.
1 // output of code 4.37
2 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of \
3 bounds for length 5
4 at fun.sanjibsinha.arrayexamples.FindMedian.getMedian(FindMedian.java:15)
5 at fun.sanjibsinha.arrayexamples.FindMedian.main(FindMedian.java:28)
While we skew the Median value we should keep that simple mathematics in our mind.
In the next code, it is more obvious that maximizing the value of the Median is fairly simple. In usual scenario, in the following code, the Median should come out as 3; instead, we have skewed it and made it 4.
1 //code 4.38
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class MaximizingMedian {
9
10 static double median;
11
12 static double getMaxMedian(int[] theArray, int lengthOfArray, int addElement){
13 int size = lengthOfArray + addElement;
14 // sort the array first
15 Arrays.sort(theArray);
16
17 // checking whether size is even
18 if (size % 2 == 0){
19 median = (double) (theArray[(size / 2) - 1] + theArray[size / 2]) / 2;
20 return median;
21 } else{
22 // else the size is odd
23 median = theArray[size / 2];
24 return median;
25 }
26 }
27 public static void main(String[] args) {
28 int[] theArray = {3, 2, 3, 4, 2};
29 int lengthOfArray = theArray.length;
30 int addElement = 4;
31 System.out.print("We can add up to 4 elements to maximize the Median: "
32 + (int)getMaxMedian(theArray, lengthOfArray, addElement));
33 System.out.println();
34 }
35 }
To maximize the Median value we have introduced a function in the above code, where the function fellow takes three parameters; one of them is the variable ‘addElement’. We can declare how many integers we want to add with the length of the array to maximize the Median.
Here is the output:
1 // output of code 4.38
2 We can add up to 4 elements to maximize the Median: 4
We have mentioned that we can add up to 4 elements to maximize the Median, else, it will give us the same error we have faced before.
1 //code 4.39
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class MaximizingMedian {
9
10 static double median;
11
12 static double getMaxMedian(int[] theArray, int lengthOfArray, int addElement){
13 int size = lengthOfArray + addElement;
14 // sort the array first
15 Arrays.sort(theArray);
16
17 // checking whether size is even
18 if (size % 2 == 0){
19 median = (double) (theArray[(size / 2) - 1] + theArray[size / 2]) / 2;
20 return median;
21 } else{
22 // else the size is odd
23 median = theArray[size / 2];
24 return median;
25 }
26 }
27 public static void main(String[] args) {
28 int[] theArray = {3, 2, 3, 4, 2};
29 int lengthOfArray = theArray.length;
30 int addElement = 5;
31 System.out.print("We can add up to 4 elements to maximize the Median: "
32 + (int)getMaxMedian(theArray, lengthOfArray, addElement));
33 System.out.println();
34 }
35 }
We have added 5 elements and we have got the error, same as before.
1 // output of code 4.39
2 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of \
3 bounds for length 5
4 at fun.sanjibsinha.arrayexamples.MaximizingMedian.getMaxMedian(MaximizingMedian.\
5 java:16)
6 at fun.sanjibsinha.arrayexamples.MaximizingMedian.main(MaximizingMedian.java:29)
The only way to solve this problem is to increase the array elements. When the array length gets larger, we can add more elements to that length and skew the Median size.
The next code tells us the same story.
1 //code 4.40
2 // Java
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class MaximizingMedian {
9
10 static double median;
11
12 static double getMaxMedian(int[] theArray, int lengthOfArray, int addElement){
13 int size = lengthOfArray + addElement;
14 // sort the array first
15 Arrays.sort(theArray);
16
17 // checking whether size is even
18 if (size % 2 == 0){
19 median = (double) (theArray[(size / 2) - 1] + theArray[size / 2]) / 2;
20 return median;
21 } else{
22 // else the size is odd
23 median = theArray[size / 2];
24 return median;
25 }
26 }
27 public static void main(String[] args) {
28 int[] theArray = {3, 2, 3, 4, 2, 4, 5};
29 int lengthOfArray = theArray.length;
30 // we cannot add 5 elements when the number of the array elements is 5
31 // becuase it will give us error as it goes beyond index bound
32 // however we can tackle this problem by increasing the array elements
33 // now we can add up to 6 elements
34 int addElement = 6;
35 System.out.print("We can add up to 6 elements to maximize the Median: "
36 + (int)getMaxMedian(theArray, lengthOfArray, addElement));
37 System.out.println();
38 }
39 }
We have increased the array length adding more elements and we can maximize the Median value more than before.
1 // output of code 4.40
2 We can add up to 6 elements to maximize the Median: 5
The real fun begins if in an ordered collection of integers, we add only one value that is much bigger than the rest of the elements. Suddenly, the Median becomes much bigger than we have ever imagined.
Remember, with only one bigger value we can skew the Median, and make it much larger.
1 //code 4.41
2 // Python 3.6
3
4 package fun.sanjibsinha.arrayexamples;
5
6 import java.util.Arrays;
7
8 public class MaximizingMedian {
9
10 static double median;
11
12 static double getMaxMedian(int[] theArray, int lengthOfArray, int addElement){
13 int size = lengthOfArray + addElement;
14 // sort the array first
15 Arrays.sort(theArray);
16
17 // checking whether size is even
18 if (size % 2 == 0){
19 median = (double) (theArray[(size / 2) - 1] + theArray[size / 2]) / 2;
20 return median;
21 } else{
22 // else the size is odd
23 median = theArray[size / 2];
24 return median;
25 }
26 }
27 public static void main(String[] args) {
28 int[] theArray = {3, 2, 3, 4, 2, 4, 41};
29 int lengthOfArray = theArray.length;
30 // we cannot add 5 elements when the number of the array elements is 5
31 // becuase it will give us error as it goes beyond index bound
32 // however we can tackle this problem by increasing the array elements
33 // now we can add up to 6 elements
34 int addElement = 6;
35 System.out.print("We can add up to 6 elements to maximize the Median: "
36 + (int)getMaxMedian(theArray, lengthOfArray, addElement));
37 System.out.println();
38 }
39 }
In normal circumstance, in the above code, the Median should have been 4. You can find that Median value without any element to its length.
However, in reality, we have just added 6 elements to artificially increase the length and is able to make the Median 41.
1 // output of code 4.41
2 We can add up to 6 elements to maximize the Median: 41
We can conclude one bitter truth. The Median is not as trustworthy as had believed before.
Isn’t it?
In the next section we will cut into more complex algorithm involving array.
Complex Array Algorithm
Before starting this section, let us know that we are going to use a new programming language, called Dart. It is new compared to other programming languages, such as C, C++, PHP, Java, C#, and Python; we have used them before in this book. However, we are going to use Dart, for the first time.
Readers, who have not used Dart before, can stay calm. Dart is a language with which we can build mobile apps, as well as web applications; we can also do server side programming, etc. Dart has been created by Google, therefore, we can conclude that future of Dart is not bleak. Moreover, it has many similarities with Java, and in some cases with Python, so Java or Python programmers will adopt Dart very quickly.
We are going to use Dart to show another thing. What we can do with C, C++, PHP, Java, or Python, we can do with Dart. As a result, we will be introduced to a new general purpose language; that is a benefit.
We will also see one more thing. As any language gets updated and passes into a more better condition gradually, it starts incorporating more features. They are useful, as long as algorithm is concerned. The higher the language is,it comes up with more in-built features that shorten our algorithm, sequence of steps, make developer’s life easy.
We can code more in short time.
To reverse an array, we need to write around thirty lines of code, in usual cases. Dart can do that in one line; not only that, Dart can take that array and change it to any other data structure objects, like Set or Map.
Summing up, this book is not for learning Dart, so let us forget this part temporarily, and try to understand how we can understand various complex array algorithm with the help of Dart language. In between we will also use PHP for one example; just for a change.
It is true, array has many limitations; but, it has many advantages, too. That memory can be allocated dynamically in an array, is one of the biggest advantages. This feature of array saves the memory of the system. When memory allocation is not dynamic, the array stores the data in contiguous memory locations. What data type you are using? That determines the amount of storage required. Granted, manipulations of an array may become complex, if you think from the perspective of algorithm; but, an array requires memory space only for the values, the start address and its length. Compare it to Linked list; a Linked List always needs a pointer for every value that is stuck in. It eats up memory for every address, and acquires extra memory for the insertion of data. The Hash table also needs extra allocation of memory.
It is true that many types of data structures need more memory than array, even so, in some cases, we need data structures. We will see those features in the next section. The first program in Dart will help us to find the largest element in an array, after that it finds the second largest element, and, after that, it finds the third largest element. The algorithm does not stop there. It arranges those first, second and the third largest elements in descending order and gives the output.
1 //code 4.42
2 // Dart
3
4 import 'dart:math';
5 void main(){
6
7 List<int> myNumbers = List(7);
8 myNumbers[0] = 100;
9 myNumbers[1] = 2;
10 myNumbers[2] = 23;
11 myNumbers[3] = 4;
12 myNumbers[4] = 15;
13 myNumbers[5] = 155;
14 myNumbers[6] = 1;
15 int lengthOfArray = myNumbers.length;
16 DisplayLargestInDescendingOrder(myNumbers, lengthOfArray);
17
18 }
19
20 void DisplayLargestInDescendingOrder(List<int> myNumbers, int lengthOfArray){
21 int first = 0;
22 int second = 0;
23 int third = 0;
24
25 if(((first.isInfinite != false) && (second.isInfinite != false)) && third.isInfinite\
26 != false){
27 print("Three largest elements in descending order: $first, $second and $third");
28 } else {
29 for(int i = 0; i < myNumbers.length; i++){
30 if(myNumbers[i] > first){
31 third = second;
32 second = first;
33 first = myNumbers[i];
34 }
35 else if(myNumbers[i] > second){
36 third = second;
37 second = myNumbers[i];
38 }
39 else if(myNumbers[i] > third){
40 third = myNumbers[i];
41 }
42 }
43 print("Three largest elements in descending order: $first, $second and $third");
44 }
45 }
To run the above program, we have to import the Dart math libraries.
1 // output of code 4.42
2 Three largest elements in descending order: 155, 100 and 23
Rotating an array clockwise, is one of the most common and complex algorithm involving an array. Actually, it rotates the array to the left by the number of elements. Suppose you have an array like this:
1 {1, 2, 3}
Now, we will rotate the above array to the left or clockwise by one element. Then it becomes like the following array:
1 {2, 3, 1}
If we rotate it by 2 elements, it becomes:
1 {3, 1, 2}
Rotating 3 elements will give us this:
1 {1, 2, 3}
From the above algorithm, we get a common pattern that we see every day. Yes, we are thinking about a clock. A clock has 12 elements. We will get to that point in a moment. Before that, we need to understand this rotational algorithm in a more efficient way. The next code snippet will give you a better idea about it.
1 //code 4.43
2 // Dart
3
4 void main(){
5 List<int> myNumbers = List(7);
6 myNumbers[0] = 100;
7 myNumbers[1] = 2;
8 myNumbers[2] = 23;
9 myNumbers[3] = 4;
10 myNumbers[4] = 15;
11 myNumbers[5] = 155;
12 myNumbers[6] = 1;
13 int lengthOfArray = myNumbers.length;
14 print("The array before left rotation by two elements: ${myNumbers}");
15 print("The array after rotation.");
16 rotateArrayLeft(myNumbers, 2, lengthOfArray);
17 displayArray(myNumbers, lengthOfArray);
18 }
19
20 void rotateArrayLeft(List<int> myArray, int rotatingNumbers, int arrayLength){
21 for(int i = 0; i < rotatingNumbers; i++){
22 rotateLeftByOne(myArray, arrayLength);
23 }
24 }
25
26 void rotateLeftByOne(List<int> myArray, int arrayLength){
27 int temp = myArray[0], i;
28 for (i = 0; i < arrayLength - 1; i++){
29 myArray[i] = myArray[i + 1];
30 }
31 myArray[i] = temp;
32 }
33
34 void displayArray(List<int> myArray, int arrayLength){
35 for(int i = 0; i < arrayLength; i++){
36 print(myArray[i]);
37 }
38 }
Let us first see the output first, then we will try to understand the algorithm.
1 // output of code 4.43
2 The array before left rotation by two elements: [100, 2, 23, 4, 15, 155, 1]
3 The array after rotation.
4 23
5 4
6 15
7 155
8 1
9 100
10 2
We have to create a function that will take two inputs – the array and the length of the array. It will give us output of a temporary value by shifting one element. After that we can call that function inside another function that takes three inputs – the array, the length of array, and the number of elements you want to shift to the left. You can dynamically create any length of array and test the above code in any programming language. It will give us the same result.
Based on the same algorithm, we can now create a digital clock in PHP.
1 //code 4.44
2 // PHP
3
4
5
6 class ClockClass {
7
8 public function clockwiseRotatebyOne(&$theDigitalClock, $numberOfHours) {
9 $temp = $theDigitalClock[0];
10 for ($i = 0; $i < $numberOfHours - 1; $i++){
11 $theDigitalClock[$i] = $theDigitalClock[$i + 1];
12 }
13 $theDigitalClock[$i] = $temp;
14 }
15
16
17 public function clockwiseRotate(&$theDigitalClock, $afterThreeHours, $numberOfHo\
18 urs) {
19 for ($i = 0; $i < $afterThreeHours; $i++){
20 $this->clockwiseRotatebyOne($theDigitalClock, $numberOfHours);
21 }
22 }
23
24 /* utility function to print
25 an array */
26 public function displayHour(&$theDigitalClock, $numberOfHours) {
27 for ($i = 0; $i < $numberOfHours; $i++){
28 if($i == 0){
29 echo "<strong>" . $theDigitalClock[$i] . "</strong>";
30 } else {
31 echo " " . $theDigitalClock[$i] . " ";
32 }
33 }
34 }
35 }
36
37 $theDigitalClock = array( 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 );
38 $numberOfHours = sizeof($theDigitalClock);
39 $afterFewHours = 4;
40
41 echo 'The number of hours shown on the clock before it starts :';
42 echo '<pre>';
43 print_r($theDigitalClock);
44 echo '</pre>';
45 echo '<br>';
46
47 $clock = new ClockClass();
48 echo "After {$afterFewHours} hours the clock shows the exact time at the starting po\
49 int : ";
50 echo '<br>';
51 echo "It rotates clockwise shifting the first {$afterFewHours} elements at the last \
52 : ";
53 echo '<br>';
54 echo '<br>';
55 $clock->clockwiseRotate($theDigitalClock, $afterFewHours, $numberOfHours);
56 $clock->displayHour($theDigitalClock, $numberOfHours);
While we run the code, first it gives us the hours arranged just like any analog clock. Although the analog clock is an example of discrete mathematical conceptions, it represents contiguous mathematical conceptions that run continuously.
On the other hand the digital clock is the correct example of discrete mathematics. Here it works as a digital clock. As you enter the amount of hours, it gives us the output accordingly.
1 // output of code 4.44
2 The number of hours shown on the clock before it starts :
3
4 Array
5 (
6 [0] => 12
7 [1] => 1
8 [2] => 2
9 [3] => 3
10 [4] => 4
11 [5] => 5
12 [6] => 6
13 [7] => 7
14 [8] => 8
15 [9] => 9
16 [10] => 10
17 [11] => 11
18 )
19
20
21 After 4 hours the clock shows the exact time at the starting point :
22 It rotates clockwise shifting the first 4 elements at the last :
23
24 4 5 6 7 8 9 10 11 12 1 2 3
Run the code locally, you will find the starting element in bold point.
According to the Set theory, we know how ‘Union’ of two sets work. If there is no repeated values, then they join accordingly. We can imagine a situation where, we can add two Sets A and B like this:
1 {1, 2} Union {3, 4}
It will produce a third Set C like this:
1 {1, 2, 3, 4}
We can consider them as arrays also. Two arrays, A and B. Now, mathematically we can also do some Union operations on those Sets in reverse order. It means, just as we have added A and B, we can also add B and A. And that Union yields this result:
1 {3, 4, 1, 2}
Our next algorithm will be to find how we can change this reversing process in a different way. We are going to change (A Union B) to (B Union A) using Dart programming language.
Certainly, there are different solutions available. We follow the next algorithm.
1 //code 4.45
2 //Dart
3
4 void main(){
5
6 List<int> arrayOne = List(2);
7 arrayOne[0] = 1;
8 arrayOne[1] = 2;
9
10 List<int> arrayTwo = List(2);
11 arrayTwo[0] = 3;
12 arrayTwo[1] = 4;
13
14 /*
15 arrayOne Union arrayTwo gives us : 1, 2, 3, 4
16 suppose we call it arrayThree
17 from arrayThree we want arrayTwo Union arrayOne, which gives us : 3, 4, 1, 2
18 there are different solutions
19 we can rotate arrayThree by 2 elements to get the same result
20 we can also follow the following algorithm
21 */
22
23 List<int> arrayThree = List(4);
24 arrayThree[0] = 1;
25 arrayThree[1] = 2;
26 arrayThree[2] = 3;
27 arrayThree[3] = 4;
28
29 print("The arrayThree is the union of arrayOne and arrayTwo and the output is : ${ar\
30 rayThree.toString()}");
31
32 int num = arrayThree.length;
33 int element = 2;
34 element = element % num;
35 print("We are going to use reversal algorithm, so that arrayThree becomes "
36 "the union of arrayTwo and arrayOne.");
37 print("The new output is : ");
38 rotatingLeft(arrayThree, element);
39 displayReversedArray(arrayThree);
40
41 }
42
43 void reversingTheArray(List<int> arrayThree, int start, int end){
44 while(start < end){
45 int temp = arrayThree[start];
46 arrayThree[start] = arrayThree[end];
47 arrayThree[end] = temp;
48 start += 1;
49 end = end -1;
50 }
51 }
52
53 void rotatingLeft(List<int> arrayThree, int element){
54 int num = arrayThree.length;
55 if(element != 0){
56 reversingTheArray(arrayThree, 0, (element - 1));
57 reversingTheArray(arrayThree, element, (num - 1));
58 reversingTheArray(arrayThree, 0, (num - 1));
59 } else {
60 print("Wrong input");
61 }
62 }
63
64 void displayReversedArray(List<int> arrayThree){
65 for(int element in arrayThree){
66 print(element);
67 }
68 }
Let us read the comments inside our code. We have clarified our algorithm there.
1 // output of code 4.45
2 The arrayThree is the union of arrayOne and arrayTwo and the output is : [1, 2, 3, 4]
3 We are going to use reversal algorithm, so that arrayThree becomes the union of arra\
4 yTwo and arrayOne.
5 The new output is :
6 3
7 4
8 1
9 2
As we have seen before, there are several solutions available. We just need only 12 lines of code to rotate any array clockwise by one element. The next code snippet will show you how we can do that.
1 //code 4.46
2 //Dart
3
4 void main(){
5
6 List<int> anArray = List(4);
7 anArray[0] = 1;
8 anArray[1] = 2;
9 anArray[2] = 3;
10 anArray[3] = 4;
11 print("The array before rotating by one element.");
12 for(int element in anArray){
13 print(element);
14 }
15 print("Rotating the array clockwise just by one element.");
16 justRotate(anArray);
17
18 }
19
20 void justRotate(List<int> someArray){
21 int x;
22 int i;
23 x = someArray.length;
24 for(i = (someArray.length - 1); i > 0; i--){
25 someArray[i] = someArray[i - 1];
26 }
27 someArray[0] = x;
28 for(int element in someArray){
29 print(element);
30 }
31 }
The outcome is quite expected. Rotate the above array clockwise just by one element, and it plucks off the last element from the end and places it at the starting point.
1 // output of code 4.46
2 The array before rotating by one element.
3 1
4 2
5 3
6 4
7 Rotating the array clockwise just by one element.
8 4
9 1
10 2
11 3
In this section, we have seen many array algorithm, and hopefully those make enough sense to go ahead for more. For us, in the next section, the data structures are awaiting.
Before going to data structures, we should remember one key point – they are not sequential as an array. It has advantages and disadvantages. While we cut into data structures, we will try to use the same algorithm to understand which one is more preferable contextually. No other data structure is able to save memory like array. That it quite evident. However, there are other advantages;and, we will learn them in the coming sections.
I write regularly on Algorithm and Data Structure in
QUIZZ and Challenge on Chapter Four
Question 1: The discrete mathematical algebraic conceptions that are known as date set is the root of Data Structures in Computer Programming.
Option 1: False
Option 2: True
Answer: Option 2
========================
Question 2: The main advantage of array is, it helps us to save the memory of the system.
Option 1: False
Option 2: True
Answer: Option 2
=======================
Question 3: Which collection of elements or data structure holds a similar “type” of elements?
Option 1: Map and Array
Option 2: Array, Set and Map
Option 3: Array
Option 4: None of the above
Answer: Option 3
=======================
Question 4: Why it is mandatory to learn Set theory in Discrete Mathematics?
Option 1: Because the Set theory conceptions are distributed over a considerable amount in computer science as a whole
Option 2: Set theory is only concerned about distinct numbers.
Option 3: With all types of set operations we can make declarative statements.
Option 4: None of the above is true.
Answer: Option 2
=======================
Question 5: What is the similarity between the Set theoretical conceptions, and the Probability concepts.
Option 1: Both are applied diversely into computer science and programming world.
Option 2: There is no similarity between these two Mathematical Concepts.
Option 3: We can explore a range of huge data or Set, and calculate all types of probabilities. Hence they are similar.
Option 4: Both deal with distinct numbers.
Answer: Option 1
=======================
Challenge 1 : Can you write a program that will find whether a particular number is there in a randomly generated data structure of integers or not.
Solution for Challenge 1:
Language used: Java
1 // code
2
3 package fun.sanjibsinha.datastructures;
4
5 public class ManipulatingArray {
6
7 private int arrayOfRandomNumbers[] = new int[20];
8
9 private int sizeOfArray = 5;
10
11 public void getRandomElements(){
12 for (int i = 0; i <= sizeOfArray; i++){
13 arrayOfRandomNumbers[i] = (int)(Math.random()*121)+121;
14 System.out.println(arrayOfRandomNumbers[i]);
15 }
16 }
17
18 public boolean getValueInArray(int findTheValue){
19 boolean theValue = false;
20 for(int i = 0; i < sizeOfArray; i++){
21 if(arrayOfRandomNumbers[i] == findTheValue){
22 theValue = true;
23 }
24 }
25 return theValue;
26 }
27
28 public static void main(String[] args) {
29 ManipulatingArray manArray = new ManipulatingArray();
30 manArray.getRandomElements();
31 System.out.println("**********");
32 System.out.println(manArray.getValueInArray(121));
33 }
34 }
35
36 // output
37
38 136
39 227
40 157
41 143
42 233
43 195
44 **********
45 false
Explanation and clue to solution: Because Java ‘Math.random()’ method produces ‘double’ data type, we have to cast it to a round figure by using ‘int’ data type.
arrayOfRandomNumbers[i] = (int)(Math.random()*121)+121;
Challenge 2 : Can you reverse an ordered sequence of words? Example: sanjib to bijnas
Solution for Challenge 2:
In first case Language used: python 3.10 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
1 # initializing strings
2 test_str = 'sanjib'
3
4 # printing original string
5 print("The original string is : " + str(test_str))
6
7 # initializing mirror dictionary
8 mirror_dictionary = {'s':'b', 'a':'i', 'n':'j', 'b':'s', 'i':'a', 'j':'n'}
9 res = ''
10
11 # accessing letters from dictionary
12 for element in test_str:
13 if element in mirror_dictionary:
14 res += mirror_dictionary[element]
15
16 # if any character not present, flagging to be invalid
17 else:
18 res = "Not Possible"
19 break
printing result
1 print("The mirror string : " + str(res))
2
3 // output:
4
5 /usr/bin/python3.10 /home/sanjib/Documents/development/test-python/hello.py
6
7 The original string is : sanjib
8 The mirror string : bijnas
==========
In Second case Language used: Java ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
1 // code
2
3 package fun.sanjibsinha;
4 /*
5 Some more Array methods using external apache commons lang3
6 */
7
8 import org.apache.commons.lang3.ArrayUtils;
9
10 public class A18 {
11
12 public static void main(String[] args){
13 //we can reverse an Array
14 char[] myName = {'s', 'a', 'n', 'j', 'i', 'b'};
15 //now we can just add this characters to get my name
16 System.out.println("My name : " + new String(myName));
17 //let us reverse thsi character to see how my name looks in the mirror
18 ArrayUtils.reverse(myName);
19 System.out.println("My name on the mirror : " + new String(myName));
20 }
21 }
22
23 OUTPUT
24 ------
25
26 My name : sanjib
27 My name on the mirror : bijnas
’’’’’’’’’ In the second case, with the help of these external libraries we can reverse any array components in less lines of code. In usual case, we need to write extra code to get the same result.
However, in Dart Programming langauge, it takes only one line of code.
’’’’’’’’’
In Third case Language used: Dart ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
1 main() {
2
3 var input = "sanjib";
4 print(String.fromCharCodes(input.runes.toList().reversed));
5
6 }
7
8 ---output---
9
10 bijnas
Challenge 3 : According to the Set theory, the Union occurs between two Sets and the output omits the common value. Can you write a program to prove this concept.
Solution for Challenge 3:
Language used: PHP 8
1 // code
2
3
4 <?php
5
6 /*
7 * They have similarities and differences
8 * Set theory of Discrete mathematics and PHP has many similarities
9 * Both represent data sets
10 Both hold a list of similar elements
11 We can operate on both by performing union, intersection etc
12 */
13
14 // consider two separate arrays
15
16 $arrayOne = [11, 12, 13];
17 $arrayTwo = [11, 12, 13, 14, 15];
18
19 // consider one universal array that contain elements of both arrays
20
21 $universalArray = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
22
23 /*
24 * According to the set theory, the union occurs as
25 * $arrayOne + $arrayTwo
26 * the output omits the common value
27 * we can do the same using PHP
28 */
29
30 $unionOfTwoArrays = $arrayOne + $arrayTwo;
31
32 echo "Union of two arrays : [" . implode(", ", $unionOfTwoArrays) . "]<br>";
33
34 /*
35 * We can do the difference operation using the same technique
36 * we can use the PHP default methods
37 */
38
39 $differenceOfTwoArrays = array_diff($arrayTwo, $arrayOne);
40
41 echo "Difference of two arrays : [" . implode(", ", $differenceOfTwoArrays) . "]<br>\
42 ";
43
44
45 /*
46 * We can do the intersection operation using the same technique
47 * it keeps the same elements
48 * we can use the PHP default methods
49 */
50
51 $intersectionOfTwoArrays = array_intersect($arrayOne, $arrayTwo);
52
53 echo "Intersection of two arrays : [" . implode(", ", $intersectionOfTwoArrays) . "]\
54 <br>";
55
56 /*
57 * We can do the complement operation on two arrays
58 * we can use the PHP default methods
59 */
60
61 $arrayOneComplement = array_diff($universalArray, $arrayOne);
62
63 echo "Complement of arrayOne : [" . implode(", ", $arrayOneComplement) . "]<br>";
64
65 $arrayTwoComplement = array_diff($universalArray, $arrayTwo);
66
67 echo "Complement of arrayTwo : [" . implode(", ", $arrayTwoComplement) . "]<br>";
68
69 // output
70
71 Union of two arrays : [11, 12, 13, 14, 15]
72 Difference of two arrays : [14, 15]
73 Intersection of two arrays : [11, 12, 13]
74 Complement of arrayOne : [14, 15, 16, 17, 18, 19, 20]
75 Complement of arrayTwo : [16, 17, 18, 19, 20]
Challenge 4 : Write a program where every element of the array is the same. Find out the probability.
Solution for Challenge 4:
Language used: Python 3.10
1 // code
2
3 # we are to find the probability of finding an element in an array
4 # it depends on two factors
5
6 # Probability = number of favorable outcome / number of possible outcomes
7 # number of possible outcomes is the length of the array
8 # number of favourable outcome is the total number of the element in the list
9 # Probability = total number of the element present / size or length of the array.
10
11 # define the function to find the probability
12 def findTheProbability(theArray, theLenghtOfArray, theElement):
13 count = theArray.count(theElement)
14
15 # find probability up to 4 decimal places
16 return round(count / theLenghtOfArray, 4)
17
18 theArrayVariable = [22, 22, 22, 22, 22, 22, 22]
19 theElementToFind = 22
20 theLenghtOfTheArrayVariable = len(theArrayVariable)
21
22 print(findTheProbability(theArrayVariable, theLenghtOfTheArrayVariable, theElementTo\
23 Find))
24
25 // output
26 // Since every element of the array is the same, the probability is 100 percent.
27
28 1.0
5. Data Structures: Abstractions and Implementation
As we have said in the beginning of the book, Data Structures are the one of the most fundamental and essential building blocks of Computer Science. Any Data Structure can be divided in two distinct parts – Abstract Data Types (ADT) and Implementation. As we progress, we will have elaborate discussion on these features; so, you need not worry at the beginning of this chapter.
We have seen many examples of Array, which is the first step to understand Data Structure. Therefore, we already know that Data Structures are basically different types of manners through which we sort, organize, insert, update, remove or display our data.
Sorting and organizing data in an efficient manner plays a very big role in constructing our data structure. Besides, we need to remember one key aspect of computation; that is,how much time the program takes, and how much memory or space it acquires.
In this part Algorithm plays a vital role. Efficient Algorithm to handle Data Structure is always needed. In this chapter, we also look at that part – time complexity, and memory allocation.
Data Structure, as a whole, is a very big topic and, moreover, every programming language has their own way to use the basic concepts of Data Structure. We will limit our main discussion to C, C++ and Java; although, in many occasions we will talk about Python, Dart, PHP and C#, as well.
To give you an idea about how the whole concepts of the complex entity like Data Structures are constructed, we should look into the Collection Interface first. In Java, the Collection Interface is divided into many branches of sub-interfaces, they are – BeanContext, BeanContextServices, BlockingDeque, BlockingQueue, Deque, List, NavigableSet, Queue, Set, SortedSet, TransferQueue. Let us first talk about the List Interface. AbstractList class implements the List Interface. Next, three more classes – ArrayList, Vector, and AbstractSequentialList classes extends the AbstractList class. Finally the LinkedList class extends the properties and methods of AbstractSequentialList class. However, this list is incomplete.
Actually, there are many implementing classes; they are - AbstractCollection, AbstractList, AbstractQueue, AbstractSequentialList, AbstractSet, ArrayBlockingQueue, ArrayDeque, ArrayList, AttributeList, BeanContextServicesSupport, BeanContextSupport, ConcurrentLinkedDeque, ConcurrentLinkedQueue, ConcurrentSkipListSet, CopyOnWriteArrayList, CopyOnWriteArraySet, DelayQueue, EnumSet, HashSet, JobStateReasons, LinkedBlockingDeque, LinkedBlockingQueue, LinkedHashSet, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, RoleList, RoleUnresolvedList, Stack, SynchronousQueue, TreeSet, and Vector.
And this ‘Collection’ interface has a super-interface – Iterable.
As you see, the list is quite long; understandably, we are not going to cover all these things in a chapter. Maybe, in a different book we can take a more detail look at those interfaces and implementing classes.
In this chapter we will look into the core Collection interface and its implementations that include Set, SortedSet, List, Queue, Deque, Map and SortedMap. Core collection interfaces are the foundation of the Java Collections Framework.
In C or C++, it is thought differently. Other languages have their own constructs.
Before discussing Data Structures, we must have some basic knowledge about how objects act upon one another. How different objects pass messages between themselves. We will also try to manually insert data into a Linked List. This is a List that is linked to each other.
How objects work with each other
We are going to use four, easy-to-understand sample Dart program to see how one object works with other objects. Let us talk about the first program. Suppose each person acquires a mobile application that helps them to enter their tasks. They can categorize the tasks and according to the necessity, they finish their tasks.
To accomplish such simple task, we need to have two classes – Person and the Mobile Application class. Because,one person object acquires one application object, we need an application object inside the Person class. The application object has a blueprint or class that defines what it can do and what it cannot do.
Once a person acquires an application object, she can start doing everything with that object that has been defined in the Mobile Application class.
1 //cdoe 5.1
2 //Dart
3
4 void main(){
5
6 var appOne = AppToDo("AppToDo One");
7 var appTwo = AppToDo("AppToDo Two");
8 var john = Person("John");
9 var mac = Person("Mac");
10 john.taskToDo = appOne;
11 mac.taskToDo = appTwo;
12 print("${john.name} gets ${john.taskToDo.name}.");
13 print("${mac.name} gets ${mac.taskToDo.name}");
14 /*
15 John gets AppToDo One.
16 Mac gets AppToDo Two
17 */
18 print("${john.name} is entering tasks.");
19 john.taskToDo.task = "Going to market to get some vegetables";
20 john.taskToDo.type = "Marketing";
21 john.taskToDo.enterTask();
22 // we presume that every task is important
23 john.getTaskFinished(appOne);
24 print("${mac.name} is entering tasks.");
25 mac.taskToDo.task = "Going out with friends";
26 mac.taskToDo.type = "Outing";
27 mac.taskToDo.enterTask();
28 // in some cases, the task may not be so important
29 appTwo.isImportant = false;
30 mac.getTaskFinished(appTwo);
31 }
32
33 class AppToDo{
34
35 String name;
36 String task;
37 String type;
38 bool isImportant = true;
39
40 AppToDo(String name){
41 this.name = name;
42 }
43
44 void enterTask(){
45 print("I want to finish this task - ${task}. It belongs to this type - ${type}."\
46 );
47 }
48 }
49
50 class Person{
51 String name;
52 AppToDo taskToDo;
53
54 Person(String name){
55 this.name = name;
56 }
57
58 void getTaskFinished(AppToDo taskToDo){
59 this.taskToDo = taskToDo;
60 if(taskToDo.isImportant){
61 print("This task - ${taskToDo.task} is important, and need to be finished.");
62 } else {
63 print("It can be avoided, it is not so important");
64 }
65 }
66 }
I hope the explanation makes sense. Each person object is a separate entity, and each application object is also separate entity. However, every separate object has some commonness, and that commonness has been defined in the class.
We can expect the output, now.
1 //output of code 5.1
2 John gets AppToDo One.
3 Mac gets AppToDo Two
4 John is entering tasks.
5 I want to finish this task - Going to market to get some vegetables. It belongs to t\
6 his type - Marketing.
7 This task - Going to market to get some vegetables is important, and need to be fini\
8 shed.
9 Mac is entering tasks.
10 I want to finish this task - Going out with friends. It belongs to this type - Outin\
11 g.
12 It can be avoided, it is not so important
The same principle can be adopted for two separate persons. The next code snippet manifests that principle.
1 //code 5.2
2 //Dart
3
4 void main(){
5 var alisa = Person("Alica");
6 var john = Person("John");
7
8 alisa.isFollowing(john);
9 john.isNotFollowing(alisa);
10 }
11
12 class Person{
13 String name;
14 Person friend;
15 Person(String name){
16 this.name = name;
17 }
18 void isFollowing(Person friend){
19 this.friend = friend;
20 print("${name} is following ${friend.name}");
21 }
22 void isNotFollowing(Person friend){
23 this.friend = friend;
24 print("${name} is not following back ${friend.name}");
25 }
26 }
Here goes the output:
1 //output of code 5.2
2 Alica is following John
3 John is not following back Alica
We can make the above code more robust and complex. However, we are trying to understand how objects work, just like other primitive data types. There is no doubt that an object is always more powerful than any single primitive data type. If you have some idea about object-oriented-programming, you know that an object encapsulates many dynamic features. An object’s power depends solely on the principle that how we have defined that object in its class.
Now, we are more curious about how we can implement this newly acquired knowledge to manipulate a simple Data Structure.
Suppose, we want to insert data into a list, and show them also at the same time. Without taking any help from array, can we do that? Can we write classes that will define such objects that will work with each other to manipulate data in a data structure?
Let us see the next code.
1 //code 5.3
2 //Dart
3
4 void main(){
5
6 int countNodes(NodeClass start){
7 int count = 0;
8 NodeClass currentPosiion = start;
9 while(currentPosiion.next != null){
10 currentPosiion = currentPosiion.next;
11 count = count + 1;
12 }
13 return count;
14 }
15
16 var nodeOne = NodeClass(10);
17 print("The value of node 1 is - ${nodeOne.data} and the count is ${countNodes(nodeOn\
18 e)}");
19 var nodeTwo = NodeClass(12);
20 nodeOne.next = nodeTwo;
21 print("The value of node 2 is - ${nodeTwo.data} and the count is ${countNodes(nodeOn\
22 e)}");
23 var nodeThree = NodeClass(122);
24 nodeTwo.next = nodeThree;
25 print("The value of node 3 is - ${nodeThree.data} and the count is ${countNodes(node\
26 One)}");
27 var nodeFour = NodeClass(1122);
28 nodeThree.next = nodeFour;
29 print("The value of node 4 is - ${nodeFour.data} and the count is ${countNodes(nodeO\
30 ne)}");
31 var nodeFive = NodeClass(1226);
32 nodeFour.next = nodeFive;
33 print("The value of node 5 is - ${nodeFive.data} and the count is ${countNodes(nodeO\
34 ne)}");
35 }
36
37 class NodeClass{
38 int data;
39 NodeClass next;
40 NodeClass(int data){
41 this.data = data;
42 }
43 }
We have created a Node Class and with the help of node object we have successfully inserted data into that structure.
1 //output of code 5.3
2 The value of node 1 is - 10 and the count is 0
3 The value of node 2 is - 12 and the count is 1
4 The value of node 3 is - 122 and the count is 2
5 The value of node 4 is - 1122 and the count is 3
6 The value of node 5 is - 1226 and the count is 4
In the above code, we have inserted data manually. Can we create two separate objects that will manage and show the data?
Yes, we can try to do that in the next program.
1 //code 5.4
2 //Dart
3
4 void main(){
5
6 var list = LinkingList();
7 list.insertData(10);
8 list.showData();
9 list.insertData(100);
10 list.insertData(1000);
11 list.insertData(10000);
12 list.insertData(100000);
13 list.insertData(1000000);
14 list.insertData(10000000);
15 list.insertData(100000000);
16 }
17
18 class NodeClass{
19 int data;
20 NodeClass next;
21 }
22
23 class LinkingList{
24 /*
25 this class will insert data into the lists
26 and show the data as well
27 */
28 /*
29 if our list is empty, the starting point of node, we will call it head, is null
30 however, if the list has at least one value the head is not null
31 */
32 NodeClass head;
33
34 void insertData(int data){
35 var node = NodeClass();
36 node.data = data;
37 // at the beginning
38 node.next = head;
39 if(head == null){
40 head = node;
41 } else {
42 NodeClass currentPosition = head;
43 while(currentPosition.next != null){
44 currentPosition.next = node;
45 }
46 // we take the last value added and print it out
47 print("One value is added to the list. ${node.data}");
48 }
49 }
50 void showData(){
51 NodeClass node = head;
52 // this method will work when the first value is added
53 if(head == null){
54 print("No value has been added in the list. It is empty.");
55 } else {
56 print("One value is added to the list: ${node.data}");
57 }
58 }
59 }
Here goes the output, where the node object ‘list’ has successfully inserted data, and finally, gives us a display of the inserted data.
1 //output of code 5.4
2 One value is added to the list: 10
3 One value is added to the list. 100
4 One value is added to the list. 1000
5 One value is added to the list. 10000
6 One value is added to the list. 100000
7 One value is added to the list. 1000000
8 One value is added to the list. 10000000
9 One value is added to the list. 100000000
We have tried to understand how in object-oriented-programming languages like C++, Java, or Dart, these Collection interface is being implemented by the implementing classes. Now, we will understand how the core libraries and functions of the Data Structure classes and objects work together.
More Algorithm and Time Complexity
This section will be short. We won’t take much time to study a few code snippets, after that we will try to understand how much time it takes to run the program.
At the same time, we will also try to understand the underlying logic, and algorithm.
By this time we are quite familiar with the terms like algorithm and time complexity. We know that our algorithm should be efficient enough to reduce the time to run the code.
We should also remember that, any problem can have many solutions; we need to find the best algorithm.
Okay, let us try to some code in Dart. In the first case, we will try to find the factors of a positive integer. As we know, a positive integer, like 4, has three factors – 1,2 and 4. Factors are the integers that can divide the number. It always starts with 1 and ends with that number.
A prime number is a number that can be divided only by the 1 and the number itself, such as 2, 3, 5, or 7. The list goes on. To find whether a number is prime or not is very easy.
We can start the examination with a prime number like 5. All we need to check that whether all the numbers starting from 2 to 4, can divide 5 or not. If any number can divide 5, then 5 is not prime. Else, 5 is prime. Now, we can easily check whether a number is prime or not.
We will come to that point in a minute. Before that, we will find factors of a number.
1 //code 5.5
2 // Dart
3 import 'dart:math';
4 void main(){
5
6 // we will find factors of 36
7 // we can add two factors 1 and 36 itself
8 // time complexity is O(n)
9 List<int> numbers = List();
10 for(int i = 1; i <= 36; i++){
11 if(36 % i == 0){
12 numbers.add(i);
13 }
14 }
15 print("${List.from(numbers)}");
16
17 List<int> moreNumbers = List();
18 moreNumbers.add(1);
19 for(int i = 1; i <= 18; i++){
20 if(36 % i == 0){
21 moreNumbers.add(i);
22 }
23 }
24 moreNumbers.add(36);
25 print("${List.from(numbers)}");
26
27
28 // in both cases, below, time complexity is O(square root of n)
29 // which is far better than before
30 List<double> nums = List();
31 for(double j = 1; j <= sqrt(36); j ++ ){
32 if(36 % j == 0){
33 nums.add(j);
34 if(j != sqrt(36)){
35 nums.add(36/j);
36 }
37 }
38 }
39 nums..sort();
40 print("${List.from(nums)}");
41
42
43 List<int> moreNums = List();
44 for(int j = 1; j <= sqrt(36); j ++ ){
45 if(36 % j == 0){
46 moreNums.add(j);
47 if(j != sqrt(36)){
48 moreNums.add((36/j).round());
49 }
50 }
51 }
52 moreNums.sort();
53 print("${List.from(moreNums)}");
54
55 List<int> numsMore = List();
56 for(int j = 1; j <= sqrt(35); j++ ){
57 if(35 % j == 0){
58 numsMore.add(j);
59 if(j != sqrt(35)){
60 print("true");
61 numsMore.add((35/j).round());
62 }
63 }
64 }
65 numsMore.sort();
66 print("${List.from(numsMore)}");
67
68
69 }
Let us see the output first.
1 // output of code 5.5
2 [1, 2, 3, 4, 6, 9, 12, 18, 36]
3 [1, 2, 3, 4, 6, 9, 12, 18, 36]
4 [1.0, 2.0, 3.0, 4.0, 6.0, 9.0, 12.0, 18.0, 36.0]
5 [1, 2, 3, 4, 6, 9, 12, 18, 36]
6 true
7 true
8 [1, 5, 7, 35]
In the first part of code, we will loop through the number itself.
1 List<int> numbers = List();
2 for(int i = 1; i <= 36; i++){
3 if(36 % i == 0){
4 numbers.add(i);
5 }
6 }
7 print("${List.from(numbers)}");
However, in the next code, we loop to the half of the number.
1 List<int> moreNumbers = List();
2 moreNumbers.add(1);
3 for(int i = 1; i <= 18; i++){
4 if(36 % i == 0){
5 moreNumbers.add(i);
6 }
7 }
8 moreNumbers.add(36);
9 print("${List.from(numbers)}");
But, the problem, in both cases, we need to the number itself. So the time complexity is big O(n).
Can we reduce the time, to run the program?
Okay, we can check them with the next sample.
1 List<double> nums = List();
2 for(double j = 1; j <= sqrt(36); j ++ ){
3 if(36 % j == 0){
4 nums.add(j);
5 if(j != sqrt(36)){
6 nums.add(36/j);
7 }
8 }
9 }
10 nums..sort();
11 print("${List.from(nums)}");
This time, we have succeeded to reduce the time complexity to big O(square root of n). For a big amount of integer, this algorithm fits fine.
In the next code snippets, we will find the prime factors of a positive integer. Factors of any integer can be divided to get the prime factors easily. The factors of 4 is 1, 2 and 4. We cannot divide 1 and 2. The integer 2 is prime. But, we can divide 4 and get 2 multiplied by 2.
Finally, it looks like: 1, 222. We can say the prime factors of 4 is 1 and 222, or we can also say that the prime factors are – 1 and 2 to the power of 3.
Let us check the next code snippets to find out the prime factors of any positive integer by passing the integer as parameter to a function.
1 // code 5.6
2 // Dart
3
4 import 'dart:math';
5
6 void main(){
7 getPrimeFactors(444);
8 print("++++++++");
9 findPrimeFactors(444);
10 }
11
12 void getPrimeFactors(int anyInteger){
13
14 /*
15 this is one way where time complexity is close to O(n)
16 for i <- 2 to n
17 for loop starts
18 if n%i == 0
19 if construct starts
20 counter = 0
21 while(n%i == 0)
22 n = n/i
23 count++
24 come out from the while loop
25 print (i, counter)
26 if construct ends
27 for construct ends
28 */
29
30 for(int i = 2; i <= anyInteger; i++){
31 if(anyInteger % i == 0){
32 int counter = 0;
33 while(anyInteger % i == 0){
34 anyInteger = (anyInteger / i).round();
35 counter++;
36 }
37 // we can say it like this
38 print("${i} to the power ${counter}");
39 }
40 }
41 // we can say it also like this after watching the output
42 print("The prime factors of 444 are 2*2, 3, 37");
43
44 }
45
46 void findPrimeFactors(int anyInteger){
47
48 /*
49 this is one way where time complexity is close to O(square root of n)
50 which is better than the previous solution
51 for i <- 2 to square root of n
52 for loop starts
53 if n%i == 0
54 if construct starts
55 counter = 0
56 while(n%i == 0)
57 n = n/i
58 count++
59 come out from the while loop
60 print (i, counter)
61 if construct ends
62 for construct ends
63 */
64
65 for(int i = 2; i <= sqrt(anyInteger); i++){
66 if(anyInteger % i == 0){
67 int counter = 0;
68 while(anyInteger % i == 0){
69 anyInteger = (anyInteger / i).round();
70 counter++;
71 }
72 // we can say it like this
73 print("${i} to the power ${counter}");
74 }
75 }
76 if(anyInteger != 1){
77 print("${anyInteger} and 1");
78 }
79 // we can say it also like this after watching the output
80 print("The prime factors of 444 are 2*2, 3, 37");
81
82 }
As you see, in the first function, due to our algorithm, the time complexity is more. However, we have succeeded to reduce that in the second function.
1 // output of code 5.6
2 /home/ss/flutter/bin/cache/dart-sdk/bin/dart --enable-asserts --enable-vm-service:38\
3 103 /home/ss/IdeaProjects/bin/PrimeFactorization.dart
4 Observatory listening on http://127.0.0.1:38103/
5
6 2 to the power 2
7 3 to the power 1
8 37 to the power 1
9 The prime factors of 444 are 2*2, 3, 37
10 ++++++++
11 2 to the power 2
12 3 to the power 1
13 37 and 1
14 The prime factors of 444 are 2*2, 3, 37
15
16 Process finished with exit code 0
In the next program, we will try to find whether a positive integer is prime or not.
1 // code 5.7
2 // Dart
3
4 void main(){
5 primeOrNot(71);
6 }
7
8 void primeOrNot(int anyPositiveInteger){
9
10 for(int i = 2; i <= (anyPositiveInteger - 1); i++){
11 if(anyPositiveInteger % i == 0){
12 print("${anyPositiveInteger} is not prime");
13 break;
14 } else {
15 print("${anyPositiveInteger} is prime.");
16 break;
17 }
18 }
19
20 }
We have passed two positive integers to test whether they are prime or not.
1 // output of code 5.7
2 /home/ss/flutter/bin/cache/dart-sdk/bin/dart --enable-asserts --enable-vm-service:37\
3 903 /home/ss/IdeaProjects/bin/PrimeOrNot.dart
4 Observatory listening on http://127.0.0.1:37903/
5
6 72 is not prime
7
8 Process finished with exit code 0
9
10 /home/ss/flutter/bin/cache/dart-sdk/bin/dart --enable-asserts --enable-vm-service:32\
11 885 /home/ss/IdeaProjects/bin/PrimeOrNot.dart
12 Observatory listening on http://127.0.0.1:32885/
13
14 71 is prime.
15
16 Process finished with exit code 0
In the next section we will start discussing data structures. However, before moving into the data structures, we will see a couple of geometry algorithm, which is important to understand one key feature of data structures in C and C++.
At the same time, we will cut into discrete mathematical concepts of vector space. In Computer Science, Vectors represent a couple of things, such as lists of rows and columns, only rows; sometimes, we can place a vector point with two co-ordinates X and Y and find the direction of the point with respect to a line segment.
This algorithm is used in producing maps, directions, finding area of polygons, and many more things using Vector cross products.
In a map, how do we get the direction of a point? Should we turn right or left? We can move forward also, if that point lies on the same line.
In Geometry, three concepts play vital roles – point, line and plane.
You have probably noticed that, we are talking about these three features, in particular. To understand our points, let us see a figure (Figure 5.1) first.
Taking a look at the figure, we can say that the point C is on the left side of the line segment AB. But, is there any formula, to find that in Vector space?
Yes, there are; we can use the Vector cross products. We always calculate the position of any point placing them on the Cartesian plane. We have X and Y co-ordinates. Having the values of two co-ordinates helps us to find the direction of C from the line segment AB.
Suppose we are moving from A to B. Now we want to take turn and reach C. Should we take the left turn, or right turn? Well, the above figure tells us to take the left turn. But, how will we calculate that using co-ordinate system?
In any two-dimensional problem, like this, using Cartesian plane is the best choice, and we have adopted that for the sake of our algorithm.
According to the above figure, co-ordinate values of A is (-4, 3), and the co-ordinate values of B and C are respectively (2, -3) and (5,3).
For the sake of simplicity, if we consider that A lies on the origin O, that is, the co-ordinate values of A changes to (0, 0), then the cross products of B and C help us to determine the exact position of C with respect to B.
If the value of the cross products is greater than 0, or positive, or counter clockwise, then C is on the left side of B. If it is negative, then it is on the right hand side. Finally, if it is 0, then C is on the same line.
The Vector cross products formula is pretty simple. It is just as follows:
1 The X co-ordinate value of B * The Y co-ordinate value of C - The Y co-ordinate val\
2 ue of B * The X co-ordinate value of C
According to the figure (assuming A has co-ordinate values (0,0) ), the value is 15, which is positive. It proves that C is on the left side of point B. However, we have assumed that the co-ordinate values of A is (0, 0), to look it simple; which is actually not.
To do the real calculation, we need to shift A from its original position to the origin O. The co-ordinate values of A will change from (-4, 3) to (0, 0).
That will also change the co-ordinate values of B and C. The new X co-ordinate value of B will be (X co-ordinate value of B – X co-ordinate value of A), and the new Y co-ordinate value of B will be (Y co-ordinate value of B – Y co-ordinate value of A). The same rule will be applied to the co-ordinate values of C.
In our next Java program, we have calculated that find the direction of C from line segment AB.
1 // code 5.8
2 // Java
3
4 package fun.sanjibsinha.classesandobjects;
5
6 class PointClass{
7 double x, y;
8 }
9 public class GetDirection {
10
11 public static void main(String[] args) {
12 PointClass a = new PointClass();
13 a.x = -30;
14 a.y = 25;
15 PointClass b = new PointClass();
16 b.x = 15;
17 b.y = -18;
18 PointClass c = new PointClass();
19 c.x = 13;
20 c.y = 18;
21 // if point a comes to the origin having x and y co-ordinates
22 // both change to 0 and 0
23 // the x and y co-ordinates of b will change
24 b.x = b.x - a.x;
25 b.y = b.y - a.y;
26 // the x and y co-ordinates of c will also change
27 c.x = c.x - a.x;
28 c.y = c.y - a.y;
29 // to get direction of point c with respect to the
30 // line segment ab, joining points a and b becomes easier
31 // we will use cross products of points b and c
32 double crossProductsOfBAndC = (b.x * c.y) - (b.y * c.x);
33 // the value is 1180.0, which denotes c is on the left
34 if(crossProductsOfBAndC > 0){
35 System.out.println("The point c is on the left of line ab.");
36 } else if(crossProductsOfBAndC < 0){
37 System.out.println("The point c is on the right of line ab.");
38 } else {
39 System.out.println("The point c is on the same line of ab.");
40 }
41 /*
42
43 */
44
45 }
46 }
Take a look at the output:
1 // output of code 5.8
2 the output is:
3 The point c is on the left of line ab.
4
5 next, let us change all the co-ordinates of c to negative value
6 the output is:
7 The point c is on the right of line ab.
8
9 next, let us change the value of c equal to b
10 the output is:
11 The point c is on the same line of ab.
We have already learned how the Vector cross products work to find the direction of the point. So, we are not discussing the algorithm, anymore. We can write our code, in a different way to accomplish a different type of task, considering that we need not shift A.
In the next code snippet, the point A is the origin, having the co-ordinate values (0, 0).
1 // code 5.9
2 // Java
3
4 package fun.sanjibsinha.classesandobjects;
5 /*
6 formula = difference between two cross products of two points
7 if it is counter clockwise it is +ve else -ve
8
9 */
10 class PointA{
11 // for the sake of simplicity we assume that
12 // point A is on the origin
13 double xCoordinate = 0;
14 double yCoordinate = 0;
15 }
16 class PointB{
17 double xCoordinate;
18 double yCoordinate;
19 PointA a;
20 double getNewXCoordinate(PointA a, double xCoordinate){
21 this.xCoordinate = xCoordinate;
22 xCoordinate = xCoordinate * a.yCoordinate - yCoordinate * a.xCoordinate;
23 return xCoordinate;
24 }
25 double getNewYCoordinate(PointA a, double yCoordinate){
26 this.yCoordinate = yCoordinate;
27 yCoordinate = xCoordinate * a.yCoordinate - yCoordinate * a.xCoordinate;
28 return this.yCoordinate;
29 }
30 }
31 class PointC{
32 PointB b;
33 double leftToB = 1.0;
34 double rightToB = -1.0;
35 double onSameLine = 0.0;
36 /*
37 double getNewXCoordinate(){}
38 double getNewYCoordinate(){}
39
40 */
41 double findPosition(PointB b, double xCoordinate, double yCoordinate){
42 this.b = b;
43 double difference;
44 difference = b.xCoordinate * yCoordinate - b.yCoordinate * xCoordinate;
45 if(difference > 0.0){
46 return leftToB;
47 } else if(difference < 0.0){
48 return rightToB;
49 } else {
50 return onSameLine;
51 }
52 }
53 }
54
55 public class FindPosition {
56 public static void main(String[] args) {
57 PointB b = new PointB();
58 b.xCoordinate = 5;
59 b.yCoordinate = -6;
60 PointC c = new PointC();
61 System.out.println("On the same line, as c has the same value as b: "
62 + c.findPosition(b, 5, -6));
63 }
64 }
For the sake of simplicity, we have not only kept the co-ordinate values of A as (0, 0); at the same time we make the value of C same as B.
Here is the output:
1 // output of code 5.9
2 On the same line, as c has the same value as b: 0.0
We are again going to experiment with our code. However, this time we have three different co-ordinate values of A, B and C.
1 // code 5.10
2 // Java
3
4 package fun.sanjibsinha.classesandobjects;
5 /*
6 formula = difference between two cross products of two points
7 if it is counter clockwise it is +ve else -ve
8 */
9 class PointNameA{
10 double xCoordinate;
11 double yCoordinate;
12 }
13 class PointNameB{
14 double xCoordinate;
15 double yCoordinate;
16 PointNameA a;
17 double getNewXCoordinate(PointNameA a, double xCoordinate){
18 this.xCoordinate = xCoordinate;
19 this.a = a;
20 xCoordinate = xCoordinate - a.xCoordinate;
21 return xCoordinate;
22 }
23 double getNewYCoordinate(PointNameA a, double yCoordinate){
24 this.a = a;
25 this.yCoordinate = yCoordinate;
26 yCoordinate = yCoordinate - a.yCoordinate;
27 return yCoordinate;
28 }
29 }
30 class PointNameC{
31 double xCoordinate;
32 double yCoordinate;
33 PointNameB b;
34 PointNameA a;
35 PointNameC c;
36 double leftToB = 1.0;
37 double rightToB = -1.0;
38 double onSameLine = 0.0;
39
40 double getNewXCoordinate(PointNameA a, double xCoordinate){
41 this.a = a;
42 this.xCoordinate = xCoordinate;
43 xCoordinate = xCoordinate - a.xCoordinate;
44 return xCoordinate;
45 }
46 double getNewYCoordinate(PointNameA a, double yCoordinate) {
47 this.a = a;
48 this.yCoordinate = yCoordinate;
49 yCoordinate = yCoordinate - a.yCoordinate;
50 return yCoordinate;
51 }
52 double findPosition(PointNameB b, PointNameC c){
53 this.b = b;
54 this.c = c;
55 double difference;
56 difference = b.xCoordinate * c.yCoordinate - b.yCoordinate * c.xCoordinate;
57 if(difference > 0.0){
58 return leftToB;
59 } else if(difference < 0.0){
60 return rightToB;
61 } else {
62 return onSameLine;
63 }
64 }
65 }
66 public class FindPositionMOre {
67 public static void main(String[] args) {
68 PointNameA a = new PointNameA();
69 a.xCoordinate = -3;
70 a.yCoordinate = 6;
71 PointNameB b = new PointNameB();
72 b.getNewXCoordinate(a, 5);
73 b.getNewYCoordinate(a, -8);
74 PointNameC c = new PointNameC();
75 double xOfC = c.getNewXCoordinate(a, 15);
76 double yOfC = c.getNewYCoordinate(a, 18);
77 System.out.println("The point C is on the left of line segment AB, as the va\
78 lue is positive : "
79 + c.findPosition(b, c));
80 }
81 }
If you run the program, you will get the outcome as follows:
1 // output of code 5.10
2 The point C is on the left of line segment AB, as the value is positive : 1.0
You can change the co-ordinate values of A, B and C to see how your output changes.
In the next section, we will start with the same problem to understand how data structures in C and C++ works. After that, we will start digging deep into Data Structures and Algorithm in chapter 6.
In the next section, we will have a brief introduction to the Data Structures using the same Vector cross products and finding direction.
Introducing Data Structures
We have already been introduced to data structures before. Of course, we have learned a few operations using Array in various languages, so we can say that the concept of data structures is not completely alien to us.
We need a good way to store, organize and use our data. As times passes by, the nature of data is becoming not only more and more complex, but also it’s getting bigger in quantity. More and more people are getting hooked to the Internet, exchanging huge amount of data every day, in various forms; scientific data are getting larger, we need weather data to be processed to get more accurate weather prediction, medical data are becoming humongous; this list is endless.
Therefore, we need more efficient way to sort, organize, and use that data.
Data Structures are all about this. It has a very close relation with Algorithm, because managing such huge amount of data is less tedious if we have more efficient Algorithm, ready at our hand.
While managing such huge humongous data, by sorting, organizing, or using them, one is not only prone to error, but also fail to satisfy one of the most important requirements – time and space. Yes, time complexity really matters, so the space.
In this section we have a short introduction to the Data Structures, but we will actually start the topic in the next chapter. First of all let us have a look at a figure (Figure 5.2) first.
We have clearly stated what Data Structures are, in the above figure. We can describe our data structures in our natural language; that is a part of any data structures. It is always good to write it down what we are going to do with our data structures.
Consider a static List or a fixed length List; that is, an array. It is a collection of similar type of data, either integer, double, or string. Moreover, it should have a fixed length while we declare it. Within that range of length, we can insert data, modify data at a specific position, even we can remove a data and make the memory space empty.
Whenever we declare a fixed length List, the memory manager fixes an amount of memory for that list or array. When we write, “int array[4]”, it means, memory manager allocates 4 bytes each for individual address, altogether 16 bytes are allocated.
In language like C or C++, if we want to insert one more data, in whatever position we can imagine; the task becomes tedious. First of all, the memory manager has already fixed a space. So we need to create a larger array. Copy the whole array to the new memory space and at the same time empty the old space.
To make an array dynamic, we might think an array with maximum size that particular data type allows us to use. Since the array is a contiguous block of memory, a large space remains unused. Suppose we declare an array of ‘n’ length. We start with 10 data. Next, as per our need we start adding data to the array. If we add one single data at the very beginning, we need to shift all other data by one space. If the data type is integer, we need not add 4 bytes more at the end in this case particularly because we have kept that space beforehand, after that we need to shift the other data accordingly.
Whatever we do, a large space still remains unused. In terms of memory allocation, this process does not seem friendly.
Since the length of an array is fixed, it works on a constant time.
Now, new languages come up to solve the limitations of older language. Consider the Dart. In Dart, we get two types of List. One is of traditional type – fixed length. Another is growable or dynamic List.
Enough talking, let us see the first code – fixed length List.
1 // code 5.11
2 // Dart
3
4 /*
5 The list is a simple ordered group of objects. Creating
6 a List seems easy because Dart core libraries have the necessary support
7 and a List class. There are two types of Lists.
8 */
9 void main(){
10 listFunction();
11 }
12
13 int listFunction(){
14 List<int> nameOfTest = List(3);
15 nameOfTest[0] = 1;
16 nameOfTest[1] = 2;
17 nameOfTest[2] = 3;
18 //there are three methods to capture the list
19 //1. method
20 for(int element in nameOfTest){
21 print(element);
22 }
23 print("-----------");
24 //2. method
25 nameOfTest.forEach((v) => print('${v}'));
26 print("-----------");
27 //3. method
28 for(int i = 0; i < nameOfTest.length; i++){
29 print(nameOfTest[i]);
30 }
31 }
The output is quite expected.
1 // output of code 5.11
2 1
3 2
4 3
5 -----------
6 1
7 2
8 3
9 -----------
10 1
11 2
12 3
In Dart, everything is object. Therefore, it is a collection of similar objects. Here it is integer. Next, we will make this list dynamic, and see how it works.
1 // code 5.12
2 // Dart
3
4 void main(){
5 growableList();
6 }
7
8 Function growableList(){
9 //1. method
10 List<String> names = List();
11 names.add("Mana");
12 names.add("Babu");
13 names.add("Gopal");
14 names.add("Pota");
15 //there are two methods to capture the list
16 print("-----------");
17 //1. method
18 names.forEach((v) => print('${v}'));
19 print("-----------");
20 //2. method
21 for(int i = 0; i < names.length; i++){
22 print(names[i]);
23 }
24 }
Growable Lists are dynamic in nature. We can dynamically add any number of elements and we can also remove it by a simple method: ‘names.remove(“any name”)’. We can also use the key; as this ordered list starts from 0. So we can remove the first name just by passing this key value: ‘names.removeAt(0)’. We use the ‘removeAt(key)’ method for that operation. We can also clear the whole List just by typing: ‘names.clear()’. Let us see the output, now.
1 // output of code 5.12
2 -----------
3 Mana
4 Babu
5 Gopal
6 Pota
7 -----------
8 Mana
9 Babu
10 Gopal
11 Pota
We have a very short introduction to Data Structures. Hopefully, now we understand what are the limitations and advantages of an array. We will discuss them in detail in the first section of the next chapter 6. Comparing array with other Data Structures will help us gain more insights into this complex topic, which is the most fundamental block of Computer Science.
How Calculus and Linear Algebra are Related to this Discourse
Calculus is the branch of mathematics that describes changes in functions. Now, linear algebraic operations start with functions; moreover, computer programming cannot move a step forward without the implementation of functions.
Mathematically, we can define polynomial, rational, trigonometric, exponential, and logarithmic functions, and at the same time, we can review how to evaluate these functions, and we show the properties of their graphs. Is the concept of function used in computer programming same as mathematical functions?
Before finding the answer, let us formally define what is mathematical function. In Mathematics, before defining a function, we need two sets A and B, where where x is an element of A and y is an element of B, is a relation from A to B.
Now, a relation from the set A to the set B defines a relationship between those two sets.
Mathematically, a function is a special type of relation in which each element of the first set is related to exactly one element of the second set.
We call the element of the first set as the input; and, the element of the second set is called the output. Functions are used all the time in mathematics to describe relationships between two sets.
Actually, when we know the input, the output is determined in a function.
We can write a function like this:
1 y = f(x)
Now, the f(x) can be of any value, such as ‘x + 1’, or ‘x - 1’; in fact, with the addition, subtraction, multiplication or division of any constant value, as we change the value of x, the value of y will change.
The same thing happens in computer programming; a function returns a value. Not always; but it is a general rule that is followed by any programming language.
We may argue that not every function returns a value; there is something called ‘void’, but that also gives us what? An output.
We can find the area of a square if we know the value of one side. We can find the area of a circle, if we know the value of radius.
Mathematically, when we write y = f(x); it can also be said as ‘y equals f of x’. While writing a function like this we refer to x as the independent variable, and y as the dependent variable.
Quite understandably the value of y depends on the value of x.
Now, a function consists of three things, in particular. A set of inputs, a set of outputs and a rule for assigning each input to exactly one output. Mathematically, the set of inputs is called the domain of the function and the set of outputs is called the range of the function.
If the assigning rule of a function is f(x) = 3 – x; and the domain is {1, 2, 3}, then the value of y or the range will be {0, 1, 2}.
Not only we can visualize the function by plotting points (x, y) on coordinate planes, we can write something like this in any programming language.
The code is as follows:
1 // code 5.13
2 // Java
3
4 package fun.sanjibsinha.functions;
5
6 /**
7 * a function will take inputs but always return one output
8 * mathematically we can write it as y = f(x)
9 * here y is output, and f(x) is function
10 * the output can be expressed as range and input as domain
11 * domain may have multiple values that points to one or more than one range
12 */
13
14 public class FunctionDemo {
15 static int x = 0;
16 static int y = 0;
17
18 static int domainOne(int x){
19 y = x + 0;
20 return y;
21 }
22 static int domainTwo(int x){
23 y = x + 1;
24 return y;
25 }
26 static int domainThree(int x){
27 y = x + 2;
28 return y;
29 }
30 static int domainFour(int x){
31 y = x + 3;
32 return y;
33 }
34 static double domainFive(double x){
35 double y;
36 y = Math.pow(x, 2);
37 return y;
38 }
39 static double domainSix(double x){
40 double y;
41 y = Math.sqrt(x);
42 return y;
43 }
44
45 static double[] xValue = {4, 3, 2, 1};
46
47 static double returnRange(int index){
48 double y = 0;
49 if(xValue[x] == 4){
50 y = xValue[x] + 0;
51 return y;
52 } else if (xValue[x] == 3){
53 y = xValue[x] + 1;
54 return y;
55 } else if (xValue[x] == 2){
56 y = xValue[x] + 2;
57 return y;
58 } else if (xValue[x] == 1){
59 y = xValue[x] + 3;
60 return y;
61 } else if (xValue[x] == 2){
62 y = Math.pow(xValue[x], 2);
63 return y;
64 } else {
65 return y;
66 }
67 }
68
69 public static void main(String[] args) {
70
71 System.out.println("The value of y : " + domainOne(4) + " when x = 4");
72 System.out.println("The value of y : " + domainTwo(3) + " when x = 3");
73 System.out.println("The value of y : " + domainThree(2) + " when x = 2");
74 System.out.println("The value of y : " + domainFour(1) + " when x = 1");
75 System.out.println("The value of y : " + domainFive(2) + " when x = 2");
76 System.out.println("The value of y : " + domainSix(16) + " when x = 16");
77 System.out.println("*****************");
78 for (int x = 0; x <= 3; x++){
79 System.out.println("The index : " + x + " and the value of set xValue : "
80 + xValue[x]);
81 }
82 System.out.println();
83 System.out.println("The value of y : " + returnRange(0)
84 + " when index of xValue = 0");
85 System.out.println("The value of y : " + returnRange(1)
86 + " when index of xValue = 1");
87 System.out.println("The value of y : " + returnRange(2)
88 + " when index of xValue = 2");
89 System.out.println("The value of y : " + returnRange(3)
90 + " when index of xValue = 3");
91 System.out.println("The value of y : " + returnRange(2)
92 + " when index of xValue = 2");
93
94 }
95 }
Let us check the output:
1 // output of code 5.13
2 The value of y : 4 when x = 4
3 The value of y : 4 when x = 3
4 The value of y : 4 when x = 2
5 The value of y : 4 when x = 1
6 The value of y : 4.0 when x = 2
7 The value of y : 4.0 when x = 16
8 *****************
9 The index : 0 and the value of set xValue : 4.0
10 The index : 1 and the value of set xValue : 3.0
11 The index : 2 and the value of set xValue : 2.0
12 The index : 3 and the value of set xValue : 1.0
13
14 The value of y : 4.0 when index of xValue = 0
15 The value of y : 4.0 when index of xValue = 1
16 The value of y : 4.0 when index of xValue = 2
17 The value of y : 4.0 when index of xValue = 3
18 The value of y : 4.0 when index of xValue = 2
We can see in the above code that the range remains at 4; however, the domain consists more than one values that point to the one output, which is 4. And yes, the domain could have infinite values depending on the permutation and combination of the value of the coefficient.
In some cases, we also need to know how calculus works in computer programming. Consider a car that should have the history of both – velocity and distance. If one is missing,we can calculate the value of the other by using calculus. Therefore, we need to know how to find the velocity from a record of the distance. This part of calculus belongs to differentiation or differential calculus. On the contrary, we also want to compute the distance from a history of the velocity. That is called integration, and it is the goal of integral calculus. We can conclude, differentiation goes from distance to velocity; integration goes from velocity to distance.
However, there is another important factor that we should consider – time. You cannot calculate velocity without time, the rate of speed, etc. At the same time, we also want to know how much time it takes to travel a certain distance. Now, we can guess that from velocity and distance, we can also calculate time.
Let us consider the following code snippet, where we have calculated these factors.
1 // code 5.14
2 // Java
3
4 package fun.sanjibsinha.calculusone;
5
6 public class VelocityClass {
7
8 private float velocity;
9
10 public void setVelocity(int velocity) {
11 this.velocity = velocity;
12 }
13
14 public float getVelocity() {
15 return velocity;
16 }
17
18 public float calculateVelocity(float time, float dis){
19 velocity = dis / time;
20 if((time > 0) && (time < 3)){
21 return velocity;
22 } else if ((time > 3) && (time < 6)){
23 return velocity;
24 } else {
25 return velocity;
26 }
27 }
28 }
29
30
31 package fun.sanjibsinha.calculusone;
32
33 public class DistanceClass {
34
35 private float distance;
36
37 public void setDistance(int distance) {
38 this.distance = distance;
39 }
40
41 public float getDistance() {
42 return distance;
43 }
44
45 public float calculateDistance(float time, float velocity){
46 distance = velocity * time;
47 if((time >= 0) && (time <= 3)){
48 return distance;
49 } else if ((time >= 3) && (time <= 6)){
50 return distance;
51 } else {
52 return distance;
53 }
54 }
55
56
57 }
58
59
60 package fun.sanjibsinha.calculusone;
61
62 public class TimeClass {
63
64 private float time;
65
66 public void setTime(int time) {
67 this.time = time;
68 }
69
70 public float getTime() {
71 return time;
72 }
73
74 public float calculateTime(float distance, float velocity){
75 time = distance / velocity;
76 if((velocity > 0) && (velocity < 10)){
77 return time;
78 } else if ((velocity > 20) && (velocity < 60)){
79 return time;
80 } else {
81 return time;
82 }
83 }
84 }
85
86 package fun.sanjibsinha.calculusone;
87
88 public class DemoClass {
89
90 public static void main(String[] args) {
91 VelocityClass vel = new VelocityClass();
92 TimeClass time = new TimeClass();
93 DistanceClass dis = new DistanceClass();
94 /**
95 * find the velocity from a record of a distance
96 * differentiation
97 * differential calculus
98 */
99 time.setTime(5);
100 dis.setDistance(80);
101 System.out.println("If a car travels " + dis.getDistance() + " kms in "
102 + time.getTime() + " hours, its velocity is "
103 + vel.calculateVelocity(time.getTime(), dis.getDistance()) + " km pe\
104 r hour.");
105
106 System.out.println();
107 /**
108 *compute distance from a history of velocity
109 * integration
110 * integral calculus
111 */
112 time.setTime(10);
113 vel.setVelocity(40);
114 System.out.println("A car with a velocity " + vel.getVelocity() +
115 " kms per hour, in " + time.getTime() + " hours travels "
116 + dis.calculateDistance(time.getTime(), vel.getVelocity()) + " kms."\
117 );
118 /**
119 * we can also time from a history of velocity
120 */
121 dis.setDistance(100);
122 vel.setVelocity(60);
123 System.out.println("A car with a velocity of " + vel.getVelocity() + " kms p\
124 er per hrs, travels" +
125 " distance of " + dis.getDistance() + " kms, hence it will reach the\
126 " +
127 " destination after "
128 + time.calculateTime(dis.getDistance(), vel.getVelocity()) + " hours\
129 .");
130
131 }
132 }
Here is the output:
1 // output of code 5.14
2 If a car travels 80.0 kms in 5.0 hours, its velocity is 16.0 km per hour.
3
4 A car with a velocity 40.0 kms per hour, in 10.0 hours travels 400.0 kms.
5 A car with a velocity of 60.0 kms per per hrs, travels distance of 100.0 kms, hence \
6 it will reach the destination after 1.6666666 hours
Now we are ready to discuss data structures in detail in the next chapter.
I write regularly on Algorithm and Data Structure in
QUIZZ and Challenge on Chapter Five
Question 1: The ‘Collection’ interface has a super-interface – Iterable.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 2: The object is always more powerful than any single primitive data type.
Option 1: False
Option 2: True
Answer: Option 2
========================
Question 3: In Geometry, which concept plays the most vital roles – point,line or plane?
Option 1: Point
Option 2: Line
Option 3: Plane
Option 4: All three described above.
Answer: Option 4
=======================
Question 4: Whenever we declare a fixed length List, the memory manager fixes an amount of memory for that list or array.
Option 1: It is true for a specific programming language.
Option 2: It is true for all programming languages.
Option 3: A few programming languages follow this rule.
Option 4: None of above statement is true.
Answer: Option 2
=======================
Question 5: Growable Lists are dynamic in nature. We can dynamically add any number of elements.
Option 1: True
Option 2: False
Answer: Option 1
=======================
Challenge 1 : How can we reduce the time complexity to big O(square root of n)from big O(n)? Write down different programs to test it.
Solution to Challenge 1:
Language used: Dart
1 //code
2
3 import 'dart:math';
4 void main(){
5
6 // we will find factors of 36
7 // we can add two factors 1 and 36 itself
8 // time complexity is O(n)
9 List<int> numbers = List();
10 for(int i = 1; i <= 36; i++){
11 if(36 % i == 0){
12 numbers.add(i);
13 }
14 }
15 print("${List.from(numbers)}");
16
17 List<int> moreNumbers = List();
18 moreNumbers.add(1);
19 for(int i = 1; i <= 18; i++){
20 if(36 % i == 0){