Tags

, , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

We have already been introduced to data structures before. Of course, we have learned a few operations using Array in various languages, so we can say that the concept of data structures is not completely alien to us.
We need a good way to store, organize and use our data. As times passes by, the nature of data is becoming not only more and more complex, but also it’s getting bigger in quantity. More and more people are getting hooked to the Internet, exchanging huge amount of data every day, in various forms; scientific data are getting larger, we need weather data to be processed to get more accurate weather prediction, medical data are becoming humongous; this list is endless.
Therefore, we need more efficient way to sort, organize, and use that data.
Data Structures are all about this. It has a very close relation with Algorithm, because managing such huge amount of data is less tedious if we have more efficient Algorithm, ready at our hand.While managing such huge humongous data, by sorting, organizing, or using them, one is not only prone to error, but also fail to satisfy one of the most important requirements – time and space. Yes, time complexity really matters, so the space.


In this section we have a short introduction to the Data Structures, and algorithm.

We can describe our data structures in our natural language; that is a part of any data structures. It is always good to write it down what we are going to do with our data structures.
Consider a static List or a fixed length List; that is, an array. It is a collection of similar type of data, either integer, double, or string. Moreover, it should have a fixed length while we declare it. Within that range of length, we can insert data, modify data at a specific position, even we can remove a data and make the memory space empty.
Whenever we declare a fixed length List, the memory manager fixes an amount of memory for that list or array. When we write, “int array[4]”, it means, memory manager allocates 4 bytes each for individual address, altogether 16 bytes are allocated.
In language like C or C++, if we want to insert one more data, in whatever position we can imagine; the task becomes tedious. First of all, the memory manager has already fixed a space. So we need to create a larger array. Copy the whole array to the new memory space and at the same time empty the old space.
To make an array dynamic, we might think an array with maximum size that particular data type allows us to use. Since the array is a contiguous block of memory, a large space remains unused. Suppose we declare an array of ‘n’ length. We start with 10 data. Next, as per our need we start adding data to the array. If we add one single data at the very beginning, we need to shift all other data by one space. If the data type is integer, we need not add 4 bytes more at the end in this case particularly because we have kept that space beforehand, after that we need to shift the other data accordingly.
Whatever we do, a large space still remains unused. In terms of memory allocation, this process does not seem friendly.
Since the length of an array is fixed, it works on a constant time.
Now, new languages come up to solve the limitations of older language. Consider the Dart. In Dart, we get two types of List. One is of traditional type – fixed length. Another is growable or dynamic List.
Enough talking, let us see the first code – fixed length List.

// code 
// Dart



/*
The list is a simple ordered group of objects. Creating
a List seems easy because Dart core libraries have the necessary support
and a List class. There are two types of Lists.
*/
void main(){
listFunction();
}



int listFunction(){
List nameOfTest = List(3);
nameOfTest[0] = 1;
nameOfTest[1] = 2;
nameOfTest[2] = 3;
//there are three methods to capture the list
//1. method
for(int element in nameOfTest){
print(element);
}
print("-----------");
//2. method
nameOfTest.forEach((v) => print('${v}'));
print("-----------");
//3. method
for(int i = 0; i < nameOfTest.length; i++){
print(nameOfTest[i]);
}
}

The output is quite expected.

// output of code 5.11
1
2



3



1
2



3



1
2
3

In Dart, everything is object. Therefore, it is a collection of similar objects. Here it is integer. Next, we will make this list dynamic, and see how it works.

// code 5.12
// Dart



void main(){
growableList();
}



Function growableList(){
//1. method
List names = List();
names.add("Mana");
names.add("Babu");
names.add("Gopal");
names.add("Pota");
//there are two methods to capture the list
print("-----------");
//1. method
names.forEach((v) => print('${v}'));
print("-----------");
//2. method
for(int i = 0; i < names.length; i++){
print(names[i]);
}
}

Growable Lists are dynamic in nature. We can dynamically add any number of elements
and we can also remove it by a simple method: ‘names.remove(“any name”)’. We can also use the key; as this ordered list starts from 0. So we can remove the first name just by passing this key value: ‘names.removeAt(0)’. We use the ‘removeAt(key)’ method for that operation. We can also clear the whole List just by typing: ‘names.clear()’.
Let us see the output, now.

// output of code 5.12



Mana
Babu
Gopal



Pota



Mana
Babu
Gopal
Pota

We have a very short introduction to Data Structures. Hopefully, now we understand what are the limitations and advantages of an array. We will discuss them in detail in the first section of the next chapter 6. Comparing array with other Data Structures will help us gain more insights into this complex topic, which is the most fundamental block of Computer Science.