go computer science playground

Algorithms

Distributed Computing

doc

Database

• MultiVersion Concurrency Control
• Gossip Protocol
• Atomic Commit

Model

• message passing model

Leader Election

Consensus

• Paxos
• Raft

Mutex (Mutual exclution)

• spin lock
• ticket lock

Cache

• write through/around/back

Cache Eviction Policies

• fifo (Firstly In, First Out)
• lifo (Last In, First out)
• lru (Least Recently Used)
• tlru (Time aware Least Recently Used)
• mru (Most Recently Used)
• plru (Pseudo LRU)
• rr (Random Replacement)
• slru (Segmented LRU)
• lfu (Least Frequently Used)
• lfuda (LFU with Dynamic Aging)
• lirs (Low Inter-reference Recency Set)
• clockpro
• arc (Adaptive Replacement Cache)
• ac (Adaptive Climb)
• car (Adaptive Climb)
• mq (Multi Queue)
• lfd (Longest Forward Distance)
• fwf (Flush When Full)

Rate Limiter

• array push
• increment
• see https://redis.io/commands/incr

Semaphore

• counting
• weighted

Sort

• bubble sort
• bucket sort
• heap sort
• merge sort
• quick sort
• insertion sort
• introspective sort
• tim sort

Search

• Linear Search
• Binary Search
• Jump Search

Coding

• lz77
• huffman
• runlength
• lz78
• lzw
• base64

Diff

• dp
• myers's diff

Math

basic functions

• factorial
• combination
• permutation
• absolute
• square
• ceil
• floor
• sqrt
• power
• logarithm
• mod
• exp
• sin
• cos
• tan
• sinc
• arcsin
• arccos
• arctan
• almost equal
  • epsilon comparison
  • unit in the last place: https://en.wikipedia.org/wiki/Unit_in_the_last_place

complex number

• test
• add, sub, mul, div
• abs, arg
• reciprocal, conjugate
• euler
• equal

interpolation

• linear
• cosine

numerical calculation

• newton
• quasi newton
• BFGS: Broyden–Fletcher–Goldfarb–Shanno
• Jacobi method
• Gauss-Seidel method
• Successive Over-Relaxation
• gaussian elimination
• euler
• Leap-Frog
• Runge–Kutta

descrete logarithm problem (dlp)

• greedy

elliptic curve dlp (ecdlp)

• hoge

Optimization

• Simulated Annealing
• genetic algorithm
• ant colony optimization
• Particle Swarm Optimization

Statistics

• Metropolis-Hastings
• Hamiltonian MC
• Gibbs sampling

Pseudorandom

• midsquare
• linear congruential generators
• gfsr (generalized feedback shift register)
• twisted gfsr
• mersenne twister
• xorshift
• Blum-Blum-Shub
• perlin noise

Version solving

• PubGrub

Cryptology

• enigma

Load balancing

• round robin
• weighted round robin
• least connection
• Agent-Based Adaptive Load Balancing
• Chained Failover
• Weighted Response Time
• Source IP Hash

Hash

uncryptographic hash

• fnv

cryptographic hash

• md5
• sha-1
• ripemd-160
• bcrypt
• whirlpool
• sha-2
• sha-3

Data structures

List

• doubly linked list
• queue
• stack

Trees

• binary search tree
• heap
• treap
• btree
• Log-structured merge-tree

hashtable

• robin hood hashing
• consistent-hashing with treap (get operation: O(lon N))
• cockoo hashing

Succinct Data Struture

• bit vector
• wavelet tree
• wavelet matrix

Probabilistic Data Structures

• bloom filter
  • wiredtiger: https://github.com/wiredtiger/wiredtiger/wiki/LSMTrees-Bloom
  • Building a Better Bloom Filter: https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
• counting filter
• quotient filter
• cuckoo filter
• xor filter

Etc

• bits

References

• https://en.wikipedia.org/wiki/List_of_data_structures
• https://en.wikipedia.org/wiki/List_of_algorithms
• https://en.wikipedia.org/wiki/List_of_algorithm_general_topics
• https://en.wikipedia.org/wiki/List_of_terms_relating_to_algorithms_and_data_structures
• https://en.wikipedia.org/wiki/List_of_computability_and_complexity_topics
• https://www.geeksforgeeks.org/