home

 

shortlist

Metropolis–Hastings algorithm

In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult.

The algorithm was named after Nicholas Metropolis, who authored the 1953 paper Equation of State Calculations by Fast Computing Machines together with Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller and Edward Teller.

<read on>

Shor’s algorithm

Shor’s algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor.

The algorithm is significant because it implies that public key cryptography might be easily broken, given a sufficiently large quantum computer. RSA, for example, uses a public key N which is the product of two large prime numbers. One way to crack RSA encryption is by factoring N, but with classical algorithms, factoring becomes increasingly time-consuming as N grows large; more specifically, no classical algorithm is known that can factor in time O((log N)k) for any k. By contrast, Shor’s algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor’s algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor’s algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

YOLO

YOLO (You only look once) is a real-time object detection system. On a Pascal Titan X it processes images at 30 FPS and has a mAP of 57.9% on COCO test-dev.

YOLOv3 is extremely fast and accurate. In mAP measured at .5 IOU YOLOv3 is on par with Focal Loss but about 4x faster. Moreover, you can easily tradeoff between speed and accuracy simply by changing the size of the model, no retraining required! <read on>

Adaboost

Ensemble learning  deals with methods which employ multiple learners to solve a problem. The generalization ability of an ensemble is usually significantly better than that of a single learner, so ensemble methods are very attractive. The AdaBoost algorithm proposed by Yoav Freund and Robert Schapire is one of the most important ensemble methods, since it has solid theoretical foundation, very accurate prediction, great simplicity (Schapire said it needs only “just 10 lines of code”), and wide and successful applications. <read on>

Ethash

Ethash is the proof-of-work function in Ethereum-based blockchain currencies. It uses Keccak, a hash function eventually standardized to SHA-3. These two are different, and should not be confused. Since version 1.0, Ethash has been designed to be ASIC-resistant via memory-hardness (harder to implement in special ASIC chips) and easily verifiable.

It also uses a slightly modified version of earlier Dagger and Hashimoto hashes to remove computational overhead.

Previously referred to as Dagger-Hashimoto, the Ethash function has evolved over time. Ethash uses an initial 1 GB dataset known as the Ethash DAG and a 16 MB cache for light clients to hold. These are regenerated every 30,000 blocks, known as an epoch. Miners grab slices of the DAG to generate mix-hashes using transaction and receipt data, along with a cryptographic nonce to generate a hash below a dynamic target difficulty.

Floyd-Warshall Algorithm

The Floyd–Warshall algorithm is an example of dynamic programming, and was published in its currently recognized form by Robert Floyd in 1962. It is also known as all pair shortest path problem. Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). <read on>

Bubble sort

Perhaps the first computer algorithm ever created (1963). Developed by system development corporation, Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
<read on>

K-nearest neighbor classification

One of the simplest, and rather trivial classifiers is the Rote classifier, which memorizes the entire training data and performs classification only if the attributes of the test object match one of the training examples exactly. An obvious drawback of this approach is that many test records will not be classified because they do not exactly match any of the training records. <read on>

Forward–backward algorithm

The forward-backward algorithm is an algorithm for computing posterior marginals in a hidden Markov model (HMM). It is based on dynamic programming, and has linear complexity in the length of the sequence. It is used as a component of several other algorithms, such as the Baum_Welch algorithm and block Gibbs sampling in factorial HMMs. <read on>

X11

X11 algorithm was developed by Dash developers and its called a Proof-of-Work. The algorithm was based on multiple rounds of different hashes (blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo) by making it one of the safest cryptocurrency in existence.

The cryptocurrencies that are mined using this algorithm are:

  • MonetaryUnit
  • Karmacoin
  • StartCoin
  • Dash
  • XCurrency

It is an altcoin that was forked from the Bitcoin protocol. The currency permits fast transactions that can be untraceable. 45% of mined coins go to miners, 45% to masternodes, and 10% into a fund that the DAO invests.