Skip to content

Latest commit

 

History

History
160 lines (160 loc) · 4.3 KB

README.md

File metadata and controls

160 lines (160 loc) · 4.3 KB

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