-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTopics
81 lines (74 loc) · 2.14 KB
/
Topics
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
Data Structures
--------------------
Basic data structures (C++ STL):
Vector
Queue
Stack
Priority Queue
Set - efficient O(log n) operations
Map - efficient O(log n) operations
Map hashing implementation - c++ unordered_map
Bitset
Union-Find (disjoint sets data structure)
Fenwick Tree ( efficient O(log n) range sum queries and updates)
Segment Tree (efficient O(log n) range queries and updates (many operations))
Segment Tree with Lazy Propagation (same but with range updates)
Trie (strings data structure)
Sparse table (range minimum query in O(1), no update)
SQRT Decomposition (method for performing operations in O(sqrt n)
Graph Theory
--------------------------
Graph Representation (adjacency list, adjacency matrix, edges list)
DFS and BFS (graph search)
Dijkstra's Algorithm (single source shortest path algorithm)
Floyd-Warshall's Algorithm (all pairs shortest path algorithm)
Flood-Fill
Finding connected components (uses union-find)
Minimum Spanning Tree (Kruskal Algorithm, Prim Algorithm)
Topological Sorting (ordering in a directed acyclic graph)
Flow Algorithms (Edmonds-Karp, Dinic, Push-relabel)
Bipartite Graphs problems (maximum matching, bipartite testing)
Strongly Connected Components (tarjan algorithm)
Articulation Points and Bridges
Tree Diameter
Lowest Common Ancestor / Binary Lifting on binary trees
Heavy-Light Decomposition
Steiner Tree
Travelling Salesman Problem
Dynamic Programming
---------------------
O(n) fibonacci with DP
Longest Increasing Subsequence
Knapsack Problem
Longest Common Subsequence
Edit Distance problem
Coin Change problem
Subset sum problem
Digit DP
Dp with Bitmask
Math
------------------
Primality test
Sieve of Eratosthenes (generating prime numbers)
Prime Factors and problems
Matrix operations
Fibonacci numbers (fibonacci in O(log n) with matrix exponentiation)
Modulo Arithmetic
Modular Inverse
Fast Exponentiation
Combinatorics
Euler's totient function
Probability
Game Theory
Geometry
---------------------
Geometry topics, representation
Sweep Line techniques
Convex Hull problem
Closest pair of points O(n log n) with sweep line
Union of rectangles
Strings
--------------
Suffix Tree
Suffix Array
KMP