Solve complex problems by performing analysis of algorithms or selecting suitable techniques for optimal performance.
Description:
“Advanced Data Structures and Algorithms” is an important subject area in Computer Science that covers more complex and advanced topics related to data structures and algorithms.
This book will teach you how to analyze algorithms to handle the difficulties of sophisticated programming. It will then help you understand how advanced data structures are used to store and manage data efficiently. Moving on, it will help you explore and work with Divide and Conquer techniques, Dynamic programming, and Greedy algorithms. Lastly, the book will focus on various String Matching Algorithms such as naïve string matching algorithms, Knuth–Morris–Pratt (KMP) Algorithm, and Rabin-Karp Algorithm.
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.
By the end of the book, you will be able to analyze various algorithms with time and space complexity to choose the best suitable algorithms for a given problem.
What you will learn:
- Understand how to examine an algorithm's time and space complexity.
- Explore complex data structures like AVL tree, Huffman coding, and many more.
- Learn how to solve larger problems using Divide and Conquer techniques.
- Identify the most optimal solution using Greedy and Dynamic Programming.
Who this book is for:
This book is aligned with the curriculum of the Computer Engineering program offered by Mumbai University. The book is designed not only for Computer Engineering and Information Technology students but also for anyone who wants to learn about advanced data structures and analysis of algorithms.
Author(s): Abirami A., Priya R.L.
Publisher: BPB Publications
Year: 2023
Language: English
Pages: 214
Cover Page
Title Page
Copyright Page
Dedication Page
About the Authors
About the Reviewers
Acknowledgements
Preface
Errata
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 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
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
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
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
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
