Quick Reference to Data Structures and Computer Algorithms, A

An Insight on the Beauty of Blockchain

Divya Joseph

• Publisher: BPB Publications
• Year: 2019
• ISBN:
  9789388176583
• Topic: Ciencia de la computación
• Subtopic: Algoritmos de programación

For beginners to level up Core Programming Skills Key Features

• Simple and easy to understand.
• Useful for any level of students including B.E., BTech, MCA, BCA, B.Sc. (Computer Science), etc.
• Algorithms used in the book are well explained and illustrated step by step.
• Help students in understanding how data structures are implemented in programs.
• Each module contains question bank which includes questions for competitive examinations like UGC-NET, placement drives, and so on.

Description
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. What Will You Learn

• New features and essential of Algorithms and Arrays.
• Linked List, its type and implementation.
• Stacks and Queues
• Trees and Graphs
• Searching and Sorting
• Greedy method
• Beauty of Blockchain

Who This Book Is For
This book is useful for all the students of B. Tech, B.E., MCA, BCA, B.Sc. (Computer Science), and so on. Person with basic knowledge in this field can understand the concept from the beginning of the book itself.
We think our book is one of a kind. We are trying to connect the past and the present here. The last module of our book is focussing on BLOCKCHAIN. It explains the concepts of blockchain through a different dimension, that is, explaining the data structure aspect of blockchain. Table of Contents

• Algorithm and Arrays
• Linked Lists
• Stacks and queues
• Trees and Graphs
• Searching and Sorting
• Greedy Method
• Beauty of Blockchain
• About the Author
  Raji Ramakrishnan Nair, has done BCA, MCA and M. Tech (IT) and currently working as an Assistant Professor at the P. G. Department of Computer Applications of Marian College Kuttikkanam (Autonomous). She has 14 years of teaching experience and believes that teaching is all about being 'friend, philosopher and guide' to her students. This book is inspired by her passion to simplify complex subjects for easy understanding; the real contribution of a great teacher. She is a philanthropist as well, actively involved in many social causes, which made her students to engage in relief works in Kerala mega flood and resulted in two houses being built for flood victims. LinkedIn Profile: linkedin.com/in/raji-ramakrishnan-nair-8820b1171 Divya Joseph, is a Teacher by passion and profession. She has done MTech (CSE) and BTech (IT) from Amal Jyothi College of Engineering, Kanjirapally. Presently, she is working as an Assistant Professor in the P.G. Department of Computer Applications, Marian College Kuttikkanam (Autonomous). Alen Joseph, is an Associate Software Developer at UST Global Trivandrum. His great passion for teaching and research motivated him to write this book. He has done MCA from Marian College Kuttikkanam (Autonomous). He is a passionate tech enthusiast and his dream is to become a full-time researcher.
  

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.	Input: An algorithm must be provided with zero or more inputs externally.
2.	Output: At least one output must be obtained.
3.	Definiteness: Every step of the algorithm should be unambiguous.
4.	Finiteness: The execution of the algorithm must terminate after a finite number of steps.
5.	Effectiveness: Every instruction must be very basic, so that any layman can understand the principle, using only pencil and paper.

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:

Characteristic	Description
Linear	Here, the data items are arranged in a linear sequence. For example, array.
Non-Linear	Here, the data types are not in sequence. For example, tree, graph.
Homogeneous	Those data structures, where all the data elements are of same type, are known as homogeneous data structures. For example, array.
Non-homogeneous	Those data structures, where data elements, may or may not be of the same data type, are known as non – homogeneous data structures. For example, structures.
Static	Data structures, whose sizes and structures, associated to memory locations, are fixed during compile time, are known as static data structures. For example, array.
Dynamic	Data structures, whose sizes and structures, associated to memory locations, can be expanded or shrunk, while execution, are known as dynamic data structures. For example, linked list created using pointers.

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 ...