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