# Graph

intro and definition

1. subgraph
2. connectivity
3. trees and forest
4. 1 simple unbalanced tree sort

# BFS

1. Definition: A BFS traversal of a graph returns the nodes of the graph level by level.
2. Application form: by queue

A queue is a line. If you’re the first to get in a bus line, you’re the first to get on the bus. First In, First Out.

## leetcode

solution

Attention

• empty data set may cause exception
• list length should not change during process of fetching one element, should use offset to start with

# DFS

1. definition
2. usage
3. complexity
4. further usage (1. path between two vertices 2. find a cycle in the graph)

## leetcode

DFS solution

Union find solution

# Union find

In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal’s algorithm for finding the minimum spanning tree of a graph.

make connections

1. usage seriano
2. find
3. union
4. find and compression

# Greatest Common Divisor Algorithm

In mathematics, the Euclidean algorithm[a], or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. The fact that the GCD can always be expressed in this way is known as Bézout’s identity.

Binary Greatest Common Divisor Algoroithm

The binary GCD algorithm, also known as Stein’s algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein’s algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known in 1st-century China.

Common GCD Algorithm

Benchmark

1. Euclidean
1. Binary

ALMOST double its effience!!!

1. Euclidean
1. Binary

Each op differs by almost 0.5 ms! still quite fast in practice

# Popcount Algorithm(Hamming Weight)

Question: how to count all the 1s in a 0-1 binary string of a number

1. arithmatical op: %2 == 1; n /= 2
2. bitwise op

2.1 iterated popcount
2.2 sparse popcount
2.3 dense popcount
2.4 lookup popcount
2.5 parallel popcount
2.6 to be continued…. cannot understand any more

code

test

benchmark

as to lookup popcount, the approach is use space to exchange time
thus, parallel pop count uses devide-and-conquer strategy to count.

leetcode

Solution

Refer

Hamming weight

Bit-counting algorithms

Fast Bit Counting

Calculating Hamming Weight in O(1)

Hamming Weight的算法分析

popcount 算法分析

Hamming Weight的算法分析（转载）

Fermat number

## Sieve of Eratosthenes derived from popcount

In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

Two Approaches to get prime table

1. normal

code

test

benchmark

1. eratosthenes

code

test

benchmark

The bigger n is, the more time the normal algorithm consumes each op!

Appearantly, use the prime table and sieve is the best way to get a bunch of primes that is smaller than n.

Refer

Euclidean algorithm

Sieve of Eratosthenes