# Questions tagged [algorithms]

Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

8,350 questions
1answer
18 views

### Complexity of solving a linear equation system over $k[x]$

Let $k$ be a field and let $A \in k[x]^{m \times n}$ be a polynomial matrix whose entry with highest degree has degree $d$. Let $b \in k[x]^m$. What is known about the complexity of computing a ...
0answers
12 views

### Dinic's algorithm

Given $N = (G = (V , E),s, t, c)$ a flow network, we run the Dinic's algorithm (https://en.wikipedia.org/wiki/Dinic%27s_algorithm) on this Network. Consider some iteration $i$ which is not the last ...
0answers
22 views

### Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
0answers
37 views

### algorithms - When not to assume $n$ is a power of 2, while solving recurrences?

In Udi Manber - Introduction to Algorithms. A Creative Approach, exercise 3.29, p.59 Although in general it is sufficient to evaluate recurrence relations only for powers of 2, that is not always ...
2answers
38 views

### Recurrence - Master theorem [on hold]

I need to solve $T(n) = 4T(\frac{n}{3}) + n\log(n)$ To apply the master theorem to the function, I need to find $a$, $b$ and $d$. Then $a$ is $4$, $b$ is $3$ but what is $d$? I have never encountered ...
0answers
55 views

### Efficient method to check whether the nearest prime has distance $d$ or more?

Suppose, a prime $\ p\$ is given. How can I check efficiently whether the distance to the nearest prime is $\ d\$ or more , if $\ d\$ is given ? My approach is to start with $\ c=2\$ and as ...
0answers
14 views

### Tough test polynomials for (finite precision) complex root finding methods, especially Aberth's method

Today I have implemented Aberth's method for complex polynomial root finding. And I have to say I am enchanted about its astonishing performance and its intriguing simplicity. Before I go on believing ...
2answers
35 views

### Solving recurrences with Master theorem

Normally, the way I am solving those problems is the following: $3T(\frac{n}{2})+ n^4$ $a=3 ; b = 2 ; d=4$ then I am doing $\log(b(a))$ which is $log(2(3))= 0.6$ Since $0.6 < d$ I can apply the ...
0answers
16 views

### asymptotic growth of functions

I ordered a list of function based on asymptotic growth but I am not 100% not. Faster to slower: n^0.001 (√n ln n) 2^(ln^2n) 2^(2^ln n) (ln ln n^2) (ln n)! n!
0answers
17 views

### Path between nodes in a colored oriented tree with given weight sum

Consider an oriented tree where each node is colored either black, white, or both. In addition, each (oriented) edge has a given weight. I am trying to see whether there exists a pair $(u, v)$ of ...
1answer
20 views

### A standard way to reduce a k-SAT to 0-1 Integer Linear Programming

I was searching for a standard (a published paper) for which it reduces a k-SAT to a 0-1 ILP (Integer Linear Programming), but couldn't find any :( I know how to reduce a SAT problem to an ILP ...
0answers
18 views

### Derive a bound for a tree with node having k left branches

We are given a binary tree of maximum level n and where each node can have a maximum $k$ left branches. $n$ is always greater than or equal to $k$. I want to know a bound on the number of nodes in ...
0answers
34 views

### Choosing vectors for projection

I have a vector $v = a_1\mu_1 + a_2\mu_2 + ... + a_n\mu_n$ where $\mu_i$ are given linearly independent but not orthogonal vectors. I need to choose $k$ vectors from the original set such that when ...
0answers
13 views

### Finding optimum time for change of equipment based on shift pattern available resources

I am trying to sort out a relatively simple problem, where I believe an algorithm or solving technique may already exist (Hungarian Algorithm?). I'd like to solve it using an methodology rather than ...
0answers
55 views

### Consider a binary operation $\circ:\{1,2,\ldots,n\}\times\{1,2,\ldots, n\} \rightarrow \{1,2,\ldots, n\}$.

Consider a binary operation $\circ:\{1,2,\ldots,n\}\times\{1,2,\ldots, n\} \rightarrow \{1,2,\ldots, n\}$. Сall the degree of associativity of this operation the number of triples $i, j, k$ such ,that ...
0answers
50 views

