A* search algorithm

A* search is an informed search algorithm used for path-finding and graph traversal. It combines the advantages of both Dijkstra’s algorithm (in that it can find a shortest path) and Greedy Best-First-Search (in that it can use a heuristic to guide search). It combines the information that Dijkstra’s algorithm uses (favoring vertices that are close to the starting point) and information that Best-First-Search uses (favoring vertices that are closer to the goal).

Continue reading

Advertisements

Divisibility rules

A number x is said to be divisible by y, written y | x (read y divides x), iff ∃ k ∈ Z: ky = x. Divisibility rules provide a way of determining whether a given (large) number is divisible by another (small) number without actually performing the division. They usually transform a number into a smaller number while preserving divisibility by a fixed divisor.

Continue reading

Range updates with BIT / Fenwick Tree

I described implementation of BIT/Fenwick tree in an earlier post as a way of maintaining cumulative frequency table, which allows operations like updating any single element and querying sum of elements in a range [a…b] in logarithmic time. I recently found out that this is only one of the ways of using a BIT. A BIT can in fact be operated in one of three modes:

Continue reading