Data Structures with Python Get familiar with the common Data Structures and Algorithms in Python (Dr. Harsh Bhasin) (z-library.sk, 1lib.sk, z-lib.sk)

 i Data Structures with Python Get familiar with the common Data Structures and Algorithms in Python Dr. Harsh Bhasin www.bpbonline.com

ii  Copyright © 2023 BPB Online All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews. Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor BPB Online or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book. BPB Online has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, BPB Online cannot guarantee the accuracy of this information. First published: 2023 Published by BPB Online WeWork 119 Marylebone Road London NW1 5PU UK | UAE | INDIA | SINGAPORE ISBN 978-93-55513-304 www.bpbonline.com

 iii Dedicated to My mother

iv  About the Author Dr. Harsh Bhasin is a researcher and practitioner. Dr. Bhasin is currently associated with the Center of Health Innovations, Manav Rachna Institutions. Dr. Bhasin has completed his Ph. D. in Mild Cognitive Impairment from Jawaharlal Nehru University, New Delhi. He worked as a Deep Learning consultant for various firms and taught at various Universities including Jamia Hamdard and DTU. He has authored 11 books including Programming in C#, Oxford University Press, 2014; Algorithms, Oxford University Press, 2015; Python for Beginners, New Age International, 2018; Python Basics, Mercury, 2019; Machine Learning, BPB, 2020, to name a few. Dr. Bhasin has authored 40 papers published in renowned journals including Alzheimer’s and Dementia, Soft Computing, BMC Medical Informatics & Decision Making, AI & Society, etc. He is the reviewer of a few renowned journals and is the editor of a few special issues. He is a recipient of a distinguished fellowship. His areas of expertise include Deep learning, Algorithms, and Medical Imaging. Outside work, he is deeply interested in Hindi Poetry: the progressive era, and Hindustani Classical Music: percussion instruments.

 v About the Reviewer Sumeet Lalla has done his masters of Data Science from Higher School Of Economics Moscow and Bachelors of Engineering in Computer Engineering from Thapar University. He also has 6 years of experience in Data Science and Software Engineering. His career graph includes working as a Data Scientist in Cognizant and as a Software Developer in Siemens Technology, along with working in Services and Technology Analyst in Deloitte Consulting and Pvt Ltd.

vi  Acknowledgement “Feeling gratitude and not expressing it is like wrapping a present and not giving it.” – William Arthur Ward I am blessed to have met people who encouraged me to learn continuously. First of all, I would like to thank Professor Moin Uddin, former Pro-Vice-Chancellor, Delhi Technological University for his unconditional support. He has deposed his faith in me when no one else did. Had it not been for his encouragement I would not have been able to achieve whatever I did. I would also like to thank Professor I. K. Bhat, Vice Chancellor, Manav Rachna University, India; and Professor Sameer Singh, Rail Vision, United Kingdom; for their continuous support and encouragement. I would also like to express my sincere gratitude to the late Professor A. K. Sharma, former Dean, and Chairperson, the Department of Computer Science, YMCA, Faridabad, for his constant encouragement. I have been able to write this book, author papers, and work on projects only because of the encouragement provided by him. I would also like to thank Professor Naresh Chauhan, former Head and Chairperson, Department of Computer Science, YMCA University of Science and Technology, and Dr. S. K. Pal, Scientist, Department of Defence and Research Organization, Govt. of India for their constant support. I am thankful to Mr. Nishant Kumar, NCU, India, for his contribution to editing, formatting, and developing some programs for this book. I would also like to thank my students and colleagues, for their critical reviews. I am also very thankful to the editorial team of BPB Publications for providing valuable assistance. I would like to express my sincere gratitude to my Mother, Sister, and the rest of the family including my pets: Zoe & Xena, and friends for their unconditional support to me. I would be glad to receive your comments or suggestions which can be incorporated into future editions of the book.

 vii Preface This book introduces the reader to Data Structures and Algorithms, the foundation stone of programming. The concepts discussed in this book will help the reader to understand various data structures, analyze the time and space complexity, and use these data structures for solving graded problems. The first chapter introduces the reader to the fascinating world of Algorithms and Data Structures. The idea of complexity has been introduced in the chapter. It contains ample examples of finding the complexity of a given algorithm. The next chapter takes the reader through various approaches to developing algorithms. The chapter introduces the Greedy approach, divide and conquer, dynamic programming, and backtracking. An introduction to branch and bound has also been included in the chapter. Recursion has been introduced in the third chapter of this book. The chapter contains the mechanism, examples, and the process of finding the complexity of a recursive algorithm. The problems related to arrays have been discussed in the fourth chapter of this book. It presents insertion, deletion, and searching in arrays along with the complexities. Chapter 5 discusses Linked Lists. The algorithms, complexity, and problems of linked lists have been covered in this chapter. This chapter forms the basis of the following chapters. The next two chapters introduce stacks and queues. The applications of these data structures have also been included in the chapters. These chapters contain assorted problems related to stacks and queues. Chapters 8 and 9 deal with trees and heaps. The insertion and deletion in binary trees and other algorithms have been included in these chapters. Chapter ten introduces priority queues. The next chapter discusses graphs. It contains traversal algorithms, spanning tree algorithms, and shortest path algorithms. Chapter 11 contains eleven sorting techniques and discusses the related problems. selection has been dealt with in the next chapter. A very efficient searching technique called hashing has been explained in detail in the fourteen chapters. The last chapter deals with the String algorithms. The book also contains four appendices containing Dijkstra's algorithm, all pairs' shortest path, and tree traversals using stacks and problems.

