Articles in the Algorithm category

1. Bellman-Ford and systems of difference constraints

   Motivation

   Bellman-Ford is an algorithm for finding shortest paths from a single source vertex to multiple target vertices in a weighted graph \(G(V,E)\) whose edge weights can be negative. The algorithm can also detect negative cycle (if any) in the graph. Its time complexity is \(O(|V|*|E …

2. Reservoir Sampling

   Getting started

   Reservoir sampling concerns with choosing \(k\) items (i.e., a random sample of size \(k\) or \(k\)-sample for short) from a population of size \(n\) (\(n > k\)) without replacement such that each chosen item is selected randomly with equal chance from the population.

   Q1. What is the …