A Quick Reference to Data Structures and Computer Algorithms: An Insight on the Beauty of Blockchain

By Divya Joseph

The book gives full understanding of theoretical topic and easy implementation in programming. The book is going to help students in self-learning of data structures and in understanding how these concepts are implemented in programs. It contains lot of figures, which will help students to visualize the concept effectively. Diagrams help students to understand how the programs involving data structure concepts are implemented within the computer system.
Algorithms are included to clear the concept of data structure. Each algorithm is explained with figures to make student clearer about the concept. Sample data set is taken and step by step execution of algorithm is provided in the book to ensure the in – depth knowledge of students about the concept discussed

• Language: English
• Publisher: BPB Online LLP
• Release date: Jul 10, 2019
• ISBN: 9789389328103

Book preview

MODULE I

Algorithms and Arrays

CHAPTER 1

Algorithms and Arrays

1.1 Introduction

An algorithm is defined as a finite set of instructions, which when executed in an order, accomplishes a predefined task. Algorithm is actually the core logic of a problem, rather than the complete code or program. We can express an algorithm, either as an informal high-level description as pseudo code or using a flowchart.

Each algorithm has the following properties:

1.2 Basic Concepts – Data Structures and Types of Data Structure

Data can be organized in many ways and one of the ways is data structures. It is mainly used to represent data in the memory of the computer, so that, data can be retrieved effectively later. The idea behind the concept of data structure is to reduce the space and time complexities of different tasks.

1.2.1 Data Type

There are various types of data available such as integer, string, and so on. To classify these available types of data, we use data type, which determines the values that can be used as well as the type of operations that can be performed on the corresponding type of data. Basically, there are two data types:

Built – in Data Type

Derived Data Type

Built-in Data Type

When any programming language provides built – in support for any data type, then such type of data types is known as built – in data type. For example, the following built – in data types are provided by most of the programming languages – integers, boolean (TRUE or FALSE), floating (Decimal Numbers), characters, and strings.

Derived Data Type

Those data types which are implemented independently in one or the other way, are known as derived data types. These are mainly the combination of primary or built – in data types and associated operations on them. For example, list, array, stack, queue, and so on (figure 1.1).

Figure 1.1 Classification of Data Structure

The data structures can also be classified on the basis of the following characteristics:

1.3 Performance Analysis of an Algorithm

If we want to buy a television, there are many brands available in market. But, we have a fixed amount of money in hand as well as fixed amount of space to place this television at home. So, while deciding which television to buy, we have to go through almost all brands available in market, keeping three factors in mind, price, space, and performance. Depending on the availability and convenience, we choose the one which suits us. Similarly, in Computer Science, multiple algorithms are available to solve a particular problem. When we have more than one algorithm to solve a single problem, then we need to select the best one. Thus, performance analysis helps us to select the best algorithm from multiple algorithms to solve a problem.

When there are multiple alternative algorithms to solve a problem, we have to analyse each of them and select the best option suitable for our requirements.

Formal definition is as follows:

Performance of an algorithm is a process of making evaluative judgment about algorithms.

It can also be defined as follows:

Performance of an algorithm means estimating the resources which are required to an algorithm to perform its task.

When we have multiple algorithms to solve a particular problem, then we have to select the best one suitable for the specified problem.

For that, we compare all available algorithms, with each other which are meant to solve the specified problem, to select the best algorithm. For comparison, we use a set of parameters or set of elements, which includes, memory required by that algorithm, execution speed of that algorithm, memory space requirement of that algorithm, easy to understand, easy to implement, and so on.

Normally, the performance of an algorithm depends on the following elements:

The analysis of an algorithm, considers only the space and time required by that algorithm and thus, ignores all remaining elements.

 Based on this information, performance analysis of an algorithm can also be defined as follows:

Performance analysis of an algorithm is the process of calculating space required by that algorithm and time required by that algorithm.

Performance analysis of an algorithm is performed by using the following measures:

1.3.1 Space Complexity

The space complexity of any algorithm mainly comprises of program space and data space. The space needed by each algorithm is mainly the sum of the following components:

Therefore, the total space requirement of any algorithm ‘A’ can be provided as:

Space (A) = Fixed components (A) + Variable Components (A)

When comparing the components, the most important part is the variable part, so it must be determined accurately, so the actual space requirement can be calculated for an algorithm ‘A’.

Let us take some examples and understand how to find the space complexity of any given algorithm.

Example 1

Algorithm add (x, y)

{

return x + y;

}

We know, space complexity of any algorithm is determined using the following formula:

Space [s] = Fixed part + Variable part

In our example, we find that there is no variable part, so the memory space needed for variable part is zero. Let us assume that, one word of memory is needed for each variable used in this algorithm. So, total two memory words needed to store the values of x and y.

Thus, S [add] = 2.

Example 2

Algorithm add (a, n)

{

S: = 0.0;

for i: = 1 to n do

S: = S + a [i];

return S;

}

Here in this example, three variables are used and they are s, i, and n. Assuming that one memory word is needed to store the value of each variable, then we require total of 3 memory words to store the values of s, i, and n. Here, we have one array also and the size of the array is completely depending upon the value of n, so array can be expanded or get reduced according to the value of n. So, the space requirement of array ‘a’ is n.

Therefore,

Space complexity (add) = 3 + n

= (n + 3) [n words for a[ ], one each for n, i, and s]

Example 3

Algorithm RecSum(a, n)

