First of all, Welcome to the Sport of Coding – Competitive Programming. As we all know competitive programming is all about “coming with an optimized and efficient solution for a given problem statement“. To be a good competitive programmer, you need to have a good knowledge of Algorithms and Data Structures. This is due to the fact that most of the problem statements have large test cases that are needed to be solved with an optimized & efficient approach as inefficient solution can lead to TIMEOUT error and hence failing the testcase.
In this post, we are going to tell you some of the great algorithms (topicwise) that can ease-up your job related to optimization.
Number Theory
1. Sieve of Eratosthenes
Sieve of Eratosthenes is an efficient algorithm which is used to find all the prime numbers less than or equal to ‘n’.
Time Complexity : O(logn)
2. Segmented Sieve
This algorithm is used to find all the prime numbers within a given range. It divides the range [0..n-1] in different segments and compute primes in all segments one by one. It uses Sieve of Eratosthenes Algorithm.
Time Complexity : O(logn)
3. Prime Factorization using Sieve
This algorithm is used to find the prime factors of a given number. It can be seen as an application of Sieve.
Time Complexity : O(logn)
4. Goldbach’s Conjecture Algorithm
It states that, “Every even integer greater than 2 can be expressed as the sum of two primes“. In other words, a Goldbach number is a positive integer that can be expressed as the sum of two primes.
Time Complexity : O(log^2(n)) // order of log square n
5. Optimized Fibonacci Series Solution { Matrix Based Solution }
This algorithm is used to find the n-th number of a fibonacci series. It is done with the help of matrix manipulation.
Time Complexity : O(log n)
6. Wilson’s Theorem
Wilson’s theorem is for computing (n − 1)! modulo n for large n.
Searching & Sorting
1. Binary Search
Binary Search is a search algorithm that finds the position of a target value within a sorted array.
Time Complexity : O(log n) (base 2)
2. Ternary Search
This algorithm is used to find an element in an array. It is similar to binary search where we divide the array into two parts but in this algorithm. In this, we divide the given array into three parts.
Time Complexity : O(log n) (base 3)
3. Merge Sort
Merge Sort Algorithm is based on divide and conquer approach of problem solving. This algorithm is very useful to sort a sequence of integers of characters.
Time Complexity : O(nlogn)
4. Quick Sort
Quick Sort Algorithm is based on divide and conquer approach of problem solving. This algorithm is very useful to sort a sequence of integers of characters.
Time Complexity : O(nlogn) // Average case
Time Complexity : O(n^2) // Worst case
5. Rabin-Karp Algorithm
It is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text.
Time Complexity : O(n)
6. KMP Algorithm
It is a searching algorithm that searches for occurrences of a “word” W within a main “text string” S.
Time Complexity : O(n)
7. Z Algorithm
This algorithm finds all the occurrences of a pattern in a text string in linear time.
Time Complexity : O(n+m)
8. Counting Sort
Counting Sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm.
Time Complexity : O(n+k)
9. Manacher’s Algorithm
This is an efficient algorithm for finding the number of palindromic substrings or finding the longest palindromic substring.
Time Complexity : O(n)
10. Finding Subarrays with given Sum
There are many problems that ask you to find the number of sub arrays equaling the given sum. Traditional approach will lead you to O(n^3) time complexity. However, it can be solved using the concepts of map.
Time Complexity : O(log n)
Dynamic Programming
1. Longest Common Subsequence
The longest common subsequence problem is the problem of finding the longest subsequence common to all sequences in a set of sequences. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
2. Subset Sum Problem
This algorithm is used to find the subset of the given set whose sum is the same as the given sum value.
3. 0-1 Knapsack Problem
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
4. Longest Path in Matrix
Given a n*n matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.
Graph
1. BFS & DFS
BFS and DFS both are used for traversing a graph. BFS traverses the graph in breadth-first order and DFS traverses the graph in depth-first order.
2. Dijikstra’s Algorithm
It is used for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
3. Floyd Warshall Algorithm
It is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
4. Prim’s & Kruskal’s Algorithm
A minimum spanning tree (MST) for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree.
Both Prim’s and Kruskal’s algorithm finds the Minimum Spanning Tree and follow the Greedy approach of problem-solving.
So, these were some great algorithms that will help you in your code optimization.
Thanks a lot
Thanks… Much needed
Why do we need Rabin-Karp Algorithm while we have find function in stl cpp?