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)

1
vote
1answer
23 views

Graph Theory - Minimization by degree problem

I'm a 3rd year Math undergrad and I decided to take an algorithms extra class. This question was a bonus one on my mid-term and I still have no idea on how to approach it. Given $n$ vertices, each ...
0
votes
0answers
40 views

Equality of two functions.

I have a specific question, from a paper given below. Here I got an answer of question: When two functions are called equivalent?.It helped me to understand the first and the second steps of the ...
0
votes
0answers
26 views

Ranking system algorithm help

I’m currently in need of help for developing an algorithm for a dynamic ranking system. I’m working on developing a children’s site where it will feature Ranking Chart on the website. Here is the ...
0
votes
0answers
14 views

Help with Hidden Markov model and SMC methods

So its quite a long background i don't really know where to start but here goes. The background is as follows: Background Observation model As the target is moving, it measures the signal (RSSI) ...
0
votes
2answers
32 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
1answer
56 views

How many more edges can be added to a graph while keeping it acyclic?

If I have a connected, directed graph with $n$ vertices and $m$ edges, is there some sort of formula that describes how many more edges can be added to the graph while keeping it acyclic?
3
votes
2answers
64 views

Efficiently solving many sets of linear equations without inversion or factorization

Suppose I have the normal set of linear equations $Ax = b$. If I can store and manipulate $A$ I have a variety of techniques available to me such as inversion, factorization, or an iterative method. ...
-1
votes
0answers
39 views

Faster method to find sum (product) parts

I have a sum (product) that includes some specific values and I need to find how many values make that product. For example: I have $481$ and values$: 5, 29, 149$. I can find that $481 = 5 + 29 + ...
0
votes
0answers
20 views

Are there any algorithm for schedule match

I am making a game. This game divide players into groups. Each group has N players in even number and will schedule player in the same group to fight each other in pair everyday I need to have every ...
0
votes
0answers
21 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 ...
1
vote
0answers
14 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
0answers
12 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
46 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 ...
1
vote
0answers
27 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
16 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
47 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
20 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
23 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
30 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
23 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
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
51 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
24 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: ...
-1
votes
0answers
15 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
17 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
49 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
11 views

Rank one correction algorithm

Are the direction d1,d2,...,dn necessarily conjugate? enter image description here
0
votes
2answers
40 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
14 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
21 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
12 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
56 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
18 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
8 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
39 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
17 views

Algorithm to Find Highest Path in a Directed Acyclic Graph

Let $G=(V,E)$ be a directed acyclic graph. We will define the function $h:V\rightarrow R^+$, where h(v) is the height of v. Let $P=(v_1,...,v_k)$ be a path. We will also define ...
-1
votes
0answers
6 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
13 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
24 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 ...
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 ...