reminder
coding interview preparation
Dynamic Programming
- Longest Common Subsequence
- Longest Increasing Subsequence
- Edit Distance
- Minimum Partition
- Ways to Cover a Distance
- Longest Path In Matrix
- Subset Sum Problem
- Optimal Strategy for a Game
- 0-1 Knapsack Problem
- Assembly Line Scheduling
- Optimal Binary Search Tree
- All DP Algorithms
BackTracking
- Rat in a Maze
- N Queen Problem
- Subset Sum
- m Coloring Problem
- Hamiltonian Cycle
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
Graph Algorithms : One of the most important topic which you can not ignore if preparing for ACM – ICPC.
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Shortest Path from source to all vertices Dijkstra
- Shortest Path from every vertex to every other vertex Floyd Warshall
- Minimum Spanning tree Prim
- Minimum Spanning tree Kruskal
- Topological Sort
- Johnson’s algorithm
- Articulation Points (or Cut Vertices) in a Graph
- Bridges in a graph
- All Graph Algorithms
Basic Mathematics
Arithmetic :
Programmers must know how integers and real numbers are represented internally and should be able to code high-precision numbers. Bit manipulation tricks and knowing library functions for number basic arithmetic would be very helpful.
Number theory : Knowing some of these concepts would save a lot of time and efforts while programming in the contests.
- Modular Exponentiation
- Modular multiplicative inverse
- Primality Test | Set 2 (Fermat Method)
- Euler’s Totient Function
- Sieve of Eratosthenes
- Convex Hull
- Basic and Extended Euclidean algorithms
- Segmented Sieve
- Chinese remainder theorem
- Lucas Theorem
Combinatorics :
Although directly might not seam to be important, Combinatorics is important to estimate asymptotic complexity of algorithms.
Analysis of Algorithms
- Combinatorial Game Theory | Set 1 (Introduction)
Geometrical Algorithms
-
Convex Hull
-
Graham Scan
-
Line Intersection
-
Matrix Exponentiation and this
-
Online construction of 3-D convex hull
-
Bentley Ottmann algorithm to list all intersection points of n line segments
-
Rotating Calipers Technique
-
Area/Perimeter of Union of Rectangles
-
Closest pair of points
-
Area of Union of Circles
-
Delaunay Triangulation of n points
-
Voronoi Diagrams of n points using Fortune’s algorithm
-
Point in a polygon problem
-
Network Flow Algorithms
-
Maxflow Ford Furkerson Algo and Edmond Karp Implementation
-
Min cut
-
Stable Marriage Problem
-
Maximum flow using Dinic’s Algorithm
-
Minimum Cost Flow Problem
-
Successive Shortest path Algorithm
-
Cycle Cancelling algorithm
-
Maximum weighted Bipartite Matching (Kuhn Munkres algorithm/Hungarian Method)
-
Hungarian Algorithm Wiki
-
Hungarian Algorithm for Assignment Problem
-
Maximum Bipartite Matching
-
Stoer Wagner min-cut algorithm
-
Maximum matching in general graph (Blossom Shrinking)
-
Gomory-Hu Trees
-
Chinese Postman problem(Please see this too)
-
Hopcroft–Karp Algorithm for Maximum Matching
More Advanced Stuff
- Bit Algorithms
- Randomized Algorithms
- Branch and Bound
- Mathematical Algorithms
- Heavy Light Decomposition
- A* Search