Advanced Data Structures and Algorithms Learn how to enhance data processing with more complex and advanced data structures (A. Abirami, R.L. Priya) (Z-Library)

📄 File Format: PDF

💾 File Size: 5.4 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

(This page has no text content)

📄 Page 3

Advanced Data Structures and Algorithms Learn how to enhance data processing with more complex and advanced data structures Abirami A Priya R L www.bpbonline.com

📄 Page 4

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-5551-792-0 www.bpbonline.com

📄 Page 5

Dedicated to Our beloved students & Our family members and friends

📄 Page 6

About the Authors Mrs. Abirami A has completed her M.E (Information Technology) from Mumbai University, and is currently pursuing Ph.D. (Information Technology), from Noorul Islam Centre for Higher Education, Kumaracoil, Tamil Nadu. Her research interests are Computer Networks, Cyber security, Network Forensics and Analysis of algorithms. She has 17 years of teaching experience and has published many papers in national and international conferences and journals and work as an editorial board member of the Editorial Board of various SCI/SCOPUS indexed journals. Asst. Professor III - Information Technology Department, Bannari Amman Institute of Technology, Sathyamangalam, Erode, Tamil Nadu. Mrs. Priya R. L is currently working as an Assistant Professor in V.E.S Institute of Technology, Mumbai, having 18 years of teaching experience for undergraduate students of Computer Engineering and Information Technology disciplines in different Engineering Institutes. She obtained her Master’s degree in Information Technology Engineering from Mumbai University. She has also worked as a Software Engineer in different firms in Chennai and Mumbai for 4 years. Her research interest is more into Artificial Intelligence, Internet of Things (IoT), Software engineering, Data Structures, Data Mining and Next Generation Networks. She has published more than 40 papers in various reputed SCI / SCOPUS indexed journals and international conferences. Assistant Professor, Department of Computer Engineering, V.E.S. Institute of Technology, Mumbai, India.

📄 Page 7

About the Reviewers Mrs. Lifna C S, Assistant Professor at the Vivekanand Education Society’s Institute of Technology, Mumbai. Her research interests are Big Data Analytics, Social Analytics, Machine Learning, UX Design, Blockchain. She has around 26+ research papers published in international conferences & journals. She is an Innovation Ambassador of VESIT - IIC (Institute Innovation Cell) formed under MHRD from 2019 onwards. She is also a member of the AI Research Group established at VESIT, in association with LeadingIndia.ai at Bennett University. Dr. Lakshmanaprakash S completed his Ph.D. from Curtin University, Sarawak, Malaysia in 2019. He is currently working as Associate Professor in the Department of IT, BIT, and Erode, India. He has published many papers in various reputed national/International conferences and Journals. Dr. Lakshmanaprakash has also been a reviewer in various SCI Journals. His research interest mainly focuses on Cybersecurity and Machine Learning.

📄 Page 8

Acknowledgements We wish to express our gratitude to all those people who assisted and helped us to complete this book. We would like to show our appreciation to the members of our student team (Riya Bhanushali, Amisha Das, Asiya Khan, Disha Shah, Jay Visaria, and Mansi Thakkar of Shah and Anchor Kutchhi Engineering College, Mumbai, and Ajay Nair from Vivekanand Education Society’s Institute of Technology, Mumbai). They helped us to understand their needs for the preparation of the contents associated with this book during the Engineering course. First and foremost, I want to express my gratitude to our friends and family members for their unwavering support to complete the book successfully. Without their encouragement, we would never have been able to finish it. We owe a debt of gratitude to the student team who accompanied us in writing this book. We gratefully acknowledge Dr. Lakshmanprakash S and Mrs. Lifna C S for their kind technical scrutiny of this book. Our gratitude also extends to the BPB team, who were kind enough to give us enough time to complete the book’s first section and to approve its publication.

📄 Page 9

Preface This book covers a collection of complex algorithms and helps to face the challenges in algorithmic analysis. Analysis of algorithms and handling sophisticated data structures focus on the fundamentals of the computer programming field. The book highlights how to find the best optimal solution to a real-world problem using an appropriate algorithm. The book provides theoretical explanations and solved examples of most of the topics covered. This book also introduces the importance of performance analysis of an algorithm, which helps to increase efficiency and reduces time and space complexity. It shows how to create and design a complex data structure. This book solves the basic understanding of greedy and dynamic programming. It also gives importance to various divide-and-conquer techniques. This book gives information about string-matching methods as well. This book is divided into six chapters. The reader will go through advanced data structures, greedy and dynamic programming, optimal solutions, string matching using various techniques, and calculations of time and space complexity using Asymptotic notations. To help learners better comprehend the material, each topic is handled with appropriate examples. The specifics are mentioned as follows. Chapter 1 emphasizes the basics of algorithmic analysis. It will discuss the need for analysis of algorithms and help us to choose a better suitable algorithm for a given problem statement. In algorithmic design, the complexity of an algorithm plays an important aspect to justify the design decisions. Accordingly, algorithm efficiency is measured from two perspectives such as time and space complexity. Hence, the major focus of this chapter is on various types of asymptotic notations used for the estimation of the time complexity of an algorithm and is discussed with examples. Chapter 2 discusses different complex data structures that may be used to effectively tackle difficult situations. AVL Tree, Huffman Coding, Redblack Tree, and several more search trees are among the advanced data structures addressed.