viii  Coloured Images Please follow the link to download the Coloured Images of the book: https://rebrand.ly/6rz6cpm We have code bundles from our rich catalogue of books and videos available at https://github.com/bpbpublications. Check them out! Errata We take immense pride in our work at BPB Publications and follow best practices to ensure the accuracy of our content to provide with an indulging reading experience to our subscribers. Our readers are our mirrors, and we use their inputs to reflect and improve upon human errors, if any, that may have occurred during the publishing processes involved. To let us maintain the quality and help us reach out to any readers who might be having difficulties due to any unforeseen errors, please write to us at : errata@bpbonline.com Your support, suggestions and feedbacks are highly appreciated by the BPB Publications’ Family. Did you know that BPB offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.bpbonline.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at : business@bpbonline.com for more details. At www.bpbonline.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on BPB books and eBooks.

 ix Piracy If you come across any illegal copies of our works in any form on the internet, we would be grateful if you would provide us with the location address or website name. Please contact us at business@bpbonline.com with a link to the material. If you are interested in becoming an author If there is a topic that you have expertise in, and you are interested in either writing or contributing to a book, please visit www.bpbonline.com. We have worked with thousands of developers and tech professionals, just like you, to help them share their insights with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea. Reviews Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions. We at BPB can understand what you think about our products, and our authors can see your feedback on their book. Thank you! For more information about BPB, please visit www.bpbonline.com. Join our book's Discord space Join the book's Discord Workspace for Latest updates, Offers, Tech happenings around the world, New Release and Sessions with the Authors: https://discord.bpbonline.com

