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).

learn more… | top users | synonyms (1)

0
votes
0answers
4 views

Partitioning the set of mappings.

The following is first two steps of an algorithm given from a research paper. I understood the first step. But please explain the second step: what does mean " Rearrange the partition according to ...
15
votes
3answers
6k views

Finding the intersection point of many lines in 3D (point closest to all lines)

I have many lines (let's say 4) which are supposed to be intersected. (Please consider lines are represented as a pair of points). I want to find the point in space which minimizes the sum of the ...
1
vote
0answers
8 views

Primitive polynomials from GF(q) to GF(q^n)

Suppose that over some finite field $GF(q)$, we have two monic primitive polynomials of orders $n$ and $mn$. -From these polynomials, is there always a 'natural' monic primitive polynomial over ...
0
votes
1answer
23 views

Decompose sum into reversible pairs

Is there any efficient way to find if a sum can be decomposed into reversible pairs?And if it does can we find these numbers? For example 66 can be decomposed into 24+42 or 66666=12345+54321. One ...
0
votes
0answers
7 views

Algorithm for ordering on an algebraic number field

Given an algebraic field extension of the rationals $Q(P(X))$, where $P(X)$ is a polynomial in $X$, how do I algorithmically define an ordering on $Q(P(X))$ that is compatible with a specific real ...
0
votes
1answer
31 views
-2
votes
0answers
20 views

For $\Theta$ notation which statements are true? [on hold]

Assume an algorithm runs in $\Theta(n^2)$, then which one of the following asymptotic notation for it? $O(n^3)$ $O(n^2)$ $\Omega(n^2)$ All above are correct.
-1
votes
0answers
18 views

Sort the following functions according to order of growth [on hold]

Sort the following functions according to their rate of growth - link here
0
votes
0answers
23 views

If an Algorithm's algorithm's running time can be expressed as function F(x)=√n+(logn)^2 ,

If an Algorithm's algorithm's running time can be expressed as function $F(x)=\sqrt n +(\log{n})^2$ , then which one of the following is not a correct bound for the running time ? $O(n)$ $O(\sqrt ...
0
votes
0answers
12 views

Spigot algorithms for transcendental numbers

I'm trying to write a program that will compute digits of transcendental numbers using a spigot algorithm. While researching, I found the BBP Formula, and a Compendium of BBP-Type Formulas, alas, I ...
0
votes
1answer
42 views

Algorithms - Finding Clique of size n in a Graph

I have the following statements (NOTE: $\bar x$ means the complement of $x$): $(x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4)$ I need to do the ...
1
vote
0answers
17 views

Is there an algorithm to find minimum cut in undirected graph separating source and sink

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components. I ...
2
votes
0answers
78 views

Computationally efficient means of determining distance in the Skorohod Topology?

I have two functions f and g in a computer. Domain 1...N. I'd like to compute their distance using the Skorohod Topology in an efficient manner. (I first ran across this metric many years ago in ...
0
votes
2answers
55 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - ...
0
votes
0answers
17 views

Nonlinear equations algorithm - Newton method

Some time ago I posted a question regarding the simple case of finding the intersection point when I have only two functions, and with your help I found an answer. It was this case: $f(x) = a + ...
1
vote
0answers
8 views

Finding the roots with the largest magnitude

Given a non-constant polynomial $p\in\mathbb{Z}[x]=\alpha\prod_{k=1}^nx-\alpha_k$ how can I find the roots $R=\{\beta_1,\ldots,\beta_t\}\subseteq\{\alpha_1,\ldots,\alpha_n\}\subseteq\mathbb{C}$ with ...
2
votes
1answer
616 views

Truth table reduction

I'm learning algorithm theory and the teacher asked a question that confuses me. Do $A$ and $B$ exist such that $A$ is not truth-table reducible to $B$, but $B$ is truth-table reducible to $A$?
0
votes
0answers
7 views

Algorithmic complexity from knowing complexity due to two different factors.

I have an algorithm that has complexity depending on two factors $n$ and $m$. If I know that fixing $m$ I have complexity $\mathcal{O}(n^p)$ and fixing $n$ I have complexity $\mathcal{O}(m^q)$, can I ...
0
votes
0answers
9 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
0
votes
1answer
23 views

An algorithm to find a subgroup generated by a subset of a finite group

I'm currently writing a library on python, and now I'm a little bit stuck on how to find a subgroup generated by a subset $S$ of the group $G$. In the case $S = \{a\}\subseteq G$ the problem's easy: ...
2
votes
0answers
19 views

Shortest paths on uncountable infinite graph

Lets consider the weighted directed graph $G=(V,E,w)$ where the vertices are $V=[0,1]\subset \mathbb R$ (alternatively $V=(0,1]$ or $(0,1)$), $E = V\times V$ and the weights are given by a function $w ...
0
votes
1answer
21 views

Pollard's $p-1$ method

I've been reading some notes regarding the Pollard's $p-1$ method1 and I came across an aglorithm that (from the math standpoint) I don't fully understand: Given that $\textbf{a = 2}$ and also in my ...
0
votes
1answer
28 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching maxima cardinallity. A tree is an acyclic connected graph. Is there an efficient algorithm ...
0
votes
0answers
23 views

Runtime of Algorithms (Recurrence&Induction)

Two algorithms are given: $$T_A(n) = (\log_4(n) + 1) \cdot n\quad\text{and}\quad T_B(n) = 4 T_B\left(\frac{n}{4}\right) + n^\alpha$$ $$T_B(1) = 1; \alpha \in \mathbb R_+; n = ...
1
vote
1answer
45 views

What math do I need to know for MD5?

This could fit into a lot of areas of SO but I feel like mathematics will know best. What area of math is used for something like an MD5 or SHA algorithm? Is there a mathematical equation/skeleton ...
1
vote
1answer
41 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
-1
votes
0answers
11 views

Francis implicit QR algorithm [on hold]

I want to implement the Francis implicit QR algorithm in C to calculate the eigenvalues and eigenvectors. I'm using "Fundamentals of Matrix Computations" by David Watkins to help me with the ...
0
votes
0answers
9 views

Getting a covariance matrix from angles

I'm reading a book (Introduction to Evolutionary Computing) which suggests1 the following algorithm for generating an arbitrary covariance matrix: Choose $\sigma_i^2>0$. They will go into the ...
2
votes
1answer
81 views

How to find all systems of distinct representatives using i.e. Hopcroft–Karp algorithm?

I would like to find all systems of distinct representatives in bipartite graph. I've found Hopcroft–Karp algorithm, which finds maximal matching, which I would like to implement. But I don't know how ...
2
votes
1answer
38 views
+100

Detecting singular system during Cholesky resolution

I am solving small linear systems with a symmetric positive matrix by the method of Cholesky, without pivoting. "Bad" matrices are detected when you take the square root of a diagonal element, which ...
1
vote
1answer
443 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
8
votes
1answer
66 views
+50

Most efficient method for computing Singular Value Decomposition of a triangular matrix?

There are several methods available for computing SVD of a general matrix. I am interested in knowing about the best approach which could be used for computing SVD of an upper triangular matrix. ...
1
vote
3answers
276 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
6
votes
0answers
28 views
+50

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
0
votes
0answers
20 views

Algorithms for Taylor Expansions

Is anything known about fast algorithms for taking symbolic Taylor expansions? I have a homegrown algorithm, but it seems to be exponential in the number of terms requested when operations like the ...
0
votes
0answers
15 views

Least amount of intervals covering array of numbers

Lets have Array of numbers eg. $A=[29, 1, 26, 4, 28, 35, 17, 42, 51]$. I want to find least number of intervals of maximal length $10$, which covers all numbers. eg. intervals $= (1,10), (17,26), ...
0
votes
1answer
17 views

Time complexity for loops

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. int j = 1; int n = any; ...
-1
votes
0answers
10 views

Rank one correction algorithm

Are the direction d1,d2,...,dn necessarily conjugate? enter image description here
1
vote
0answers
42 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than $2$ I should choose a special partitioning hyperplane for the divide and conquer algorithm to get $O(n \log n)$. I am confused because to choose this ...
1
vote
0answers
53 views

partitions of finite set in same-size parts having at most one element in common

Given $g \ge 2$, $k \ge 1$ and a population of $p = kg$ workers, I'm trying to figure out the longest series of work shifts such that: during each shift, all workers work in $k$ teams of g people; ...
0
votes
0answers
27 views

mathematical formula to compute sum of all sub sequences of a number N

We have a number say N and we list down all its sub- sequences and sum them up.SAY for n=123 ,the sum is 177(123+12+23+13+1+2+3). I came across this mathematical formula which computes the sum taking ...
0
votes
2answers
20 views

Difference between Depth first search and Breadth first search algorithm

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a ...
0
votes
1answer
20 views

To decrypt this version of Turing's code, does the decrypter actually need the secret key?

I am self studying MIT's Mathematics for Computer Scientists (link) There is a chapter in the readings on Number Theory, and it goes through the math involved in the cryptography methods used around ...
1
vote
0answers
12 views

Minimum sum in an array with constraint

I am a newbie to the dynamic programming paradigm.. while trying to solve this question....... How to find minimum sum of the numbers in an given array such that at least one of three ...
-1
votes
0answers
11 views

Is f(n1 x n2) = Θg( n1 x n2 ) true?(Discrete mathematics, Algorithm)

I have a question about Theta Notation. For X={1,2,3 .....} n1 and n2 are elements of X If f(n1) = Θg(n1) and f(n2) =Θg(n2), then is f(n1 x n2) = Θg(n1 x n2 ) true? My speculation is that for n1 x n2 ...
7
votes
0answers
139 views
+50

Dynamically two-coloring a finite graph

Let $G=(V,E)$ be a finite graph whose vertices are going to be colored dynamically. More precisely, consider time periods $t \in \left\{0,1,2\ldots,\right\}$ and for each time $t$ and $i \in V$, let ...
5
votes
1answer
92 views

Complexity of Gaussian Process algorithms is $\mathcal{O}(n^3)$

It is often quoted that the complexity of Gaussian Process algorithms is $\mathcal{O}(n^3)$ due to the need to invert an $n \times n$ matrix, where $n$ is the number of data points. But as far as I ...
0
votes
0answers
17 views

Balancing integer bins to have a certain summation

Assume that we have bins $$ B_1, B_2 ..., B_n $$ There exists integer bin values $$ V_1, V_2 ..., V_n $$ Let $$ Total_{V} =\sum_{i=1}^{n} V_i$$ There then exists weights ( $ W $) of each bin to ...
1
vote
1answer
39 views

Representing a number as $a^2+db^2$ given $d$

Given integers $n$ and $d$, how can I find integers $a$ and $b$ (or show that they do not exist) such that $n=a^2+db^2$? If it helps, in my present application I know the factorizations of $n$ and ...
0
votes
0answers
6 views

Algorithm to determine popularity through sentiment, volume, time, and feedback

I am quite new to this space of ranking algorithms, and I'm faced with a problem. I have the following factors that will determine an entity's "popularity" ranking: Number of occurrences mentioned ...