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
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
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
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
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
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
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
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
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
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