My programming practice

Hi! This is just some notes from my algo and not only practice. If you find some mistake please create an issue or pull request with fixes. Thanks!

Data structures

1. Binary heap.
2. Set with iterators.
3. Unordered map with iterators.
4. Segment tree(sum) with 2N memory use.
5. Segment tree with lazy propagation.
6. DSU(disjoint set union).
7. DSU with backup.
8. Basic Bloom filter.
9. Counting Bloom filter.
10. Explicit treap.
11. Implicit treap.
12. Fenwick tree.
13. Queue based on two stacks with template functor.
14. Bidirectional list.
15. Deque based on vector of blocks(without invalidation when container relocate).
16. Cow-vector(relocate if and only if we want to change it and do not relocate if read-only).
17. Intrusive list.

Math algorithms

Matrix algos

1. LU decomposition.
2. LDLT decomposition.
3. Gauss method to find inverse matrix.
4. Matrix transposition.
5. Tridiagonal matrix algorithm.
6. QR algorithm to find eigenvalues of matrix and eigenvectors of symmetric matrix(Givens rotation, Householder transformation).

Approxes

1. Lagrange interpolation.
2. Hermit interpolation(with Newton interpolation).
3. Spline interpolation.
4. Least square method.
5. 2D Lagrange.
6. Value in point on 100 equallyspaced points.
7. Newton method for solving nonlinear system.
8. Power method to find max eigenvalue.
9. Simpson integration.
10. Count definite integral with five points method and adaptive steps.
11. Count definite integral with Gauss-3 and adaptive steps.
12. Solve integral equation with approximation kernel with degenerate kernel.

Other

1. Binary exponential.
2. Eiler function.
3. Fast finding nth fibonacci number modulo m.
4. Fast finding nth fibonacci number modulo m on compilation time.
5. Danilevskiy algo to find characteristic polynomial and Newton algo to find real roots.

Some algos in pictures

Graphs

1. Dijkstra algorithm.
2. LCA(less common ancestor) with binary lifts.
3. Find all minimum spanning trees in O(ans * nmlog(n)).
4. Parallel Kruskal.
5. Check two trees for isomorphism(this is probability solver).
6. Some examples.

Uncategorized

1. Knut-Morris-Pratt algo.
2. Rabin-Carp algo.

C++

Algos

0. Generate all permutations in lexicographic order.
1. LRU-cache.

Classes

1. Vector and tests.
2. Unique ptr.
3. Shared and weak ptr.
4. Any.

Concurrency

1. FindIf(multithreading function to find all numbers in some range that satisfies some unary predicate).
2. Reduce(multithreading function than compute result of some associative commutative binary predicate to all vector elements).
3. Spinlock.
4. Read-write lock.
5. Buffered channel(class that provides synchronization between threads when store some values(in buffer)).
6. Unbuffered channel(same as buffered channel but without buffer).
7. Concurrent unordered map.
8. Matrix multiplication algos(trivial and by block) with openmp.

Golang

0. Effective reverse.
1. Sprintf.
2. LRU-cache.

Linux programming

1. File system tasks.
2. Processes tasks.
3. Shell tasks.
4. Shell2 tasks.
5. GNU cat.
6. Custom pipeline.

Windows programming

1. Pipeline.
2. Wrapper for winapi conditional variable.
3. Wrapper for winapi critical section.

MapReduce

1. Inplace(with solve for WordCount).
2. Web Robot.

Other

1. Rational class.
2. External sort.
3. Get hex string from number(C++).