{

if (n £ ) then return 0.0;

Else

return RecSum(a, n-1) + a[n];

}

Let us solve this example with some data sets. Here our array is ‘a’ and let the size of n = 3. So, the pictorial representation of this array is as follows:

And suppose the values in a[1], a[2], and a[3] are 10, 20, and 30 respectively. So, array look like the following:

When the algorithm RecSum(a,n) is invoked by operating system, the stack representation is as follows:.

Here, we have n = 3, as assumed earlier.

When execution starts, the if condition is being checked and we found it is wrong, so else part is being executed and it returns RecSum(a, 2) + a[3], that means, return RecSum (a, 2) + 30, and the next function call is RecSum(a, 2) and so the stack representation is as follows:

Now, function RecSum(a, 2) is being executed and the if condition is being checked and we found it is false, so else part is being executed and it returns RecSum(a, 1) + a[2], that means, return RecSum(a, 1) + 20, and the next function call is RecSum(a, 1) and so the stack representation is as follows:

When execution for function RecSum(a, 1) starts, the if condition is being checked and we found it is false, so the else part is being executed and it return RecSum(a, 0) + a[1], that means return RecSum(a, 0)+10 and the next function call is RecSum(a, 0) and so the stack representation is as follows:

Now, function RecSum(a, 0) is being executed and the if condition is being checked and we found it is true and hence it return zero for this function call.

Let us see how return function returns in the whole program and it is shown pictorially as follows:

Assume that the return address requires only one word of memory, so, each call to RecSum requires at least three words, which includes space for the value of n, the return address and a pointer to a[ ].

Here, we can see the depth of the recursion stack is 3 + 1 (where 3 is the value of n that we assumed earlier). And, we know, for each call to RecSum requires 3 words, so for this algorithm, the recursion stack needed is as follows:

So, in general, we can state that, the recursion stack space

needed is ≥ 3(n + 1)

Note: The space requirement S(P) of any algorithm P may therefore be written as

S(P) = c + S p (instance characteristics), where ‘c’ is a constant.

For analysing the space complexity of an algorithm, we have to give importance on estimating Sp (instance characteristics). This is very problem specific. So, for any given problem, we need to identify which instance characteristics to use to estimate the space requirements.

1.3.2 Time Complexity

Time complexity of any algorithm gives the total amount of time needed for that algorithm to complete its task. The time T(P) taken by a program is mainly the sum of the compile time and the run time (execution time). Time complexity of any algorithm depends on many things like hardware part of the system, operating system, processors, and so on. But, to calculate the time complexity of an algorithm, we will only consider the run time (execution time) of an algorithm.

The main factor in determining the time complexity of an algorithm is the run time of that algorithm. The compile time of an algorithm doesn’t depend on the instance characteristics. And also, once a program is compiled, there is no need to recompile the same program for its every execution. The run time of an algorithm depends on the instance characteristics, so time complexity of an algorithm is very program specific. This run time is denoted by tp.

The time complexity of any algorithm is calculated by finding the total number of program steps involved to complete its task. A program step is loosely defined as a segment of a program, that has an execution time, but is independent of instance characteristics.

The total number of program steps of any program depends upon the type of statement. For example, if the statement is a comment, then the program step associated with such statement is zero step, an assignment statement is counted as one step, and for an iterative statement such as for, while, and repeat-until statements, the program step depends upon the number of times the control part executes.

Now we have to find the number of steps needed by a program to solve a particular problem in any one of the two ways available. In the first method, we have a global variable COUNT, initialized to 0. Statements to increment COUNT by the appropriate amount are introduced into the program. This is done so that each time a statement in the original program is executed COUNT is incremented by the step count of that statement.

Let us take an example. Following is the algorithm with COUNT statements added.

Algorithm 1.1 Algorithm with COUNT statements added

In algorithm 1.1, the change in the value of COUNT by the time this program terminates is the number of steps executed by this algorithm. To find the number of steps for algorithm 1.1, we find the total number of COUNT. We can see that, for each statement in the program, the COUNT is increased by 1. For the statements 3 and 13, the COUNT is increased by 1. In the for loop, for each entry into the loop, the COUNT is incremented by 1. So, we can see COUNT increment twice in the for loop. At the time of exit for for loop, COUNT is incremented once. So, when we go through the algorithm, we can find 2 increments for COUNT in for loop and outside invocation of add (Algorithm 1.1) executes a total of 2n + 3 steps.

Let us take another example, where recursive function is used.

Algorithm 1.2 Algorithm with count added

The algorithm 1.2, is divided into two parts: IF part and ELSE part. We are getting into the IF part, only when the condition mentioned is true, otherwise statements in the ELSE part will get executed. Let t RecSum (n) be the increase in the value of COUNT when algorithm 1.2 terminates. We know that t RecSum (0) = 2. When n>o, COUNT increases by 2 plus whatever increase results from the invocation of RecSum from within the ELSE clause. The additional increase is because of t RecSum (n-1). So, if the value of COUNT is zero, initially, its value at the time of termination is 2 + t RecSum (n-1), n>o.

When analysing a recursive program for its step count, we often obtain recursive formula for the step count, as shown below:

tRecSum (n) = 2 if n = 0

   2 + tRecSum (n – 1) if n > 0

These recursive formulas are referred to as recurrence relations. One way of solving any recurrence relation is to make repeated substitutions for each occurrence of the function tRecSum on the right-hand side until all such occurrences disappear:

So, the step count for RecSum is 2n