1Preface
16810.6 Selection Sort: 10.6.1 How Selection Sort Works?
21 Introduction to Data Structures and Algorithm
16910.7 Insertion Sort: 10.7.1 Advantages of Insertion Sorting
31.1 Introduction
17010.8 Shell Sort
41.2 Variables: 1.2.1 Definition
17110.9 Merge Sort
51.3 Data Type
17210.10 Heap Sort
61.4 Data Structures
17310.11 Quick Sort
71.4.1 Definition
17410.12 Tree Sort
81.4.2 Abstract Data Types
17510.13 Comparison of Various Sorting Algorithms
91.5 Algorithm
17610.14 Linear Sorting Algorithms
101.5.1 Definition
17710.15 Counting Sort
111.5.2 Why it’s Necessary to Analyze an Algorithm?
17810.16 Bucket Sort
121.5.3 What is the Primary Purpose of Analyzing an Algorithm
17910.17 What is Radix Sort?
131.5.4 What is Running Time Analysis
18010.18 Topological Sort
141.5.5 How to Compare Different Algorithms?
18110.19 External Sorting
151.6 Define Rate of Growth: 1.6.1 Commonly used Rate of Growths
18210.20 References
161.7 Various Types of Analysis
18311 Detailed Overview of Searching
171.7.1 Asymptotic Notation
18411.1 What is Searching?
181.7.2 Important Notes
18511.2 Why do We Need Searching?
191.7.3 Why is it called Asymptotic Notation?
18611.3 Types of Searching
201.7.4 Guidelines for Asymptotic Notations
18711.3.1 Binary Searching
211.8 Properties for Notations
18811.3.2 Linear Search
221.9 Commonly Used Logarithms and Summations
18911.4 Symbol Tables and Hashing
231.9.1 Logarithms
19011.4.1 Symbol Table
241.9.2 Summations
19111.4.2 Hashing
251.10 Master Theorem for Divide and Conquer: 1.10.1 Problems on Master Theorem for Divide and Conquer
19211.4.3 Hash Function
261.11 Master Theorem for Subtract and Conquer Recurrence
19311.5 Search Algorithm: 11.5.1 Classifications of Search Algorithms
271.12 Method of Guess and Confirm
19411.6 References
281.13 Amortized Analysis
19512 Detailed Overview of Selection Algorithms
291.14 References
19612.1 Introduction
302 Brief about Recursion and Backtracking
19712.2 Selection by Sorting
312.1 Introduction
19812.3 Partition Based Selection
322.2 What is Recursion?
19912.4 Incremental Sorting by Selection
332.2.1 Properties
20012.5 Linear Selection Algorithm – A Median of Medians
342.2.2 Implementation
20112.6 References
352.3 Why Recursion?
20213 Detailed Overview of Symbol Tables
362.3.1 Time Complexity
20313.1 Introduction
372.3.2 Space Complexity
20413.2 What are Symbol Tables?
382.4 Format of Recursive Function
20513.2.1 Uses of Symbol Table
392.5 Recursion and Memory (Visualization)
20613.2.2 Symbol Table Entries
402.6 Recursion versus Iteration
20713.2.3 Symbol Table Stores
412.7 Points to Remember about Recursion
20813.2.4 Symbol Table provides the following Information to Compiler
422.7.1 Direct Recursion
20913.2.5 Operations on Symbol Table
432.7.2 Indirect Recursion
21013.2.6 Advantages of Symbol Table
442.7.3 What is Tail Recursion?
21113.2.7 Disadvantages of Symbol Table
452.7.4 What are Linear and Tree Recursion?
21213.3 Symbol Table Implementation
462.7.5 How to Convert Recursive Functions to be Tail Recursive?
21313.4 Comparison of Symbol Table Implementations
472.7.6 How to Convert Tail Recursive Functions to Iterative Functions
21413.4.1 List
482.8 Brief about Recursive Algorithm
21513.4.2 Linked List
492.9 Problems on Recursion
21613.4.3 Hash Table
502.10 What is Backtracking?: 2.10.1 Backtracking Algorithm
21713.4.4 Binary Search Tree
512.11 References
21813.5 References
523 Brief about Linked List
21914 Detailed Overview of Hashing
533.1 Introduction
22014.1 What is Hashing?
543.2 Array Overview
22114.2 Why is Hash used?
553.3 Linked Lists Vs Dynamic Arrays
22214.3 Hash Table ADT
563.4 Singly Linked Lists
22314.3.1 Understanding Hashing
573.5 What is Doubly Linked List?
22414.3.2 Hash Function
583.6 Circular Linked Lists
22514.3.3 Load Factor
593.7 What is the Unrolled Linked List?
22614.4 Collision
603.8 What is the Skip List?
22714.4.1 Separate Chaining
613.9 References
22814.4.2 What is Open Addressing?
624 Everything about Stacks
22914.5 Advantages and Disadvantages of Hashes
634.1 What is a Stack?
23014.5.1 Advantages
644.2 How to Use stacks
23114.5.2 Disadvantages
654.2.1 Stack Pop Method
23214.6 Uses of Hashes
664.2.2 Stack Peek Method
23314.7 Hash implementation in Java
674.2.3 Boolean Empty Stack
23414.7.1 Various Constructors used in Implementing Hash Tables
684.2.4 Stack Search Method
23514.7.2 Various Methods used While Implementing Hash Tables
694.3 Stacks in ADT
23614.8 Hashing Techniques
704.4 Exceptions
23714.8.1 Linear Probing
714.5 Implementation of Stack
23814.8.2 Quadratic Probing
724.5.1 Stack Implementation Using an Array
23914.8.3 Double Hashing
734.5.2 Implementation of Stack Using Linked List
24014.8.4 Bloom Filters
744.6 Applications of Stacks
24114.9 References
754.7 Comparison of Implementation of Stacks
24215 Detailed Overview of String Algorithms
764.8 References
24315.1 Introduction
775 Detailed Overview of Queues
24415.2 String Algorithms
785.1 Introduction
24515.3 Brute Force Method
795.2 Operations on Queue
24615.4 Rabin-Karp String Matching Algorithm
805.2.1 How are Queues Used?
24715.5 String Matching with Finite Automata
815.2.2 Queue Abstract Data Type
24815.5.1 Automate
825.2.3 Queue as an Array
24915.5.2 Finite Automata
835.2.4 Queue as a Linked List
25015.6 KMP Algorithm
845.2.5 Exceptions in Queue
25115.7 Boyce-Moore Algorithm
855.3 Queue Implementation
25215.8 Data Structures for Storing Strings
865.4 References
25315.8.1 Storing String as a Character Array
876 Everything about Trees
25415.8.2 Storing String as a Character Pointer
886.1 What is a Tree?
25515.9 Hash Tables for Strings
896.2 Glossary
25615.10 Binary Search Trees for String
906.3 What is a Binary Tree?
25715.11 Tries
916.3.1 Properties of Binary Tree
25815.12 Ternary Search Tree
926.3.2 Types of Binary Tree
25915.13 Comparing BSTs, Tries, and TSTs
936.4 Binary Tree Traversals
26015.13.1 Binary Search Trees
946.5 Generic Trees (N-ary Trees)
26115.13.2 Tries
956.5.1 Advantages
26215.13.3 Ternary Search Tree
966.5.2 Disadvantages
26315.14 Suffix Trees
976.6 Threaded [Stack or Queue Less] Binary Tree Traversal
26415.15 References
986.6.1 Introduction to Threaded Binary Tree
26516 A Brief about Algorithm Design Techniques
996.6.2 Why Do We Need Threaded Binary Tree
26616.1 Introduction
1006.6.3 Types of Threaded Binary Tree
26716.2 Classification of Algorithms Based on the Representation
1016.6.4 Threaded Binary Tree Traversal
26816.3 Choosing the Right Algorithm
1026.7 Expression Trees: 6.7.1 Construction of Expression Tree
26916.4 Classification of Algorithm Based on Implementation
1036.8 XOR Tree
27016.4.1 Serial Implementation
1046.9 Binary Search Trees (BSTs)
27116.4.2 Parallel Implementation
1056.9.1 Properties of Binary Search Tree
27216.5 Classification of Algorithms Based on Design
1066.9.2 Operation Which can be Performed on Binary Search Tree
27316.6 Classification Algorithms
1076.9.3 Advantages of Binary Search Tree
27416.7 References
1086.9.4 Disadvantages of Binary Search Tree
27517 Detailed Overview of Greedy Algorithms
1096.10 Balanced Binary Search Tree
27617.1 Introduction
1106.10.1 Conversion of a Binary Search Tree to Balanced Binary Search Tree
27717.2 Greedy Strategy
1116.10.2 What is the Difference between Binary Search Tree and Binary Tree?
27817.3 Elements of Greedy Algorithm
1126.11 AVL (Adelson-Velskii and Landis) Trees
27917.4 Does Greedy Always Work?
1136.11.1 Properties of AVL Tree
28017.5 Advantages and Disadvantages of the Greedy Algorithm
1146.11.2 Height Balanced Tree
28117.6 Applications of Greedy Algorithm
1156.11.3 AVL Rotations
28217.6.1 Dijkstra’s Algorithm
1166.12 Other Variation in Trees
28317.6.2 Huffman Coding
1176.13 References
28417.7 Understanding Greedy Technique
1187 Detailed Overview of Priority Queues and Heaps
28517.8 References
1197.1 Introduction
28618 Brief about Divide and Conquer Algorithm
1207.2 Priority Queue ADT: 7.2.1 Here are the Operations of the Priority Queue ADT
28718.1 Introduction
1217.3 Double Ended Priority Queue
28818.2 Divide and Conquer Strategy
1227.4 Applications of Priority Queues: 7.4.1 Some of the Other Implementation Queues
28918.3 Does Divide and Conquer Always Works?
1237.5 Naïve and Usual Implementation of Priority Queues
29018.4 Visualization of Divide and Conquer
1247.6 Heaps and Binary Heaps
29118.5 Understanding Divide and Conquer
1257.7 Binomial Tree
29218.5.1 Deployment of the Issues
1267.8 Binary Heap
29318.5.2 Advantages
1277.8.1 Operations of Binary Heap
29418.5.3 Disadvantages
1287.8.2 Advantages of Binary Heap
29518.6 Master Theorem
1297.9 References
29618.7 Divide and Conquer Applications
1308 Detailed Overview of Disjoint Set ADT
29718.8 References
1318.1 Introduction
29819 Brief About Dynamic Programming
1328.2 Equivalence Relation and Equivalence Classes
29919.1 Introduction
1338.3 Disjoint Set ADT
30019.2 What is Dynamic Programming Strategy?
1348.4 Operations on Disjoint sets
30119.3 Properties of Dynamic Programming Strategy
1358.5 Applications: 8.5.1 What is a Kruskal’s Algorithm?
30219.4 Can Dynamic Programming Solve all the Problems?
1368.6 Quick Find Fast Union Implementation
30319.5 Dynamic Programming Approaches
1378.7 Quick Find Implementation in JAVA
30419.6 Examples of Dynamic Programming Algorithms
1388.8 Path Compression
30519.6.1 0-1Knapsack Problem
1398.9 References
30619.6.2 Chain Matrix Multiplication
1409 Detailed Overview of Graph Algorithms
30719.6.3 All Pairs Shortest Path
1419.1 Introduction
30819.6.4 The Floyd Warshall Algorithm: Improved All Pairs Shortest Path
1429.2 Definition
30919.7 Understanding of Dynamic Programming
1439.3 Applications of Graphs
31019.8 References
1449.4 Graph Representation
31120 Brief about Complexity Classes
1459.4.1 Representation Using Sets
31220.1 Introduction
1469.4.2 Adjacency Matrix
31320.2 Polynomial/ Exponential Time
1479.4.3 Adjacency List
31420.3 Decision Problem
1489.5 Graph Traversals
31520.3.1 Decidability
1499.5.1 Breadth First Search
31620.3.2 Function Problems
1509.5.2 Depth First Search
31720.4 Decision Procedure
1519.5.3 Topological Sort
31820.5 What is a Complexity Class?
1529.5.4 Shortest Path Algorithms
31920.6 Types of the Complexity Class
1539.5.5 Unweighted Shortest paths
32020.6.1 Complexity Class P
1549.5.6 Dijkstra’s Algorithm
32120.6.2 NP class
1559.5.7 All-to-all Shortest Problem
32220.7 Reduction
1569.6 Minimal Spanning Tree
32320.7.1 Requirement of Reduction
1579.6.1 Brouvka’s Algorithm
32420.7.2 Types and Applications of Reduction
1589.6.2 Kruskal’s Algorithm
32520.8 References
1599.6.3 Jarnik Prims Algorithm
32621 Miscellaneous Concepts
1609.6.4 Dijkstra’s Algorithm
32721.1 Introduction
1619.7 References
32821.2 References
16210 Detailed Overview of Sorting
32922 Appendix A: Abbreviations
16310.1 What is Sorting?
33023 Appendix B: Figures
16410.2 Why is Sorting Necessary?
33124 Appendix C: Graphs & Tables
16510.3 Classification
33224.1 Graphs
16610.4 Other Classifications
33324.2 Tables
16710.5 What is a Bubble Sort?
334Index
