Skip to content

Latest commit

 

History

History
549 lines (474 loc) · 19.6 KB

Algorithms.md

File metadata and controls

549 lines (474 loc) · 19.6 KB

Here i am providing all the patterns of the algorithms which i have foung on the internet. Hope it helps Happy Hacking! Please let me know if any thing wrong.

Types of Algorithms: There are several types of algorithms available. Some important algorithms are:

  1. Brute Force Algorithm: It is the simplest approach for a problem. A brute force algorithm is the first approach that comes to finding when we see a problem.

  2. Recursive Algorithm: A recursive algorithm is based on recursion. In this case, a problem is broken into several sub-parts and called the same function again and again.

  3. Backtracking Algorithm: The backtracking algorithm basically builds the solution by searching among all possible solutions. Using this algorithm, we keep on building the solution following criteria. Whenever a solution fails we trace back to the failure point and build on the next solution and continue this process till we find the solution or all possible solutions are looked after.

  4. Searching Algorithm: Searching algorithms are the ones that are used for searching elements or groups of elements from a particular data structure. They can be of different types based on their approach or the data structure in which the element should be found.

  5. Sorting Algorithm: Sorting is arranging a group of data in a particular manner according to the requirement. The algorithms which help in performing this function are called sorting algorithms. Generally sorting algorithms are used to sort groups of data in an increasing or decreasing manner.

  6. Hashing Algorithm: Hashing algorithms work similarly to the searching algorithm. But they contain an index with a key ID. In hashing, a key is assigned to specific data.

  7. Divide and Conquer Algorithm: This algorithm breaks a problem into sub-problems, solves a single sub-problem and merges the solutions together to get the final solution. It consists of the following three steps:

Divide Solve Combine 8. Greedy Algorithm: In this type of algorithm the solution is built part by part. The solution of the next part is built based on the immediate benefit of the next part. The one solution giving the most benefit will be chosen as the solution for the next part.

  1. Dynamic Programming Algorithm: This algorithm uses the concept of using the already found solution to avoid repetitive calculation of the same part of the problem. It divides the problem into smaller overlapping subproblems and solves them.

  2. Randomized Algorithm: In the randomized algorithm we use a random number so it gives immediate benefit. The random number helps in deciding the expected outcome.

Topics : Analysis of Algorithms Searching and Sorting Greedy Algorithms Dynamic Programming Pattern Searching Other String Algorithms Backtracking Divide and Conquer Geometric Algorithms Mathematical Algorithms Bit Algorithms Graph Algorithms Randomized Algorithms Branch and Bound Quizzes on Algorithms Misc Analysis of Algorithms:

Asymptotic Analysis Worst, Average and Best Cases Asymptotic Notations Little o and little omega notations Lower and Upper Bound Theory Analysis of Loops Solving Recurrences Amortized Analysis What does ‘Space Complexity’ mean? Pseudo-polynomial Algorithms NP-Completeness Introduction Polynomial Time Approximation Scheme A Time Complexity Question Time Complexity of building a heap Time Complexity where loop variable is incremented by 1, 2, 3, 4 .. Time Complexity of Loop with Powers Performance of loops (A caching question) Recent Articles on Analysis of Algorithms Quiz on Analysis of Algorithms Quiz on Recurrences

Searching and Sorting:

Linear Search, Binary Search, Jump Search, Interpolation Search, Exponential Search, Ternary Search Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, QuickSort, Radix Sort, Counting Sort, Bucket Sort, ShellSort, Comb Sort, Pigeonhole Sort, Cycle Sort Interpolation search vs Binary search Stability in sorting algorithms When does the worst case of Quicksort occur? Lower bound for comparison based sorting algorithms Which sorting algorithm makes minimum number of memory writes? Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted Merge Sort for Linked Lists Sort a nearly sorted (or K sorted) array Iterative Quick Sort QuickSort on Singly Linked List QuickSort on Doubly Linked List Find k closest elements to a given value Sort n numbers in range from 0 to n^2 – 1 in linear time A Problem in Many Binary Search Implementations Search in an almost sorted array Sort an array in wave form Why is Binary Search preferred over Ternary Search? K’th Smallest/Largest Element in Unsorted Array K’th Smallest/Largest Element in Unsorted Array in Expected Linear Time K’th Smallest/Largest Element in Unsorted Array in Worst Case Linear Time Find the closest pair from two sorted arrays Find common elements in three sorted arrays Given a sorted array and a number x, find the pair in array whose sum is closest to x Count 1’s in a sorted binary array Binary Insertion Sort Insertion Sort for Singly Linked List Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists? Merge Sort for Doubly Linked List Minimum adjacent swaps to move maximum and minimum to corners Recent Articles on Searching Recent Articles on Sorting Quiz on Searching Quiz on Sorting Coding Practice on Searching Coding Practice on Sorting

