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
1answer
41 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
20 views

Sort the following functions according to order of growth [closed]

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

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

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
vote
0answers
25 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
13 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
44 views

Find the matrix X such as A . X is close to B

Consider : A an m by n matrix B an ...
0
votes
0answers
19 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
9 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 ...
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
12 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 ...
2
votes
0answers
22 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
29 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
1answer
22 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 ...
1
vote
0answers
25 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 ...
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
46 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 ...
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: ...
0
votes
0answers
11 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 ...
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
19 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; ...
0
votes
1answer
45 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
votes
0answers
10 views

Rank one correction algorithm

Are the direction d1,d2,...,dn necessarily conjugate? enter image description here
0
votes
2answers
25 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
0answers
30 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 ...
1
vote
0answers
13 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 ...
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
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 ...
3
votes
1answer
55 views

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 ...
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
7 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 ...
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
34 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
0
votes
0answers
14 views

Algorithm to find highest path in a DAG

Let it be $G=(V,E)$, a directed acyclic graph. We will define function $h:V\rightarrow R^+$, when h(v) is the height of v. Let it be path $P=(v_1,...,v_k)$. We will also define the height of a path ...
-1
votes
0answers
4 views

Minimizing the distance between two set of vectors such that the angle of both set is equal

Suppose I have two set of vectors K1,I1 and K2,I2 forming a surface S1 and S2 respectively in R2 or R3. The angle between K1 and I1 is T1 and K2 and I2 is T2 respectively. The goal is to minimize the ...
0
votes
0answers
10 views

BFS and bipartites graphs

I have the lemma Lemma. Let G be a connected graph, and let $L_0$, …, $L_k$ be the layers produced by BFS starting at node s. Exactly one of the following holds: (i) No edge of G joins two ...
0
votes
0answers
12 views

Maximizing a Special Node-weight sum on a Directed Acyclic Graph

Given a Directed Acyclic Graph (DAG) $G=(V,E)$, also satisfying that if $(u,v),(v,w)\in E \implies (u,w)\in E$. For $S\subseteq V$, define the following set $\Gamma(S)=\left\{u \in S, \not\exists ...
0
votes
1answer
33 views

Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
1
vote
1answer
23 views

What is the name of this kind of factoring algorithm

I just think about algorithm to find factor of number by doing something like guessing last digit of number and increase digit bit by bit Such as, I want to find factor of 749 Algorithm would begin ...
-2
votes
0answers
18 views

Can I find number of “even” subarrays in less than $O(n^2)$?

You have an array called $A$ of length $n$ (indexed from $0$), filled with numbers from interval $[1,n]$, not necessarily different. You need to know how many subarrays this array has in which every ...
0
votes
1answer
30 views

Is my exam board correct in saying that a variable is a condition? [closed]

A question given in an exam goes as follows: A student is tracing the following algorithm- Start Input N Let A=1, B=1, C=0 Let C = C+A Let D = A +B Print A Let N = N-1 If N ...
1
vote
0answers
20 views

Catalan Number Modulo Prime

What is the fastest method to find the $n$th Catalan number modulo some prime $p$? I was looking at Lucas's method to solve $\binom{2n}{n}$ fast, but not sure if it will work. What is the fastest way ...
0
votes
1answer
13 views

Modular Exponentiation doesn't work on a prime mod?

For 83627264^275372 mod 277 using modular exponentiation, I noticed that things weren't lining up when I checked them on Wolfram. So far I have this: 83627264^1 mod 277 = 133 83627264^2 mod 277 = 238 ...
1
vote
3answers
59 views

Integer solutions to $xyz = w^2(x+y+z)$

I'm looking for a way to enumerate all positive integer solutions of the equation $xyz = w^2(x+y+z)$ where $w \le W$ and $1 \le x \le y \le z$. Could anyone provide a hint at how to approach this? ...
12
votes
0answers
179 views

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 ...
6
votes
0answers
57 views

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
11 views

Is the Antikythera Mechanism Turing-Complete?

Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ...
0
votes
0answers
15 views

Rosenbrock function matlab

I am new to MATLAB and I am asked to implement on matlab the following algorithm: for an unconstrained minimisation problem. I am asked to apply the BFGS method with armijo line search ...
-1
votes
2answers
37 views

Algorithms on arrays [closed]

You have an array called $A$ of length $n$ (indexed from $0$), filled with numbers from interval $[1,n]$, not necessarily different. You need to know how many subarrays this array has in which every ...