x  Table of Contents 1. Introduction to Data Structures ................................................................................ 1 Structure .................................................................................................................. 2 Objectives ................................................................................................................ 2 Introduction ............................................................................................................ 2 Data types ............................................................................................................... 3 Types of data structures ........................................................................................ 4 Game of clones ....................................................................................................... 6 The game of clones revisited .............................................................................. 10 Conclusion ............................................................................................................ 12 Multiple choice questions ................................................................................... 12 Theory-based questions ...................................................................................... 14 Application-based questions .............................................................................. 15 2. Design Methodologies ............................................................................................. 17 Structure ................................................................................................................ 18 Objectives .............................................................................................................. 18 Greedy approach ................................................................................................. 19 Divide and conquer ............................................................................................. 20 Backtracking and dynamic programming ....................................................... 21 Longest common sub-sequence ......................................................................... 24 Conclusion ............................................................................................................ 30 Multiple choice questions ................................................................................... 30 Programming/application ................................................................................. 32 Further references ................................................................................................ 34 3. Recursion .................................................................................................................... 35 Structure ................................................................................................................ 36 Objectives .............................................................................................................. 36 Exponentiation ..................................................................................................... 36 Tower of Hanoi..................................................................................................... 38

 xi Rabbit problem ..................................................................................................... 41 Generating binary numbers ............................................................................... 44 Lists ........................................................................................................................ 47 Numbers ............................................................................................................... 48 Conclusion ............................................................................................................ 49 Multiple choice questions ................................................................................... 50 Programming ...................................................................................................... 51 Further references ................................................................................................ 53 4. Arrays ........................................................................................................................... 55 Structure ................................................................................................................ 55 Objectives .............................................................................................................. 56 Introduction .......................................................................................................... 56 Memory map .................................................................................................... 58 Address in column-major ................................................................................... 58 Inserting and deleting ......................................................................................... 59 Operations on arrays ........................................................................................... 67 Linear search .................................................................................................... 68 Problems................................................................................................................ 70 Conclusion ............................................................................................................ 75 Multiple choice questions ................................................................................... 76 Programming ...................................................................................................... 77 5. Linked List .................................................................................................................. 79 Structure ................................................................................................................ 79 Objectives .............................................................................................................. 80 One-way linked list ............................................................................................. 80 Traversing ............................................................................................................. 80 Insertion and deletion ......................................................................................... 81 Two-way linked list ............................................................................................. 90 Traversing ............................................................................................................. 91 Insertion and deletion ......................................................................................... 91 Cyclic list ............................................................................................................... 96

xii  Stacks and Queues ............................................................................................... 96 Reversing a linked list ......................................................................................... 99 Concatenate lists ................................................................................................ 100 Check cycle ......................................................................................................... 101 Conclusion .......................................................................................................... 101 Multiple choice questions ................................................................................. 102 Theory ................................................................................................................. 103 Problems.............................................................................................................. 104 6. Stacks ......................................................................................................................... 107 Structure .............................................................................................................. 108 Objectives ............................................................................................................ 108 Introduction ........................................................................................................ 108 Implementing two stacks using a single list .................................................. 114 Types and uses ................................................................................................... 116 Reversing a string .............................................................................................. 117 Expressions ......................................................................................................... 117 Evaluation of postfix ...................................................................................... 118 Infix to postfix ................................................................................................ 120 Infix to prefix.................................................................................................. 126 Problems.............................................................................................................. 129 Conclusion .......................................................................................................... 132 Multiple Choice Questions ............................................................................... 133 Problems.............................................................................................................. 136 7. Queues ....................................................................................................................... 139 Structure .............................................................................................................. 139 Objectives ............................................................................................................ 140 Introduction ........................................................................................................ 140 Algorithm and implementation ....................................................................... 142 Circular queue .................................................................................................... 146 Doubly-ended queue: DEQueue ..................................................................... 149 Generating binary numbers using a queue ................................................... 152

 xiii Stack using two queues .................................................................................... 155 Stack from a single queue ................................................................................. 156 Scheduling .......................................................................................................... 159 Conclusion .......................................................................................................... 160 Multiple Choice Questions ............................................................................... 160 Problems.............................................................................................................. 163 8. Trees-I ........................................................................................................................ 165 Introduction ........................................................................................................ 165 Structure .............................................................................................................. 166 Objectives ............................................................................................................ 166 Definition and terminology .............................................................................. 166 Representation of a Binary Tree ....................................................................... 169 Traversal .............................................................................................................. 171 Post-order traversal ............................................................................................. 174 Pre-order traversal............................................................................................... 176 Binary search tree............................................................................................... 178 Insertion in a BST ............................................................................................... 180 Deletion ............................................................................................................... 185 Leftmost node ...................................................................................................... 188 Rightmost node .................................................................................................... 188 Conclusion .......................................................................................................... 192 Multiple choice questions ................................................................................. 192 Numerical/problems ........................................................................................ 194 9. Trees-II ....................................................................................................................... 197 Structure .............................................................................................................. 198 Objectives ............................................................................................................ 198 AVL trees ............................................................................................................. 198 Insertion .............................................................................................................. 199 Deletion ............................................................................................................... 200 Insertion in an AVL tree .................................................................................... 200 Deletion from an AVL Tree.................................................................................. 209

