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
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
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
Fast algorithms for computing the factorial
Check out this paper (PDF link) by Richard Fateman. The code samples are in Lisp, in but in any event, much of the secret boils down to minimizing the number of bignum (arbitrary precision integer) calculations you have to do. Naturally, if you don’t need/have bignums, it’s trivial; either a lookup table or a simple … Read more
How to detect significant change / trend in a time series data? [closed]
As has been pointed out already, you’re not looking for the derivative. You’re really looking for a “significant change” detection algorithm for a time series. You’ll certainly want a smoothing filter (and the moving average filter is fine — see Bjorn’s answer for this part). But in addition to the smoothing filter, you will also … Read more
Cheap algorithm to find measure of angle between vectors
If you don’t need the actual euclidean angle, but something that you can use as a base for angle comparisons, then changing to taxicab geometry may be a choice, because you can drop trigonometry and it’s slowness while MAINTAINING THE ACCURACY (or at least with really minor loosing of accuracy, see below). In main modern … Read more
What are probabilistic data structures?
There are probably a lot of different (and good) answers, but in my humble opinion, the common characteristics of probabilistic data structures is that they provide you with approximate, not precise answer. How many items are here? About 1523425 with probability of 99% Update: Quick search produced link to decent article on the issue: Probabilistic … Read more