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