Ajit Singh - Data Structure and Algorithm: Simply In Depth

Data Structure and Algorithm

Simply In Depth

Copyrighted Material

Copyright 2021-22 by Ajit Singh. All Rights Reserved.

No part of this publication may be reproduced, stored in a retrieval system or transmitted, in any form or by any means electronic, mechanical, photocopying, recording or otherwise without prior written permission from the author, except for the inclusion of brief quotations in a review.

For information about this title or to order other books and/or electronic media, contact the publisher:

Ajit Singh

ajit_singh24@yahoo.com

http://www.ajitvoice.wordpress.in

Acknowledgement

This piece of study of Data Structure & Algorithm is an outcome of the encouragement, guidance, help and assistance provided to me by my colleagues, Sr. faculties, Tech-friends and my family members.

Here, I am taking this opportunity to express my deep sense of gratitude to everybody whose roles were crucial in the successful completion this book, especially to my sr. students. This book benefited from discussions with many IT professionals (Ex-students) over the three years it took me to write it.

My primary goal is to provide a sufficient introduction and details of the Data Structure so that the students can have an efficient knowledge about Data Structure & Algorithm. Moreover, it presupposes knowledge of the principles and concepts. While reading this textbook, students may find the going somewhat tough in spite of my treating the topics in depth but in simple manner. In that case, reread the topic, if still it doesnt do the trick, then only you may need the help of expert. Any remaining errors and inaccuracies are my responsibility and any suggestions in this regard are warmly welcomed !

Special thanks go to my respected elder brother Er. Ranbir Singh, who encouraged me to utilize my skills in timely manner. He was my test audience representing non-technical readers; to the extent this book is accessible to people who aren't already programmers, that's largely his doing.

Last but not the least, I pay my sincere respect and regards to my Mother-In-Law Late Smt. Jayashree Singh and my Daughter whore ever obliged for bearing with me from time to time and insist me to share my knowledge across the world.

I would also like to thank those who provided the odd suggestion via email to us. All feedback was listened to and you will no doubt see some content influenced by your suggestions.

Finally, I would like to thank the Kindle Direct Publishing team and Amazon team for its enthusiastic online support and guidance in bringing out this book.

I hope that the reader likes this book and finds it useful in learning the concepts of Data Structure & Algorithm.

Thank You !!

Preface

Share the knowledge!!

Strong the surroundings........

The study/learning of Data Struture & Algorithm is an essential part of any computer science education and of course for the B.Tech / MCA / M.Tech courses of several Universities across the world. This textbook is intended as a text for an explanatory course of Data Structure & Algorithm for Graduate and Post Graduate students of several universities across the world.

To The Student

This text is an introduction to the complex world of the Data Structure & Algorithm. A key factor of this book and its associated implementations is that all algorithms (unless otherwise stated) were designed by me, using the theory of the algorithm in question as a guideline (for which we are eternally grateful to their original creators). Therefore they may sometimes turn out to be worse than the normal implementationsn and sometimes not.

The book is the result of several decades of teaching experience in data structures and algorithms. The book is self-contained and does not assume any prior knowledge of data structures, just a comprehension of basic programming and mathematics tools generally learned at the very beginning of computer science or other related studies. Through this book I hope that you will see the absolute necessity of understanding which data structure or algorithm to use for a certain scenario. In all projects, especially those that are concerned with performance (here we apply an even greater emphasis on real-time systems) the selection of the wrong data structure or algorithm can be the cause of a great deal of performance pain. The chapters cover: Models of Computation, Lists, Induction and Recursion, Trees, Algorithm Design, Hashing, Heaps, Balanced Trees, Sets Over a Small Universe, Graphs, Strings.

Therefore, it is absolutely key that you think about the run time complexity and space requirements of your selected approach. In this book, I only explain the theoretical implications to consider, but this is for a good reason: Compilers are very diifferent in how they work. One C++ compiler may have some amazing optimisation phases specifically targeted at recursion, another may not, for example. Of course this is just an example but you would be surprised by how many subtle diifferences there are between compilers. These diifferences which may make a fast algorithm slow, and vice versa. We could also factor in the same concerns about languages that target virtual machines, leaving all the actual various implementation issues to you given that you will know your language's compiler much better than me...well in most cases. This has resulted in a more concise book that focuses on what we think are the key issues.

Algorithms in the book are presented in a way that readers can easily understand the method of solving problems. Concepts are illustrated through examples. All programs in the text are tested. All the algorithms in the book are provided in pseudocode, so that students can implement the algorithms in a programming language of their choice.

One final note: never take the words of others as gospel; verify all that can be feasibly verified and make up your own mind. I hope you enjoy reading this book as much as I have enjoyed writing it.

Feedback

I have attempted to wash out every error in my first edition of this book after being reviewed by lots of bachelor of Computer Science, but as happens with Algorithm A few difficult to understand bugs shall remain - and I shall highly welcome the suggestions from the part of students that may lead to improvement of next edition in shortcoming future.

Constructive suggestions and criticism always go a long way in enhancing any endeavour. I request all readers to email me their valuable comments / views / feedback for the betterment of the book at ajit_singh24@yahoo.com mentioning the title and author name in the subject line. Please report any piracy spotted by you as well..I would be glad to hear suggestions from you.

Contents