xiv  B Trees .................................................................................................................. 219 Conclusion .......................................................................................................... 225 Multiple choice questions ................................................................................. 225 Theory ................................................................................................................. 228 Numericals .......................................................................................................... 228 10. Priority Queues ........................................................................................................ 231 Structure .............................................................................................................. 231 Objectives ............................................................................................................ 232 Introduction to priority queues ....................................................................... 232 Structure of heap ............................................................................................ 232 Operations ..................................................................................................... 234 Inserting an element in a heap ......................................................................... 234 Deletion ............................................................................................................... 240 Heap sort ............................................................................................................. 243 Problems.............................................................................................................. 246 Conclusion .......................................................................................................... 247 Multiple choice questions ................................................................................. 248 Programming .................................................................................................... 249 Further references .............................................................................................. 250 11. Graphs ....................................................................................................................... 251 Introduction ........................................................................................................ 251 Structure .............................................................................................................. 252 Objectives ............................................................................................................ 252 Representation ................................................................................................... 252 Traversals ............................................................................................................ 256 Depth First Search ............................................................................................. 256 Breadth First Search ...................................................................................... 262 Topological sort .............................................................................................. 266 Spanning tree ...................................................................................................... 270 Kruskal’s algorithm ........................................................................................... 271 Conclusion .......................................................................................................... 274

 xv Multiple choice questions ................................................................................. 274 Numerical/application based .......................................................................... 277 Programming ..................................................................................................... 280 12. Sorting ....................................................................................................................... 281 Structure .............................................................................................................. 282 Objectives ............................................................................................................ 282 Bubble sort .......................................................................................................... 282 Comb sort ............................................................................................................ 286 Selection sort....................................................................................................... 289 Insertion sort....................................................................................................... 291 Radix sort ............................................................................................................ 292 Counting sort ...................................................................................................... 295 Merge and merge sort ....................................................................................... 296 Partition and quick sort .................................................................................... 301 Conclusion .......................................................................................................... 304 Illustrations ......................................................................................................... 305 Multiple choice questions ................................................................................. 308 Theory ................................................................................................................. 311 13. Median and Order Statistics ................................................................................. 313 Introduction ........................................................................................................ 313 Structure .............................................................................................................. 313 Objectives ............................................................................................................ 314 Introduction to median and order statistics .................................................. 314 Median of medians ............................................................................................ 315 Median using heaps .......................................................................................... 318 Median using insertion sort ............................................................................. 323 Median using partition ..................................................................................... 323 Conclusion .......................................................................................................... 325 Solved problems ................................................................................................ 325 Multiple choice questions ................................................................................. 328 Applications/implementation ......................................................................... 330