Greedy Algorithms:

Activity Selection Problem Kruskal’s Minimum Spanning Tree Algorithm Huffman Coding Efficient Huffman Coding for Sorted Input Prim’s Minimum Spanning Tree Algorithm Prim’s MST for Adjacency List Representation Dijkstra’s Shortest Path Algorithm Dijkstra’s Algorithm for Adjacency List Representation Job Sequencing Problem Quiz on Greedy Algorithms Greedy Algorithm to find Minimum number of Coins K Centers Problem Minimum Number of Platforms Required for a Railway/Bus Station Recent Articles on Greedy Algorithms Quiz on Greedy Algorithms Coding Practice on Greedy Algorithms

Dynamic Programming:

Overlapping Subproblems Property Optimal Substructure Property Longest Increasing Subsequence Longest Common Subsequence Edit Distance Min Cost Path Coin Change Matrix Chain Multiplication Binomial Coefficient 0-1 Knapsack Problem Egg Dropping Puzzle Longest Palindromic Subsequence Cutting a Rod Maximum Sum Increasing Subsequence Longest Bitonic Subsequence Floyd Warshall Algorithm Palindrome Partitioning Partition problem Word Wrap Problem Maximum Length Chain of Pairs Variations of LIS Box Stacking Problem Program for Fibonacci numbers Minimum number of jumps to reach end Maximum size square sub-matrix with all 1s Ugly Numbers Largest Sum Contiguous Subarray Longest Palindromic Substring Bellman–Ford Algorithm for Shortest Paths Optimal Binary Search Tree Largest Independent Set Problem Subset Sum Problem Maximum sum rectangle in a 2D matrix Count number of binary strings without consecutive 1?s Boolean Parenthesization Problem Count ways to reach the n’th stair Minimum Cost Polygon Triangulation Mobile Numeric Keypad Problem Count of n digit numbers whose sum of digits equals to given sum Minimum Initial Points to Reach Destination Total number of non-decreasing numbers with n digits Find length of the longest consecutive path from a given starting character Tiling Problem Minimum number of squares whose sum equals to given number n Find minimum number of coins that make a given value Collect maximum points in a grid using two traversals Shortest Common Supersequence Compute sum of digits in all numbers from 1 to n Count possible ways to construct buildings Maximum profit by buying and selling a share at most twice How to print maximum number of A’s using given four keys Find the minimum cost to reach destination using a train Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) Count number of ways to reach a given score in a game Weighted Job Scheduling Longest Even Length Substring such that Sum of First and Second Half is same Recent Articles on Dynamic Programming Quiz on Dynamic Programming Coding Practice on Dynamic Programing

Pattern Searching:

Naive Pattern Searching KMP Algorithm Rabin-Karp Algorithm A Naive Pattern Searching Question Finite Automata Efficient Construction of Finite Automata Boyer Moore Algorithm – Bad Character Heuristic Suffix Array Anagram Substring Search (Or Search for all permutations) Pattern Searching using a Trie of all Suffixes Aho-Corasick Algorithm for Pattern Searching kasai’s Algorithm for Construction of LCP array from Suffix Array Z algorithm (Linear time pattern searching Algorithm) Program to wish Women’s Day Recent Articles on Pattern Searching

Other String Algorithms:

Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1, Part 2, Part 3, Part 4 Longest Even Length Substring such that Sum of First and Second Half is same Print all possible strings that can be made by placing spaces Recent Articles on Strings Coding practice on Strings

Backtracking:

Print all permutations of a given string The Knight’s tour problem Rat in a Maze N Queen Problem Subset Sum m Coloring Problem Hamiltonian Cycle Sudoku Tug of War Solving Cryptarithmetic Puzzles Recent Articles on Backtracking Coding Practice on Backtracking

Divide and Conquer:

Introduction Write your own pow(x, n) to calculate x*n Median of two sorted arrays Count Inversions Closest Pair of Points Strassen’s Matrix Multiplication Quick Sort vs Merge Sort Recent Articles on Divide and Conquer Quiz on Divide and Conquer Coding practice on Divide and Conquer

Geometric Algorithms:

