~iany/ Menu
  • Series
  • Tags
  1. Home
  2. Tags
  3. Algorithm

Algorithm

A collection of 6 articles

Most-Significant Bit

The function most-significant bit msb(n) returns the index of the highest 1 bit in the integer n. MSB can be resolved using integer algorithm to find the rank in the array of all the powers of 2.

Updated Nov 25, 2020  •  1 min read

Splay Tree

Splay tree is a balanced search tree that it splays the just touched node. Splay Tree CS166: Data Structures

Updated Nov 25, 2020  •  1 min read

x-Fast Trie

The data structure x-Fast Trie is a binary trie that The nodes of each layer are stored in Cuckoo hash table. Missing 0 and 1 child pointers are used to store links to siblings.

Updated Nov 25, 2020  •  1 min read

y-Fast Trie

A y-Fast trie splits nodes into blocks. Each block is a balanced search tree and has 2/w to 2w nodes. The block maximums constitutes an ♯ x-Fast Trie. x-Fast and y-Fast Tries CS166: Data Structures

Updated Nov 25, 2020  •  1 min read

Integer Longest Common Prefix

lcp(m, n) = w - 1 - msb(m xor n) where w is the number of bits in a word, and msb is ♯ Most-Significant Bit.

Updated Aug 29, 2020  •  1 min read

Study on Alias Method

@miloyip has published a post recently which motioned the Alias Method to generate a discrete random variable in O(1). After some research, I find out that it is a neat and clever algorithm. Following are some notes of my study on it.

Updated Jan 28, 2021  •  7 min read

© 2022  •  ~iany/  •  CC-BY-SA 4.0

浙ICP备17004784号-1