xvi  Bibliography ....................................................................................................... 330 14. Hashing ..................................................................................................................... 333 Structure .............................................................................................................. 333 Objectives ............................................................................................................ 334 Hash tables ......................................................................................................... 334 Storing information ........................................................................................... 335 Sorted sequential array .................................................................................. 335 Linked list representation .............................................................................. 336 AVL trees ....................................................................................................... 336 Hashing ............................................................................................................... 337 Hash function ................................................................................................ 338 Collision resolution ........................................................................................ 338 Selecting hash function .................................................................................. 338 Collisions ............................................................................................................. 339 Collision resolution ........................................................................................... 340 Linear probing ................................................................................................ 340 Quadratic probing ......................................................................................... 342 Separate chaining ........................................................................................... 344 Solved problems ................................................................................................ 345 Conclusion .......................................................................................................... 348 Multiple choice questions ................................................................................. 349 Theory ................................................................................................................. 351 Problems.............................................................................................................. 351 Programming ..................................................................................................... 351 15. String Matching ....................................................................................................... 353 Structure .............................................................................................................. 353 Objectives ............................................................................................................ 354 Introduction to string-matching ...................................................................... 354 Brute force method ............................................................................................ 354 Rabin Karp .......................................................................................................... 355 Knuth–Morris–Pratt algorithm ........................................................................ 359

 xvii KMP method ...................................................................................................... 363 Conclusion .......................................................................................................... 367 Multiple choice questions ................................................................................. 367 Theory/applications ......................................................................................... 369 Find errors/special cases ................................................................................. 369 References ........................................................................................................... 371 Appendix 1: All Pairs Shortest Path .................................................................... 373 Introduction ........................................................................................................ 373 All Pairs Shortest Path ...................................................................................... 373 Appendix 2: Tree Traversals .................................................................................. 377 Introduction ........................................................................................................ 377 In-Order Traversal ............................................................................................. 377 Pre-order traversal ............................................................................................. 379 Post-order traversal ........................................................................................... 381 Appendix 3: Dijkstra’s Shortest Path Algorithm .............................................. 385 Introduction ........................................................................................................ 385 Dijkstra’s shortest path algorithm ................................................................... 385 Appendix 4: Supplementary Questions .............................................................. 391 Arrays: Level 0 ................................................................................................... 391 Arrays: Level 1 ................................................................................................... 392 Stacks ................................................................................................................... 392 Linked List .......................................................................................................... 392 Trees ..................................................................................................................... 393 Graphs ................................................................................................................. 395 Application based .............................................................................................. 396 Index ...................................................................................................................399-402

xviii 

Introduction to Data Structures  1 Chapter 1 Introduction to Data Structures Richard Buckland from the University of New South Wales often uses the acronym PAPP while teaching Data Structures and Algorithms. Here, the first P stands for the problem, the A stands for the algorithm, the second P for the program, and the third P for the process. An algorithm is the sequence of steps to accomplish the task at hand or solve the problem. The algorithm is then implemented in some programming language, thus, giving rise to a program. When you execute this program, it becomes a process. You learn languages, say Python, to implement an algorithm;this takes us from the algorithm to the program. You execute this program, thus, creating a process. To understand the transition from a program to a process, you learn the basics of Compiler Design and Operating Systems. In this chapter, you will learn the transition from Algorithm to Program and to some extent, the problem to the algorithm. That is, you will be presented with algorithms related to some data structures, which you will implement. Furthermore, at times, you will be presented with some problems that you need to solve using the implemented data structures. This chapter defines the term data structure and presents a brief overview of the things to come. The reader is expected to know Python;for that matter, he/she must be versed in at least one programming language. The following discussion will extensively use loops, nested loops, lists, tuples, dictionaries, arrays (both 1-dimensional and 2-dimensional), and the difference between reference types and value types.

2  Data Structures with Python Structure In this chapter, we will cover the following topics: • Define data structures • Define data type • Classify data structures • Learn a way to sort numbers Objectives This chapter aims to introduce the fascinating subject of data structures to the readers. The chapter will deal with the basic data types, types of data structures, and a problem related to sorting. After reading this chapter, the reader will be able to classify data structures and understand why this study is important. The reader will also learn when to use which data structure and what operations can be performed on them. This discussion will act as a foundation stone of the building called data structures. Introduction The single value stored in a variable is called a datum. The set of values of a variable is called data. Note that data may contain many values, each of which is referred to as a data item. Each data item can further be divided into sub-items. For example, a variable called name, which stores the name of a student, may have the value “Brandon Walsh”. This data item can be divided into two sub-items, “Brandon” and “Walsh”, which are the first name and the last name, respectively, though some data items like PAN CARD NUMBER cannot be divided into sub-items. Some of you might have studied Object Oriented Programming and have some basic idea of a “Class”, which is a real or a conceptual entity having importance to the problem at hand. An entity has attributes, each of which can be assigned some values and these values may belong to a particular data type. For example, in the following illustration, an entity called Movie has attributes name, year, genre, and so on. The data type of Name is a string, that of Year is an integer, and that of Genre, Director, and Music are strings. The values assigned to these variables are “Sairat”, 2016, “Don’t talk about it”, “Nagraj Manjule”, and “Ajay-Atul” respectively. Movie Name : Sairat Year : 2016