Closest Pair of Points | O(nlogn) Implementation How to check if two given line segments intersect? How to check if a given point lies inside or outside a polygon? Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping) Convex Hull | Set 2 (Graham Scan) Given n line segments, find if any two segments intersect Check whether a given point lies inside a triangle or not How to check if given four points form a square Recent Articles on Geometric Algorithms Coding Practice on Geometric Algorithms

Mathematical Algorithms:

Write an Efficient Method to Check if a Number is Multiple of 3 Efficient way to multiply with 7 Write a C program to print all permutations of a given string Lucky Numbers Write a program to add two numbers in base 14 Babylonian method for square root Multiply two integers without using multiplication, division and bitwise operators, and no loops Print all combinations of points that can compose a given number Write you own Power without using multiplication() and division(/) operators Program for Fibonacci numbers Average of a stream of numbers Count numbers that don’t contain 3 MagicSquare Sieve of Eratosthenes Number which has the maximum number of distinct prime factors in the range M to N Find day of the week for a given date DFA based division Generate integer from 1 to 7 with equal probability Given a number, find the next smallest palindrome Make a fair coin from a biased coin Check divisibility by 7 Find the largest multiple of 3 Lexicographic rank of a string Print all permutations in sorted (lexicographic) order Shuffle a given array Space and time efficient Binomial Coefficient Reservoir Sampling Pascal’s Triangle Select a random number from stream, with O(1) space Find the largest multiple of 2, 3 and 5 Efficient program to calculate e^x Measure one litre using two vessels and infinite water supply Efficient program to print all prime factors of a given number Print all possible combinations of r elements in a given array of size n Random number generator in arbitrary probability distribution fashion How to check if a given number is Fibonacci number? Russian Peasant Multiplication Count all possible groups of size 2 or 3 that have sum as multiple of 3 Tower of Hanoi Horner’s Method for Polynomial Evaluation Count trailing zeroes in factorial of a number Program for nth Catalan Number Generate one of 3 numbers according to given probabilities Find Excel column name from a given column number Find next greater number with same set of digits Count Possible Decodings of a given Digit Sequence Calculate the angle between hour hand and minute hand Count number of binary strings without consecutive 1?s Find the smallest number whose digits multiply to a given number n Draw a circle without floating point arithmetic How to check if an instance of 8 puzzle is solvable? Birthday Paradox Multiply two polynomials Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality xx + y*y < n Count ways to reach the n’th stair Replace all ‘0’ with ‘5’ in an input Integer Program to add two polynomials Print first k digits of 1/n where n is a positive integer Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 Program for Bisection Method Program for Method Of False Position Program for Newton Raphson Method Recent Articles on Mathematical Algorithms Coding Practice on Mathematical Algorithms

Bit Algorithms:

Find the element that appears once Detect opposite signs Set bits in all numbers from 1 to n Swap bits Add two numbers Smallest of three A Boolean Array Puzzle Set bits in an (big) array Next higher number with same number of set bits Optimization Technique (Modulus) Add 1 to a number Multiply with 3.5 Turn off the rightmost set bit Check for Power of 4 Absolute value (abs) without branching Modulus division by a power-of-2-number Minimum or Maximum of two integers Rotate bits Find the two non-repeating elements in an array Number Occurring Odd Number of Times Check for Integer Overflow Little and Big Endian Reverse Bits of a Number Count set bits in an integer Number of bits to be flipped to convert A to B Next Power of 2 Check if a Number is Multiple of 3 Find parity Multiply with 7 Find whether a no is power of two Position of rightmost set bit Binary representation of a given number Swap all odd and even bits Find position of the only set bit Karatsuba algorithm for fast multiplication How to swap two numbers without using a temporary variable? Check if a number is multiple of 9 using bitwise operators Swap two nibbles in a byte How to turn off a particular bit in a number? Check if binary representation of a number is palindrome Recent Articles on Bit Algorithms Quiz on Bit Algorithms Coding Practice on Bit Algorithms

Graph Algorithms:

Introduction, DFS and BFS:

Graph and its representations Breadth First Traversal for a Graph Depth First Traversal for a Graph Applications of Depth First Search Detect Cycle in a Directed Graph Detect Cycle in a an Undirected Graph Detect cycle in an undirected graph Longest Path in a Directed Acyclic Graph Topological Sorting Check whether a given graph is Bipartite or not Snake and Ladder Problem Biconnected Components Check if a given graph is tree or not Minimum Spanning Tree:

Prim’s Minimum Spanning Tree (MST)) Applications of Minimum Spanning Tree Problem Prim’s MST for Adjacency List Representation Kruskal’s Minimum Spanning Tree Algorithm Boruvka’s algorithm for Minimum Spanning Tree Shortest Paths:

