Which cycle detection within a directed graph are more efficient than O(n^2)? [closed]
Tarjan’s strongly connected components algorithm has O(|E| + |V|) time complexity. For other algorithms, see Strongly connected components on Wikipedia.
algorithm
First occurrence in a binary search
An addition to Jon Skeets post: The potential faster implementation is actually not hard to implement and adds only 2 lines of code, here is how I’d do it: if (midVal < key) low = mid + 1; else if (midVal > key) high = mid – 1; else if (low != mid) //Equal but … Read more
Maximum sum of non consecutive elements
Dynamic programming? Given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(-1) = 0 (used in the recurrence), M(0) = A[0], and M(i) = max(M(i – 1), M(i – 2) + A[i]) for i = 1, …, n. M(n) is the solution we want. This is O(n). … Read more
How to detect how similar a speech recording is to another speech recording?
A lot of people seem to be suggesting some sort of edit distance, which IMO is a totally wrong approach for determining the similarity of two speech patterns, especially for patterns as short as OP is implying. The specific algorithms used by speech-recognition in fact are nearly the opposite of what you would like to … Read more
Use Dijkstra’s to find a Minimum Spanning Tree?
The answer is no. To see why, let’s first articulate the question like so: Q: For a connected, undirected, weighted graph G = (V, E, w) with only nonnegative edge weights, does the predecessor subgraph produced by Dijkstra’s Algorithm form a minimum spanning tree of G? (Note that undirected graphs are a special class of … Read more
Smoothing data from a sensor
The simplest is to do a moving average of your data. That is, to keep an array of sensor data readings and average them. Something like this (pseudocode): data_X = [0,0,0,0,0]; function read_X () { data_X.delete_first_element(); data_X.push(get_sensor_data_X()); return average(data_X); } There is a trade-off when doing this. The larger the array you use, the smoother … Read more
Find maximum of three number in C without using conditional statement and ternary operator
Taking advantage of short-circuiting in boolean expressions: int max(int a, int b, int c) { int m = a; (m < b) && (m = b); //these are not conditional statements. (m < c) && (m = c); //these are just boolean expressions. return m; } Explanation: In boolean AND operation such as x && … Read more
Automatic enhancement of scanned images
translated to hsv V-layer is corrected by scaling values from (min,max) range to (0,255) range assembled back to rgb correcting R,G,B layers of result by same idea as the V-layer on second step there is no aforge.net code, because it processed by php prototype code, but afaik there is no any problem to do such … Read more
Counting palindromic substrings in O(n)
The following site shows an algorithm for computing the longest palindromic substring in O(n) time, and does so by computing the longest palindromic substring at every possible center and then taking the maximum. So, you should be able to easily modify it for your purposes. http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ EDIT: The first link looks a little shaky upon … Read more
What is an efficient algorithm for counting the number of triangles in a graph? [closed]
You will need depth first search. The algorithm will be: 1) For the current node ask all unvisited adjacent nodes 2) for each of those nodes run depth two check to see if a node at depth 2 is your current node from step one 3) mark current node as visited 4) on make each … Read more