Algorithms

This project contains algorithms implemented with java. Below are the list of algorithms that have been implemented.

Pattern String algorithms

• KMP pattern search
• Rabin Karp pattern search
• Finite Automata pattern search
• Boyer Moore - Bad heuristic rule

Sorting algorithms(swapping)

• Bubble sort
• Selection sort
• Insertion sort
• Shell sort
• Merge sort
• Quick sort
• Heap sort

Sorting algorithms(linear)

• Counting sort
• Bucket sort
• Radix sort

Graphs

• Depth first search
• Breadth first search
• Topological sort
• Dijkstras single source shortest path
• Bellman-Ford single source shortest path

Greedy Algorithms

• Activity selection
• Job Scheduling
• Egyptian factor

Dynamic Programming

• Binomial coefficient
• Longest common sequence
• Longest repeated sequence
• Longest increasing sequence
• Largest sub-array sum
• Ugly numbers
• Minimum edit distance
• Cover distance
• Longest path matrix
• Optimal game strategy
• Coin change ways
• Cutting rod
• 0-1 Knapsack problem
• Optimize matrix multiplications
• Shortest common super sequence
• Max product cutting rod
• Word break
• Dice throwing
• Box stacking
• Egg dropping

Array & Matrix Algorithms

• Array Rotation
• Finding Repetative element in 5 ways
• Triplets Sum
• Right Angle Matrix
• Matrix180Rotation
• MatrixSpiralForm

Linked Lists

• Loop Length
• LinkedList Is Palindrome
• Merge Sort for Linked Lists
• Insertion Sort for Linked Lists
• Reverse List in Groups
• Rearrange Linked List Nodes
• Merge K Sorted Linked Lists
• Segregate Even Odd Nodes
• Intersection Point
• Move Occurences

Stack

• Expression Evaluation
• Expression Conversions
• Next Greater Element
• Max Rectangle area in histogram
• Stack using queues
• Min element in stack - O(1) TC
• Stock Span

Queues

• Sum of Min & Max in sub-arrays
• First Non Repeating Character
• Petrol Pumps
• Binary Tree Height

Binary Trees

• Tree traversals iterative approach
• Morris traversal
• Foldable binary tree
• Symmetric tree
• Inorder predecessor & successor
• Construct tree from array
• Construct tree from inorder & preorder traversals
• Construct tree from inorder & postorder traversals
• Construct tree from inorder & level order traversals
• Mirror binary tree
• Convert binar tree to DLL
• Convert ternary expression to binary tree
• Covered & Uncovered nodes sum
• Divide binary tree
• Print cousins
• Sum tree
• Diagonal sum
• Largest sub tree sum
• Sum in longest path
• Print K - sum paths
• Lowest common ancestor
• Max diff between a node and its ancestor
• Printing common nodes
• Diameter of binary tree
• Is balanced tree
• Binary tree max width
• Binary tree vertical width
• Binary tree bottom view
• BST dead end
• Construct BST
• Is BST preorder traversal
• LCA in BST
• Print array in sort order BST
• Correct BST

Heap

• Sorting using heap DS
• Is given tree is binary heap

Hashing

• Longest sub array
• Longest increasing sub sequence
• Largest contiguous sub array
• Sum pair exists

Graphs

• DFS & BFS
• Minimal spanning trees
• Articulation points & bridges
• Shortest path algorithms
• Graph connectivity using Kosaraju's algorithm
• Topological sort using DFS & Kahns algorithms
• Cycle detection in grap