Dijkstra’s shortest path algorithm Dijkstra’s Algorithm for Adjacency List Representation Bellman–Ford Algorithm Floyd Warshall Algorithm Johnson’s algorithm for All-pairs shortest paths Shortest Path in Directed Acyclic Graph Some interesting shortest path questions Shortest path with exactly k edges in a directed and weighted graph Connectivity:

Find if there is a path between two vertices in a directed graph Connectivity in a directed graph Articulation Points (or Cut Vertices) in a Graph Biconnected graph Bridges in a graph Eulerian path and circuit Fleury’s Algorithm for printing Eulerian Path or Circuit Strongly Connected Components Transitive closure of a graph Find the number of islands Count all possible walks from a source to a destination with exactly k edges Euler Circuit in a Directed Graph Biconnected Components Tarjan’s Algorithm to find Strongly Connected Components Hard Problems:

Graph Coloring (Introduction and Applications) Greedy Algorithm for Graph Coloring Travelling Salesman Problem (Naive and Dynamic Programming) Travelling Salesman Problem (Approximate using MST) Hamiltonian Cycle Vertex Cover Problem (Introduction and Approximate Algorithm) K Centers Problem (Greedy Approximate Algorithm) Maximum Flow:

Ford-Fulkerson Algorithm for Maximum Flow Problem Find maximum number of edge disjoint paths between two vertices Find minimum s-t cut in a flow network Maximum Bipartite Matching Channel Assignment Problem Misc:

Find if the strings can be chained to form a circle Given a sorted dictionary of an alien language, find order of characters Karger’s algorithm for Minimum Cut Karger’s algorithm for Minimum Cut | Set 2 (Analysis and Applications) Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction) Hopcroft–Karp Algorithm for Maximum Matching | Set 2 (Implementation) Length of shortest chain to reach a target word Find same contacts in a list of contacts All Algorithms on Graph Quiz on Graph Quiz on Graph Traversals Quiz on Graph Shortest Paths Quiz on Graph Minimum Spanning Tree Coding Practice on Graph

Randomized Algorithms:

Linearity of Expectation Expected Number of Trials until Success Randomized Algorithms | Set 0 (Mathematical Background) Randomized Algorithms | Set 1 (Introduction and Analysis) Randomized Algorithms | Set 2 (Classification and Applications) Randomized Algorithms | Set 3 (1/2 Approximate Median) Karger’s algorithm for Minimum Cut K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time) Reservoir Sampling Shuffle a given array Select a Random Node from a Singly Linked List Recent Articles on Randomized Algorithms

Branch and Bound:

Branch and Bound | Set 1 (Introduction with 0/1 Knapsack) Branch and Bound | Set 2 (Implementation of 0/1 Knapsack) Branch and Bound | Set 3 (8 puzzle Problem) Branch And Bound | Set 4 (Job Assignment Problem) Branch and Bound | Set 5 (N Queen Problem) Branch And Bound | Set 6 (Traveling Salesman Problem)

Recent Articles on Branch and Bound

Quizzes on Algorithms:

Analysis of Algorithms Sorting Divide and Conquer Greedy Algorithms Dynamic Programming Backtracking Misc NP Complete Searching Analysis of Algorithms (Recurrences) Recursion Bit Algorithms Graph Traversals Graph Shortest Paths Graph Minimum Spanning Tree Misc:

Commonly Asked Algorithm Interview Questions | Set 1 Given a matrix of ‘O’ and ‘X’, find the largest subsquare surrounded by ‘X’ Nuts & Bolts Problem (Lock & Key problem) Flood fill Algorithm – how to implement fill() in paint? Given n appointments, find all conflicting appointments Check a given sentence for a given set of simple grammer rules Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array How to check if two given sets are disjoint? Minimum Number of Platforms Required for a Railway/Bus Station Length of the largest subarray with contiguous elements | Set 1 Length of the largest subarray with contiguous elements | Set 2 Print all increasing sequences of length k from first n natural numbers Given two strings, find if first string is a subsequence of second Snake and Ladder Problem Write a function that returns 2 for input 1 and returns 1 for 2 Connect n ropes with minimum cost Find the number of valid parentheses expressions of given length Longest Monotonically Increasing Subsequence Size (N log N): Simple implementation Generate all binary permutations such that there are more 1’s than 0’s at every point in all permutations Lexicographically minimum string rotation Construct an array from its pair-sum array Program to evaluate simple expressions Check if characters of a given string can be rearranged to form a palindrome Print all pairs of anagrams in a given array of strings