-
Notifications
You must be signed in to change notification settings - Fork 13
/
techniques.txt
156 lines (156 loc) · 3.25 KB
/
techniques.txt
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
Recursion
Divide and conquer
Finding interesting points in N log N
Greedy algorithm
Scheduling
Max contigous subvector sum
Invariants
Huffman encoding
Graph theory
Dynamic graphs (extra book-keeping)
Breadth first search
Depth first search
* Normal trees / DFS trees
Dijkstra's algoritm
MST: Prim's algoritm
Bellman-Ford
Konig's theorem and vertex cover
Min-cost max flow
Lovasz toggle
Matrix tree theorem
Maximal matching, general graphs
Hopcroft-Karp
Hall's marriage theorem
Graphical sequences
Floyd-Warshall
Eulercykler
Flow networks
* Augumenting paths
* Edmonds-Karp
Bipartite matching
Min. path cover
Topological sorting
Strongly connected components
2-SAT
Cutvertices, cutedges och biconnected components
Edge coloring
* Trees
Vertex coloring
* Bipartite graphs (=> trees)
* 3^n (special case of set cover)
Diameter and centroid
K'th shortest path
Shortest cycle
Dynamic programmering
Knapsack
Coin change
Longest common subsequence
Longest increasing subsequence
Number of paths in a dag
Shortest path in a dag
Dynprog over intervals
Dynprog over subsets
Dynprog over probabilities
Dynprog over trees
3^n set cover
Divide and conquer
Knuth optimization
Convex hull optimizations
RMQ (sparse table a.k.a 2^k-jumps)
Bitonic cycle
Log partitioning (loop over most restricted)
Combinatorics
Computation of binomial coefficients
Pigeon-hole principle
Inclusion/exclusion
Catalan number
Pick's theorem
Number theory
Integer parts
Divisibility
Euklidean algorithm
Modular arithmetic
* Modular multiplication
* Modular inverses
* Modular exponentiation by squaring
Chinese remainder theorem
Fermat's small theorem
Euler's theorem
Phi function
Frobenius number
Quadratic reciprocity
Pollard-Rho
Miller-Rabin
Hensel lifting
Vieta root jumping
Game theory
Combinatorial games
Game trees
Mini-max
Nim
Games on graphs
Games on graphs with loops
Grundy numbers
Bipartite games without repetition
General games without repetition
Alpha-beta pruning
Probability theory
Optimization
Binary search
Ternary search
Unimodality and convex functions
Binary search on derivative
Numerical methods
Numeric integration
Newton's method
Root-finding with binary/ternary search
Golden section search
Matrices
Gaussian elimination
Exponentiation by squaring
Sorting
Radix sort
Geometry
Coordinates and vectors
* Cross product
* Scalar product
Convex hull
Polygon cut
Closest pair
Coordinate-compression
Quadtrees
KD-trees
All segment-segment intersection
Sweeping
Discretization (convert to events and sweep)
Angle sweeping
Line sweeping
Discrete second derivatives
Strings
Longest common substring
Palindrome subsequences
Knuth-Morris-Pratt
Tries
Rolling polynom hashes
Suffix array
Suffix tree
Aho-Corasick
Manacher's algorithm
Letter position lists
Combinatorial search
Meet in the middle
Brute-force with pruning
Best-first (A*)
Bidirectional search
Iterative deepening DFS / A*
Data structures
LCA (2^k-jumps in trees in general)
Pull/push-technique on trees
Heavy-light decomposition
Centroid decomposition
Lazy propagation
Self-balancing trees
Convex hull trick (wcipeg.com/wiki/Convex_hull_trick)
Monotone queues / monotone stacks / sliding queues
Sliding queue using 2 stacks
Persistent segment tree