New answers tagged search-algorithms
1
To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort.
If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of ...
0
In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.
Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the ...
0
I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation.
My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other ...
0
Suppose that the array $A$ is chosen in the following way:
Sample $n$ real numbers uniformly from the interval $[0,1]$.
Sort the $n$ samples.
Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices ...
0
You could do ternary search by splitting into three parts, use one comparison to see if the key has to be in the first third, and another one to distinguish between second and third stretch if it isn't in the first one. Assuming uniformly distributed searches, this would reduce the range to a third with $1/3 + 2 \cdot 2/3 = 5/3$ comparisons. This idea leads ...
1
This would fall under something called black box optimization. In general, there are several methods you could try in practice such as (stochastic) hill climbing or say a genetic algorithm. Such methods might seem "random", but they take some care in moving in a smart way but also use some "randomness" to escape local optimums.
9
BFS is usually described something like the following (from Wikipedia).
1 procedure BFS(G,start_v):
2 let Q be a queue
3 label start_v as discovered
4 Q.enqueue(start_v)
5 while Q is not empty
6 v = Q.dequeue()
7 if v is the goal:
8 return v
9 for all edges from v to w in G.adjacentEdges(...
2
Let's say you have n = 100, $a_1 = 50$, $a_{100} = 100$, and $a_{50} = 73$. You would then know that the range from $a_1$ to $a_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a_{50}$ to $a_{100}$ contains all numbers from 73 to 100, and maybe some others.
I think binary search will actually work, if the number you are ...
Top 50 recent answers are included
