Data-structures-and-algorithms

Algorithms

• Count_Inversion - Given an array, return a number of pair (i,j) such that i<j and a[i]>a[j] in O(n)
• FindRank - It is a las vegas randamise algorithm to find rank of a number. Time complexity of the algorithm is on average O(n)
• Next_greatest_element - Given a array, return a array containig index of element, with greater value and lesser index difference in O(n)
• Rabin Karp - It is a pattern search algorithm of order O(n+m) where n,m : length of two strings
• Expression Evaluation - evaluates given mathematical expression using stacks
• Sieve Of Eratosthenes - Best Known algorithm to find all prime numbers Between 1 to n in O(n)
• Longest_Common_Substring - Given two strings, returns longest common substring with the help of rolling hash and Binary Search. Time complexity is O(nlogn)
• Merge Sort - T(n) = O(nlogn)
• Quicksort - T(n) = O(nlogn)

Graph Theory

• Dijkstra's Algorithm - Single Source Shortest Path problem T(n) = O((E+V)logV) using min heap
• Depth First Search
• Breath First Search
• Prims Algorithm - To find min span tree
• Bellman Ford Algorithm

Data strucures

• Linked List
• Stack
• Queue
• Hashtable
• Binary Heap(Min)
• Binary Indexed Tree
• Segment Tree
• Segment Tree with Lazy Propogation
• AVL_Tree (Balanced Binary Search Tree)
• Red Black Tree