A Quick Reference to
Data Structures and
Computer Algorithms
By
Raji Ramakrishnan Nair
Divya Joseph
Alen Joseph
FIRST EDITION 2019
Copyright BPB Publications, INDIA
ISBN: 978-93-88176-58-3
All Rights Reserved. No part of this publication can be stored in a retrieval system or reproduced in any form or by any means without the prior written permission of the publishers
LIMITS OF LIABILITY AND DISCLAIMER OF WARRANTY
The Author and Publisher of this book have tried their best to ensure that the programmes, procedures and functions described in the book are correct. However, the author and the publishers make no warranty of any kind, expressed or implied, with regard to these programmes or the documentation contained in the book. The author and publisher shall not be liable in any event of any damages, incidental or consequential, in connection with, or arising out of the furnishing, performance or use of these programmes, procedures and functions. Product name mentioned are used for identification purposes only and may be trademarks of their respective companies.
All trademarks referred to in the book are acknowledged as properties of their respective owners.
Distributors:
BPB PUBLICATIONS
20, Ansari Road, Darya Ganj
New Delhi-110002
Ph: 23254990/23254991
MICRO MEDIA
Shop No. 5, Mahendra Chambers,
DN Rd. Next to Capital Cinema,
V.T. (C.S.T.) Station, MUMBAI-400
Ph: 22078296/22078297
BPB BOOK CENTRE
Old Lajpat Rai Market,
Delhi-110006
Ph: 23861747
DECCAN AGENCIES
4-3-329, Bank Street,
Hyderabad-500195
Ph: 24756967/24756400
Published by Manish Jain for BPB Publications, 20, Ansari Road, Darya Ganj, New Delhi-110002 and Printed by Repro India Pvt Ltd, Mumbai
Dedicated to
My Students
My Strength and My Weakness
A book is a dream that you hold in your hand.
Neil Gaiman
Preface
quick reference to Data Structures and Computer is written in a very simple and understandable manner. The theory is described well with step by step examples. The book gives full understanding of each 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. The book contains lot of figures and this 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.
We have designed this book out of necessity. Right now, references that are available in market in this field, focusses on specific area only. For studying a specific topic, we have to refer minimum of textbooks. That was really hectic and time consuming. Some textbooks focus on programming part, some focusses on algorithms and some focusses on its illustration using figures. Because of all these limitations, we thought to write a book which will satisfy the students in every way. Our book can be a handbook for some, a quick reference for competitive examinations and it can be surely a textbook in any University that offers Computer Science in their curriculum.
This book is useful for all the students of B. Tech, B.E., MCA, BCA, B.Sc. (Computer Science), etc. A student 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 It explains the concepts of blockchain through a different dimension, that is, explaining the data structure aspect of blockchain.
Our book contains seven chapters, focussing from basics of an algorithm to different design strategies. This book also includes different searching and sorting methods.
Chapter 1: Algorithms and This chapter describes the algorithm and the performance analysis of an algorithm Space Complexity and Time Complexity. Explains polynomials and its importance in day to day life. Explains polynomial addition in detail. Gives information related to sparse matrix and its representation in memory. C programs help to understand the implementation easily. Question bank is also provided at the end of the chapter.
Chapter 2: Linked Lists: Here focus is given on the linked list implementations. Different types of linked lists have been discussed with its various operations. Diagrammatic representation of each operation helps to understand the working concept effectively. Static and dynamic representation of single linked list is well explained here. Doubly linked lists with its operations are well explained here. Programmes are given for different linked list operations. Question bank at the end of chapter helps to practice the concept well for future references.
Chapter 3: Stacks and Queues: This chapter deals with the data structure used for specific situations, i.e., when we want to have insertion and deletion operation at only one place or when we want to perform insertion operation at one end and deletion operation at another end. Here we are focussing on the different memory representations of stacks and queues. Different operations of stacks are discussed well here. Applications of stack are well explained in this chapter. C programmes included help to understand the concept effectively. Different types of queues are also explained here. Question bank is provided at the end of the chapter help to refer in future.
Chapter 4: Trees and Graphs: This chapter includes basic concepts related to trees. It focusses on different types of trees, especially binary tree concepts. Helps to understand the representation of binary tree in memory. Explains the different types of traversals available. Explains the different operations on binary trees. Other than this, introduces the concept of B and B+ trees. Explains the height balanced trees well. Also helps to understand the concept of graphs, with its various ways of representation in memory. Gives a good idea on graph traversals with proper explanation. Question bank is also provided at the end of each chapter.
Chapter 5: Searching and Sorting: This chapter deals with the Divide and Conquer strategy. Mainly focusses on the different searching and sorting methods available. Many of the methods have been explained well with suitable examples. Question bank is also provided at the end of each chapter.
Chapter 6: The Greedy Method: Here the concept of greedy method is well explained. Two algorithms are effectively explained and they are the Kruskals algorithm and the Prims algorithm. Question bank is provided at the end of the chapter.
Chapter 7: Beauty of Blockchain: This chapter goes through Blockchain a real application of data structure; we are trying to bring curiosity to students about the disruptor technology which they are going to get hands-on experience in the near future. It is the difficult topic but we have tried to make it easier. First of all, we explained the origin of the Blockchain, clarify the dilution regarding Blockchain and cryptocurrency. Then the elements and jargons of Blockchain are discussed. We jump deeper explaining Blockchain terminology with use cases. After that, we go into different types of Blockchain, how to implement them and their different use cases. We concluded by explaining the advantages and disadvantages of Blockchain along with its future.