## Find cycle of shortest length in a directed graph with positive weights

You can easily modify Floyd-Warshall algorithm. (If you’re not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms). Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won’t affect algorithm itself, as those zeroes weren’t … Read more

## Iterating over a Binary Tree with O(1) Auxiliary Space

Geez, I’ll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time. static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr … Read more

## Connected Component Labeling – Implementation

I’ll first give you the code and then explain it a bit: // direction vectors const int dx[] = {+1, 0, -1, 0}; const int dy[] = {0, +1, 0, -1}; // matrix dimensions int row_count; int col_count; // the input matrix int m[MAX][MAX]; // the labels, 0 means unlabeled int label[MAX][MAX]; void dfs(int x, … Read more

## Algorithm to find the most common substrings in a string

This is as task similar to Nussinov algorithm and actually even simpler as we do not allow any gaps, insertions or mismatches in the alignment. For the string A having the length N, define a F[-1 .. N, -1 .. N] table and fill in using the following rules: for i = 0 to N … Read more

## Is there any fast method of matrix exponentiation?

You could factor the matrix into eigenvalues and eigenvectors. Then you get M = V * D * V^-1 Where V is the eigenvector matrix and D is a diagonal matrix. To raise this to the Nth power, you get something like: M^n = (V * D * V^-1) * (V * D * V^-1) … Read more

## How Can I Best Guess the Encoding when the BOM (Byte Order Mark) is Missing?

Maybe you can shell out to a Python script that uses Chardet: Universal Encoding Detector. It is a reimplementation of the character encoding detection that used by Firefox, and is used by many different applications. Useful links: Mozilla’s code, research paper it was based on (ironically, my Firefox fails to correctly detect the encoding of … Read more

## Fuzzy date algorithm

There is a property in NSDateFormatter – “doesRelativeDateFormatting”. It appears only in 10.6/iOS4.0 and later but it will format a date into a relative date in the correct locale. From Apple’s Documentation: If a date formatter uses relative date formatting, where possible it replaces the date component of its output with a phrase—such as “today” … Read more

## Fastest available algorithm for distance transform

This paper reviews the known exact distance transform algorithms: “2D Euclidean distance transform algorithms: A comparative survey” https://rfabbri.github.io/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf The fastest exact distance transform is from Meijster: “A General Algorithm for Computing Distance Transforms in Linear Time.” http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf The design of the algorithm is particularly well suited for parallel calculation. This is implemented in my open … Read more

## What is the algorithm that opencv uses for finding contours?

If you read the documentation it is mentioned this function implements the algorithm of: Suzuki, S. and Abe, K., Topological Structural Analysis of Digitized Binary Images by Border Following. CVGIP 30 1, pp 32-46 (1985) OpenCV is open source if you want to see how this is implemented just need to read the code: https://github.com/opencv/opencv/blob/master/modules/imgproc/src/contours.cpp#L1655 … Read more

## O(klogk) time algorithm to find kth smallest element from a binary heap

Well, your intuition was right that we need extra data structure to achieve O(klogk) because if we simply perform operations on the original heap, the term logn will remain in the resulting complexity. Guessing from the targeted complexity O(klogk), I feel like creating and maintaining a heap of size k to help me achieve the … Read more