CS
Algorithms
Problems Base course RU

Solves

distinct counting

Articles

SYS Data structure HyperLogLog The number of distinct elements of a stream in a kilobyte of memory: long runs of zeros in hashes and an average over registers. O(1) per element, O(m) per estimate 2 problems

Problems

An estimate from hashes Words across chapters

Often together

sketch 1 streaming 1 hashing 1 probabilistic 1 analytics 1 databases 1 in production 1

Written by Viacheslav Legostin. Everything is free; readers’ code is not stored.

Computer Science The algorithms catalogue Problems Base course Mathematics legost.in

The algorithms catalogue

Problems

SRT Searching and sorting

  1. Binary search
  2. Binary search on the answer
  3. Exponential search
  4. Interpolation search
  5. External sorting
  6. Heapsort
  7. Counting sort and radix sort

DS Data structures

  1. Dynamic array
  2. Linked list
  3. Hash table
  4. Cuckoo hashing
  5. Bloom filter
  6. Binary heap
  7. Binary search tree
  8. AVL tree
  9. B-tree
  10. Disjoint set union
  11. Fenwick tree
  12. LRU cache

GRA Graphs

  1. Storing a graph
  2. Breadth-first search
  3. Depth-first search
  4. Bridges and articulation points
  5. Dijkstra's algorithm
  6. A*
  7. Bidirectional search
  8. The Bellman–Ford algorithm
  9. Floyd–Warshall algorithm
  10. Johnson's algorithm
  11. Contraction hierarchies
  12. Maximum flow
  13. Dinic's algorithm
  14. Graph colouring
  15. Bipartite matching
  16. Hungarian algorithm
  17. Eulerian path
  18. Lowest common ancestor
  19. Heavy paths
  20. Centroid decomposition

STR Strings and text

  1. Prefix function and KMP
  2. The Aho–Corasick algorithm
  3. Boyer–Moore
  4. The Burrows–Wheeler transform
  5. Manacher’s algorithm
  6. Edit distance
  7. BK-tree
  8. Huffman code
  9. LZ77 and LZW

DP Dynamic programming

  1. Dynamic programming
  2. The knapsack problem
  3. Longest increasing subsequence
  4. Longest common subsequence
  5. Interval DP
  6. Bitmask DP
  7. Digit DP
  8. Convex hull trick
  9. Knuth and divide-and-conquer optimisations

PAR Paradigms

  1. Greedy algorithms
  2. Backtracking
  3. Branch and bound
  4. Divide and conquer
  5. Closest pair of points
  6. Meet in the middle

NUM Numbers and algebra

  1. Euclid's algorithm
  2. Fast exponentiation
  3. Chinese remainder theorem
  4. Big integers
  5. Karatsuba multiplication
  6. Fast Fourier transform
  7. Matrices and recurrences
  8. Gaussian elimination

GEO Geometry

  1. Vectors and orientation
  2. Convex hull
  3. Delaunay triangulation and Voronoi diagram
  4. k-d tree

NUM~ Numerical methods

  1. Bisection and Newton's method
  2. Gradient descent
  3. Kahan summation

SYS Systems and big data

  1. Consistent hashing
  2. Count-Min Sketch
  3. HyperLogLog
  4. Inverted index and BM25
  5. LSM tree
  6. Retry with jitter
  7. CRDT
  8. LFU and ARC

ML Data and machine learning

  1. k-means
  2. DBSCAN
  3. k nearest neighbours
  4. Decision tree
  5. Linear regression
  6. Logistic regression
  7. Recommendations by matrix factorization
  8. Perceptron and backpropagation

RND Randomness

  1. Las Vegas and Monte Carlo
  2. Genetic algorithm

TEC Techniques

  1. Big O
  2. Fast input and output
  3. How to benchmark honestly
  4. Cache-friendly data
  5. Complexity from measurements
  6. Memoization
  7. Numbers worth knowing
  8. Amortized analysis
  9. Choosing a data structure
  10. How much memory it takes
  11. Coordinate compression
  12. Bit tricks