📄 Page 10

Chapter 3 discusses the divide and conquer technique with the basic introduction and various methods that are involved in it with suitable examples. Divide and Conquer is the simplest and easiest technique of decomposing a larger problem into simpler problems, to solve any given problem statement. Chapter 4 will cover information about various greedy algorithms such as the knapsack problem, optimal merge pattern, subset cover problem, and so on, in detail with various solved examples. Chapter 5 discusses Dynamic Programming. It describes various classical computer science problems and their optimal solutions using dynamic programming approaches along with their applications. The need for dynamic algorithms and introduction to NP-Hard & NP-Complete are discussed with examples. Chapter 6 describes different string-matching algorithms with suitable examples. The chapter also provides description of genetic algorithms.

📄 Page 11

Coloured Images Please follow the link to download the Coloured Images of the book: https://rebrand.ly/x0d84sg 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

📄 Page 12

technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on BPB books and eBooks.

📄 Page 13

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

📄 Page 14

(This page has no text content)

📄 Page 15

Table of Contents 1. Analysis of Algorithm Introduction Structure Objectives Analysis of algorithm What is analysis of algorithms? Why to analyze algorithms? Asymptotic notations Θ Notation Big O Notation Ω (Omega) Notation Example 1 Example 2 Example 3 Example 4 Time complexity Calculating the time complexity Calculating the rate of growth of an algorithm with respect to the input Example 5 Example 6 Example 7 General rules for time complexity analysis Rule 1: Remove all lower order expressions & drop the constant multiplier Example 8 Example 9 Example 10 Rule 2: The running time of an algorithm is equal to the summation of running time of all the fragments of the algorithm. Example 11 Rule 3: In case of conditional statements; consider the complexity of

📄 Page 16

the condition which is the worst case. Example 12 Recurrences Substitution method Example 13 Master theorem Example 14 Recursive Tree Method Example 15 Conclusion Key facts Questions 2. Advanced Data Structures Introduction Structure Objectives Advanced data structures AVL Tree RR Rotation LL Rotation LR Rotation RL rotation Huffman algorithm Example 1 Example 2 2-3 Tree operation Searching an element in 2-3 tree Search an element in 2-3 Tree: Inserting an element in a 2-3 Tree: Red-Black Trees Example 3 Example 4 Tries Types of tries Standard tries Compressed tries

📄 Page 17

Suffix tries Heap Sort Types of heaps Maximum Heap Minimum heap ReHeap-Up ReHeap-Down Algorithm for heap sort Example 5 B Trees Constructing a B-Tree Conclusion Key facts Questions 3. Divide and Conquer Introduction Structure Objectives Divide and conquer Binary search Algorithm Example 1 Example 2 Analysis of Algorithm Finding the minimum and maximum Naive method Divide and conquer approach Algorithm Analysis of Algorithm Merge Sort Algorithm Analysis of Merge Sort Quick Sort Algorithm Analysis of algorithm Best case

📄 Page 18

Worst case Strassen’s matrix multiplication Example 3 Analysis of algorithm Conclusion Key facts Questions 4. Greedy Algorithms Introduction Structure Objectives Knapsack problem Example 1 Example 2 Example 3 Job Sequencing with deadlines Algorithm Example 4 Minimum Cost Spanning Tree Kruskal’s algorithm Algorithm Example 5 Prim’s algorithm Algorithm Example 6 Optimal Storage on Tapes Optimal storage on single tapes Example 7 Example 8 Optimal Storage on Multiple Tapes Example 9 Optimal Merge Pattern Example 10 Algorithm Tree (n) Example 11 Example 12

📄 Page 19

Subset cover problem Algorithm of set cover problem Example 13 Container Loading Problem Algorithm of Container Loading Problem Example 14 Conclusion Key facts Questions 5. Dynamic Algorithms and NP-Hard and NP-Complete Introduction Structure Objectives Dynamic algorithms All Pair Shortest Path Algorithm Example 1 0/1 Knapsack Problem Algorithm Example 2 Example 3 Example 4 Traveling Salesman Problem Example 5 Example 6 Coin Changing problem Example 7 Example 8 Matrix Chain Multiplication Example 9 Flow Shop scheduling Algorithm Optimal Binary Search Tree Algorithm Example 10 Example 11 NP – HARD & NP – COMPLETE

📄 Page 20

NP-COMPLETE problems NP-HARD problems Conclusion Key facts Questions 6. String Matching Introduction Structure Objectives The Naïve String-Matching Algorithm Example 1 Algorithm for Naïve bayes string matching Rabin Karp Algorithm Example 2 Example 3 The Knuth-Morris-Pratt Algorithm Example 4 Example 5 Example 6 Longest Common Subsequence (LCS) Example 7 Example 8 Genetic Algorithms Search Space Fitness score Operators of genetic algorithms Conclusion Key Facts Questions Index