### Test if a function is continuous or has at least one discontinuous vertical asymptote between an interval

Imagine evaluating a function with little intervals incrementally across a graph and testing by using the end points of the each interval (and maybe a midpoint), whether the function is continuous for ...
0answers
27 views

### Find polygon that traverses all given points with minimal circumference but has a single surface

I know about Convex Hull, but convex hull is convex, which isn't what I want. I want a polygon that will always try to minimize it's perimeter however will not have multiple surfaces: For example, I ...
1answer
31 views

### How can I properly force this “object” to follow the indicated path

I'm working with drones and I want them to follow a path. This is the current behavior (black is the path, red is the drone): As you can see, it goes to the destination point (C), but it doesn't ...
2answers
52 views

### (n & (n -1)) == 0 [on hold]

I am going through this interview study book for algorithms and it states that: " So, we have our answer: ( (n & (n -1)) == 0) checks if n is a power of 2 (or if n is 0). " How is this possible, ...
0answers
22 views

### Minimal one-step distance set of vertices to all vertices

I want to find minimal set of vertices such that every vertex in this graph either in this set or connected with some vertex from this set with one edge. Is there standard name for this algorithm? It ...
1answer
24 views

### Cut In a Flow Network

Given $N = (G = (V , E),s, t, c)$ a flow network (assume that the capacity $c$ is always positive) and $e = (u,v) \in E$. I would like to develop an algorithm that tell if there exist a min-cut (cut ...
1answer
9 views

### Algorithm Problem for arrival and departure time of a dataset

Algorith for arrival and departure time I have got a piece of algorithms which consists of several equations to determine the arrival and departure times of a water vessel to a dock from AIS data. I ...
0answers
30 views

### Finding small solutions to modular congruences

I was wondering what computational/algorithmic techniques can be used to solve a modular congruence when we are looking for a pair of small values. The specific problem is like this (the numbers are ...
1answer
32 views

### time the pseudo random generator gonna start repeating itself

as you know the general formula for pseudo random generator is this U(n)=a*U(n−1)+b [mod z] where we have control of U(n-1)...
0answers
17 views

### Which uniformed search algorithm is the best here?

So I have an exercise like this where I have to choose the best strategy. I wonder here which one is the best: A robotic engineer wants to add movement planning ability to a small mobile robot. ...
2answers
43 views

### Biased binary search complexity

We know Binary search on a set of n element array performs O(log(n)). We have this recursive equation through which the search space is reduced by half in each iteration, after a single comparison. <...
0answers
16 views

### Compute the shortest path in a directed acyclic graph

Problem: Let $D = (V,A)$ be a directed acyclic graph, i.e., there exists no directed cycle in D, and let $w : A → R$ be arc weights. Assume that you are given a topological sort of the vertices. Show ...
0answers
26 views

0answers
26 views

### LLL for quadratic forms

It is quite easy to use the LLL algorithm to find approximate solutions to linear/multilinear forms, and I am able to do that. However, I am trying to understand how the LLL algorithm is used to ...
0answers
9 views

### Measure effectiveness of algorithm (plot included for clarification)

I have written a short algorithm that computes the "comovement" of a time series. My problem is what method to use to measure how accurate this algorithm is. Ideally it should only have negative lines ...
1answer
17 views

### Calculate generators of an intersection of Ideals

$$I = (x_1^2-x_1,x_2^2-x_2,...,x_n^2-x_n,t-\sum_{i=1}^n 2^{i-1}*x_i)$$ Ideal in $\mathbb Q[x_1, ..., x_n,t]$. How can I calculate the generators of $J = I \cap \mathbb Q[t]$ by hand? I tried it with ...
0answers
15 views

### Reducing knapsack problem to a inversed knapsack problem

1)Suppose we have a common 0-1 knapsack problem. Given a set of n items numbered from 1 up to n, each with a weight w_i and a value v_i, along with a maximum weight capacity W. Here we need to select ...
0answers
15 views

### How many swaps in a set of size n will ensure that the set is shuffled reasonably well?

I'm implementing my own version of a shuffle method for shuffling a set of objects in a list. My implementation generates two (pseudo)random numbers and swaps the elements at these two indexes. ...
0answers
15 views