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).
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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!
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
3
votes
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 ...
0
votes
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 ...
3
votes
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
...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
-1
votes
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, ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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)...
1
vote
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. ...
2
votes
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.
<...
0
votes
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 ...
1
vote
0answers
26 views
Algorithm expressing a fraction as a sum of unit fractions
I am looking for an algorithm to express some fraction $\frac{a}{b}$, with $a,b \in \mathbb{Z}$, as a sum of unit fractions, like:
$$\frac{a}{b} = \frac{1}{w_1} \pm \frac{1}{w_2} \pm \frac{1}{w_3} \...
-3
votes
1answer
38 views
Find all rational solutions of 1) $3x^2 +8x^2 -15x+4=0$ question 2)$x^4 -6x^3+22x-30x+13=0$ [closed]
Finding all rational solutions of $3x^2 +8x^2 -15x+4=0$ and $x^4 -6x^3+22x-30x+13=0$
0
votes
2answers
19 views
Time complexity for an algorithm
How do you realize that
$$(3log^2(n) + 55log(n^{10})+8log(n))*log(n) \neq \Omega(log^{10}(n))$$
,where $log^x(n)$ means $(log(n))^x$
I know that by definition, if $f(n) = \Omega(g(n))$ ...
1
vote
1answer
33 views
are $\sum_{i=0}^{n}i$ and $\sum_{i=n}^{0}i$ equivalent?
So here's the ugly history of how I came to ask this question. I was following this proof:
and got stuck at this step:
$$\sum_{j=0}^{(\log_2n) - 1}\frac{1}{(\log_2n) - j} = \sum_{l = 1}^{\log_2n}\...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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. ...
0
votes
0answers
15 views
Discret optimization problem
the problem setting is as follows: We are given a set of words (for simplicity we can assume all of the same length, i.e. n-tuples) $W = \{ w_1, w_2, ..., w_N \}$ where $w_i = (a_{i1}, a_{i2}, ... a_{...
0
votes
0answers
19 views
Can a network flow have a vertex with no s-t path? [on hold]
I was wondering if the second picture was a valid example of a network flow? I don't think it is since I haven't actually seen an example of such a graph but I could be wrong?
0
votes
0answers
11 views
Domination problem is NPC
I call the problem as DOM. Given a graph $G$ and an integer $d$, Decision problem DOM - "Does there exists a dominating set of size less than or equal to 'd' in G? " DOM is NP Complete problem.
But, ...
2
votes
3answers
809 views
How come the time complexity of Binary Search is log n
I am watching this professor's video on Binary Search but when he reached here, I am a bit lost. How come he came up the time coomplexity is log in just by breaking off binary tree and knowing height ...
0
votes
0answers
3 views
How to show time complexity comparation of Fleury's and Hierholzer's algorithm?
I know that time complexity of Fleury's algorithm equals to $O(e^2)$ and Hierholzer's equals to $O(e)$. I need to show that Fleury's algorithm is less efficient on some example or by giving a proof of ...
1
vote
0answers
27 views
The number of colours in greedy colouring is $\leq \frac{1}{2} + \sqrt{2E(G)+\frac{1}{4}} $
I am stuck with the following exercise:
Let $\sigma$ be an ordering of the vertices of a given graph $G$ and let $\chi(G,\sigma)$ be the number of colours the greedy colouring algorithm uses. Show ...
0
votes
0answers
19 views
Gaussian Elimination Roundoff Error Confusion
I have a couple questions about Gaussian Elimination
Regular Gaussian Elimination (No pivoting, No making pivots 1, No Row Swapping)
Gaussian Elimination with pivoting (Which just means row ...
1
vote
2answers
52 views
Easy ways of finding small prime divisors
Are there any "relatively simple" ways of seeing whether a number is divisible by a small prime not 3. For example, one simply sums the digits of n modulo 3 and if they sum to zero, then n is ...
1
vote
0answers
8 views
Looking for ways to transform time-series data recorded from object movement into equation describing the movement direction of the object
Looking for some time-series data transformation advice!
I want to know what's the best way to transform data of 9-tuples time series data of IMU (Inertia Measurement Unit) sensor, recorded from a ...
0
votes
0answers
38 views
Recurrence relationship for crawling a directory
I am trying to write a recurrence relationship for problems that can be solved using recurrence.
As an example recurrent for finding the 3^4 (which is 3*3*3*3) can be written as:
...
0
votes
0answers
14 views
Simplify a triple cycle
I'm writing an algorithm which computes the solution for a pretty complex (for me) problem which I found online. I couldn't find a smart solution, so I decided to use the brute force.
BUT
as ...
0
votes
0answers
11 views
How do they find positive neighborhood of set Frontier in BFS?
I'm trying to understand the Breadth First Search complexity (work and span).
For the case in the picture, I don't understand how line 9 works, and from that to calculate the Work & Span.
Full BFS ...
0
votes
1answer
30 views
Game theory problem - two towers
I'm asking that question because I still cannot figure out the solution after hours of thinking.
You are given two towers where first has exactly n stones and second has exactly m stones. You are ...
0
votes
1answer
28 views
Algorithm for Integration of a Rational Function
Let $p(x)/q(x)$ be a real-valued rational function in $\mathbb{R}(x)$. I am wondering what the complete story is for integration of these functions. I would expect some algorithm to work like this:
1)...
