In this post you will know what algorithms you must learn for an undergraduate level programming competition. So the following algorithms you should get knowledge.
Mathematics:
(a)Number Theory
Prime Number Generation (Sieve, Segmented Sieve)
Euler Totient Theorem
Fermat’s Theorem
HCF & LCM (Euclid)
Linear Diophantine Equations (Extended Euclid)
Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
Cycle Finding (Floyd Algo and Brent Algo)
Integer Factorization (Trial Division , Pollard Rho method)
Lucas Theorem (Simple & Advance)
Chinese Remainder Theorem
Wilson Theorem
Miller - Rabin Primality Testing
Perfect Numbers
Goldbach Conjecture
(b)Probability
Basic Probability and Conditional Probability
Random Variables
Probability Generating Functions
Expectation
Probability Distribution [Binomial, Poisson, Normal,Bernoulli]
(c)Counting
Pigeonhole principle
Inclusion Exclusion
Special Numbers [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
Polya Counting
Burnside lemma
(d)Permutation Cycles
(e)Linear Algebra
Addition And Subtraction Of Matrices
Multiplication ( Strassen's algorithm ), Logarithmic exponentiation
Matrix Transformations [ Transpose, Rotation Of Matrix, Representing Linear Transformations Using Matrix ]
Determinant , Rank and Inverse Of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
Solving System Of Linear Equations
Matrix Exponentiation To Solve Recurrences
Eigenvalues And Eigen vector
Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial]
Lagrange Interpolation
(e)Game Theory
Basic Concepts & Nim Game [Grundy Theorem , Grundy Number]
Hackenbush
(f)Group Theory
Burnside Lemma
Polya's Theorem
Graphs:
(a)Graph Representation
Adjacency Matrix
Adjacency List
Incidence Matrix
Edge List
(b)Graph Types
Directed
Undirected
Weighted
Unweighted
Planar
Hamilton
Euler
Special Graphs
(c)DFS & It’s Application
Cycle Detection
Articulation Points
Bridges
Strongly Connected Component
Connected Component
Path Finding
Solving Maze
Biconnectivity in Graph
Topological Sorting
Bipartite Checking
Planarity Testing
Flood-fill algorithm
(d)BFS & It’s Application
Shortest Path (No. Of Edges)
Bipartite Checking
Connected Components
(d)Minimum Spanning Tree
Prim’s Algorithm
Kruskal Algorithm
(d)Single Source Shortest-Path
Dijkstra
Bellman Ford
(e)All pair Shortest Path
Floyd Warshall’s Algorithm
(f)Euler Tour
(g)Flow
Ford-Fulkerson [PFS,DFS,BFS]
Dinic's Algorithm
Min Cost - Max Flow [Successive Shortest Path Algo,Cycle Cancelling Algorithm]
Max Weighted BPM [Kuhn Munkres algorithm/Hungarian Method]
Stoer Wagner Min-Cut Algo
Hop-Kraft BPM
Edmond Blossom Shrinking Algorithm
(h)Other Important Topics On Graphs
2-SAT,
LCA
Maximum Cardinality Matching
Application Flow
Min Path Cover Over Dag
Independent Edge Disjoint Path
Minimum Vertex Cover
Maximum Independent Set
Data Structures:
Arrays
Linked List
Trees (Binary Tree And Binary Search Tree)
Stacks
Queues
Heap
Hash Tables
Disjoint-Set Data Structures
Trie
Segment Tree
Binary Index Tree
Treap
Searching And Sorting:
Linear Search
BInary Search
Ternary Search
Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Quick Select
Heap Sort
Radix Sort
Counting Sort
Greedy:
Classical Problems of Greedy & Concept
example : Fractional Knapsack
Dynamic Programming Classical Problems
Edit Distance
Egg Dropping Puzzle
Integer Knapsack
Largest Independent Set
Longest Biotonic Subsequence
Longest Common Subsequence
Longest Common Substring
Longest Increasing Subsequence
Longest Palindromic Subsequence
Longest Palindromic Substring
Longest Substring Without Repeating Character
Matrix Chain Multiplication
Max Size Square Submatrix With One
Maximum Length Chain Pairs
Maximum Sum Increasing Subsequence
Optimal Binary Search Tree
Palindrome Partition Problem
Set Partition Problem
Subset Sum
Word Wrap Problem
Dynamic Programming Advanced Techniques
DP + Tree
DP + Bit Masking
DP + Binary Search
DP + Graph
DP + Matrix Exponentiation
DP + Probability Space
DP + Crack Recurrence
Divide & Conquer
Classical Problems & Concepts
Merge Sort
Closest Pair Points
Other Algorithm Design Techniques :
BackTracking
Man In Middle
Newton-Raphson to reach the fixed point
Brute Force
Constructive Algo
Sliding Window
Pancake Sorting
Mathematics:
(a)Number Theory
Prime Number Generation (Sieve, Segmented Sieve)
Euler Totient Theorem
Fermat’s Theorem
HCF & LCM (Euclid)
Linear Diophantine Equations (Extended Euclid)
Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
Cycle Finding (Floyd Algo and Brent Algo)
Integer Factorization (Trial Division , Pollard Rho method)
Lucas Theorem (Simple & Advance)
Chinese Remainder Theorem
Wilson Theorem
Miller - Rabin Primality Testing
Perfect Numbers
Goldbach Conjecture
(b)Probability
Basic Probability and Conditional Probability
Random Variables
Probability Generating Functions
Expectation
Probability Distribution [Binomial, Poisson, Normal,Bernoulli]
(c)Counting
Pigeonhole principle
Inclusion Exclusion
Special Numbers [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
Polya Counting
Burnside lemma
(d)Permutation Cycles
(e)Linear Algebra
Addition And Subtraction Of Matrices
Multiplication ( Strassen's algorithm ), Logarithmic exponentiation
Matrix Transformations [ Transpose, Rotation Of Matrix, Representing Linear Transformations Using Matrix ]
Determinant , Rank and Inverse Of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
Solving System Of Linear Equations
Matrix Exponentiation To Solve Recurrences
Eigenvalues And Eigen vector
Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial]
Lagrange Interpolation
(e)Game Theory
Basic Concepts & Nim Game [Grundy Theorem , Grundy Number]
Hackenbush
(f)Group Theory
Burnside Lemma
Polya's Theorem
Graphs:
(a)Graph Representation
Adjacency Matrix
Adjacency List
Incidence Matrix
Edge List
(b)Graph Types
Directed
Undirected
Weighted
Unweighted
Planar
Hamilton
Euler
Special Graphs
(c)DFS & It’s Application
Cycle Detection
Articulation Points
Bridges
Strongly Connected Component
Connected Component
Path Finding
Solving Maze
Biconnectivity in Graph
Topological Sorting
Bipartite Checking
Planarity Testing
Flood-fill algorithm
(d)BFS & It’s Application
Shortest Path (No. Of Edges)
Bipartite Checking
Connected Components
(d)Minimum Spanning Tree
Prim’s Algorithm
Kruskal Algorithm
(d)Single Source Shortest-Path
Dijkstra
Bellman Ford
(e)All pair Shortest Path
Floyd Warshall’s Algorithm
(f)Euler Tour
(g)Flow
Ford-Fulkerson [PFS,DFS,BFS]
Dinic's Algorithm
Min Cost - Max Flow [Successive Shortest Path Algo,Cycle Cancelling Algorithm]
Max Weighted BPM [Kuhn Munkres algorithm/Hungarian Method]
Stoer Wagner Min-Cut Algo
Hop-Kraft BPM
Edmond Blossom Shrinking Algorithm
(h)Other Important Topics On Graphs
2-SAT,
LCA
Maximum Cardinality Matching
Application Flow
Min Path Cover Over Dag
Independent Edge Disjoint Path
Minimum Vertex Cover
Maximum Independent Set
Data Structures:
Arrays
Linked List
Trees (Binary Tree And Binary Search Tree)
Stacks
Queues
Heap
Hash Tables
Disjoint-Set Data Structures
Trie
Segment Tree
Binary Index Tree
Treap
Searching And Sorting:
Linear Search
BInary Search
Ternary Search
Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Quick Select
Heap Sort
Radix Sort
Counting Sort
Greedy:
Classical Problems of Greedy & Concept
example : Fractional Knapsack
Dynamic Programming Classical Problems
Edit Distance
Egg Dropping Puzzle
Integer Knapsack
Largest Independent Set
Longest Biotonic Subsequence
Longest Common Subsequence
Longest Common Substring
Longest Increasing Subsequence
Longest Palindromic Subsequence
Longest Palindromic Substring
Longest Substring Without Repeating Character
Matrix Chain Multiplication
Max Size Square Submatrix With One
Maximum Length Chain Pairs
Maximum Sum Increasing Subsequence
Optimal Binary Search Tree
Palindrome Partition Problem
Set Partition Problem
Subset Sum
Word Wrap Problem
Dynamic Programming Advanced Techniques
DP + Tree
DP + Bit Masking
DP + Binary Search
DP + Graph
DP + Matrix Exponentiation
DP + Probability Space
DP + Crack Recurrence
Divide & Conquer
Classical Problems & Concepts
Merge Sort
Closest Pair Points
Other Algorithm Design Techniques :
BackTracking
Man In Middle
Newton-Raphson to reach the fixed point
Brute Force
Constructive Algo
Sliding Window
Pancake Sorting
No comments:
Post a Comment