Questions tagged [algorithms]
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 design and analysis of algorithms.
11,780 questions
2
votes
1
answer
58
views
Flaw in logic to solution to two generals problem
I am failing to find the flaw in logic to a “partial” solution to the two generals problem and would appreciate help seeing where I went wrong (knowing it’s unsolvable)
There are two generals A and B, ...
- 121
0
votes
0
answers
32
views
Which types of outputs are more likely to be produced by simple rule-based programs with fixed rules?
I’m interested in knowing how the complexity of outputs relates to the programs that generate them. For example, in cellular automata like Conway’s Game of Life (a grid-based system where simple rules ...
- 213
-2
votes
1
answer
53
views
Can't understand why my algorithm is not correct [DFS AND BACKTRACKING]
I'm trying to solve the following Leetcode problem: https://leetcode.com/problems/path-sum-ii/description/
This solution I came up with is working: https://pastebin.com/ma3DtU5b
However, I was not ...
- 97
0
votes
1
answer
44
views
Why Pseudo-polynomial time algorithms are required?
One of the problems that has Pseudo-polynomial time algorithm is $0/1$ Knapsack problem.
The $0/1$ Knapsack problem is a follow. Given a set of $n$ elements with weights and prices, and a positive ...
- 163
1
vote
0
answers
28
views
Good algorithm to solve a system of "cyclic" banded linear equations
I would like to solve the equation $Ax=b$ where $A$ is an $N\times N$ "cyclic" banded matrix (there might be a better term, but I wasn't able to find it), i.e. a matrix that look like
$$\...
- 111
2
votes
0
answers
53
views
Find all non-extendable ranges in an array of real values with a non-positive sum
I have a long array of size $n>10^6$, call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions
$\sum_{i=a}^{b-1}X[i] \leq 0$,
$b-a \geq K$,
$\sum_{i=a-1}^{b-1} X[i]...
- 21
1
vote
0
answers
46
views
Is there an efficient algorithm to reduce the degree of a multivariate polynomial given a list of monomial substitutions?
The degree of an $n$-variate polynomial is defined as the maximum degree of the monomials that composes it. Now, given a polynomial $P$ (or rather, a list of monomials, since the coefficients don't ...
- 133
0
votes
1
answer
52
views
Fast algorithm to find factor of a term that is a power
Let's say we have a term (eg an integer, but interested in symbolic polynomial as well) $t$ that can be factored as $t=p^k \cdot m$.
Note: $p$ need not be necessarily prime or otherwise irreducible ...
- 1,038
0
votes
1
answer
44
views
Best strategy with limited ability of memoization
Background
The algorithm to calculate the n-th Fibonacci number using recursion is as follows:
...
1
vote
0
answers
57
views
A Fast Polynomial Multiplication Using only Integers for AKS Algorithm
I'm getting stuck at choosing a fast polynomial multiplication algorithm for the last step of the AKS primality test:
...
- 651
-2
votes
0
answers
27
views
Algorithm Design Binary Tree
I have this request: "Design an algorithm that sums all node values within a tree and compares the result to a target value. If the sum is equal to the target, return 1; otherwise, return 0."...
- 1
1
vote
0
answers
59
views
Find the largest subset of chords in which every pair intersects
I have been trying to solve the following problem from ericksons algorithms:
20)c) Let P be a set of n points evenly distributed on the unit circle, and let S be a set of m
line segments with ...
- 11
5
votes
2
answers
161
views
How is $\overline{SAT}$ not obviously in NP?
First of all, I do know that it is not known whether or not $\overline{SAT}$ is in NP. But to me, it clearly looks like it is in NP. Given a Boolean formula φ with n variables, we nondeterministically ...
- 91
-1
votes
1
answer
42
views
Master Theorem for this equation
$$T(n) = T\big(\frac{ n}{2}\big) + \Theta(1)$$
Hi,
I'm resolving this recurrence relation through Master Theorem.
I would like to know my solution is correct.
$\alpha = 1$
$\beta =2$,
$f(n) = \Theta(...
- 1
0
votes
1
answer
115
views
Runtime analysis of Fibonacci series
To compute the $n$th Fibonacci number, a recursive algorithm is as follows:
...
- 163