Questions tagged [algorithm]
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
algorithm
23,842
questions with no upvoted or accepted answers
15
votes
1
answer
2k
views
Computing a move score in a Minimax Tree of a certain depth
I've implemented a Chess game in C, with the following structs:
move - which represents a move from (a,b) to (c,d) on a char board[8][8] (Chess board)
moves - which is a linked list of moves with ...
12
votes
1
answer
435
views
Algorithm itemset matching pattern
I've a set of elements (potentially big) with an order relation:
[a,b,c,d,e,f]
and a set of frequent patterns (potentially big) with ids:
[a]:1,[b]:2,[c]:3,[a,b]:4,[b,c]:5,[a,b,c]:6
I have a ...
12
votes
5
answers
3k
views
Check if there exist a path between two vertices in directed acyclic graph - queries
This question can be easily solved in O(n + m) per query, however is this possible to answer such queries in better complexity with preprocessing better than O(n²) ?
In tree it can be easily done by ...
12
votes
1
answer
9k
views
Abstract syntax tree using the shunting yard algorithm
I have an infix expression that I have tokenised and would like to proceed to create an abstract syntax tree. I understand the shunting-yard algorithm used in these cases. I have only found ways to ...
11
votes
0
answers
292
views
Is the libc++ implementation of the STL deque push_front function standards-compliant?
The C++ Standard (N4901) says this with reference to the deque push_front function:
An implementation shall provide these operations for all container types shown in the “container” column, and shall ...
11
votes
0
answers
2k
views
GUI layout algorithms overview
I'm looking for systematic review of the algorithms used for GUI layout. I'm particularly interested in the algorithms that favor speed over complexity, but it's hard to find anything useful other ...
11
votes
1
answer
5k
views
DIvisive ANAlysis (DIANA) Hierarchical Clustering
(This post is continuation of my previous question on divisive hierarchical clustering algorithm.)
The problem is how to implement this algorithm in Python (or any other language).
Algorithm ...
11
votes
1
answer
428
views
Average case algorithm analysis using Kolmogorov Incompressibility Method
The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations ...
11
votes
2
answers
965
views
How are fluid simulations integrated into Rigid Body physics engines?
Is there any proof that simulations that mix Rigid Body physics and fluids (say SPH) can provide modeling for real world?
How does a frame of such mix work?
Say we have a wooden swing inside a box ...
11
votes
1
answer
1k
views
My implementation of the evaluation function and Alpha-beta pruning for Connect Four is not smart enough
I am trying to implement correctly the Connect Four game AI yet not to avail my AI acts stupid:
It does not block the opposite player pattern which can lead to failure of the AI,
It does not take ...
10
votes
0
answers
355
views
Why does C++11 require std::sort to have WCET O(n log n)?
Since C++11, the C++ Standard Library (c.f. Section 25.4.1.1 of a draft verion of the standard) requires the std::sort algorithm to have asymptotic worst case execution time O(n log n) instead of ...
10
votes
3
answers
1k
views
Minimum add to make parentheses string consisting of '{', '}', '[', ']', '(', ')' valid
This problem is an addition to the familiar stack question(https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/) where we have to return the minimum number of additions to make the ...
10
votes
0
answers
2k
views
Can I guess the appropriate epsilon for RDP (Ramer-Douglas-Peucker)?
I have sets of time series data which I display as charts in mobile applications.
To make the charts clearer, I simplify the sets by applying Ramer-Douglas-Peucker.
If I apply RDP to a small set ...
10
votes
2
answers
155
views
Strategy for translating a UX `pan` gesture to set a linear value without an upper bound
I'm trying to set a slider (actually a kitchen timer) using a pan gesture in ionic2 see: http://ionicframework.com/docs/v2/components/#gestures
The slider/timer has an open upper-bound that could be ...
10
votes
3
answers
12k
views
Parenthesizing a string so that expression takes a given value
The following problem is from the chapter on Dynamic Programming by Vazirani et. al.
[6.6]Let us define a multiplication operation(×) on three symbols a; b; c according to the following table:
...