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

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
0
votes
1answer
14 views

Time complexity for loop with pow and log n advancement.

So, I'm analyzing this loop. And I'm not sure of the time complexity. ...
7
votes
1answer
103 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
0
votes
1answer
30 views

Time complexity for inner loop

What's the time complexity for this code? ...
1
vote
1answer
14 views

Given a ray and line segment, compute radius of smallest circle satisfying certain criteria

Given a ray and a line segment, (efficiently) compute the radius of the smallest circle satisfying the following criteria: The circle contains the origin of the ray. The center of the circle lies on ...
2
votes
1answer
24 views

What is the algorithm used by Matlab for computing the Bessel function?

I am quite curious about the algorithm behind. It is definitely not the power series expansion, right? So, what is the trick? I cannot find it in the help file of Matlab.
1
vote
0answers
27 views

Any efficient approach to find the minimal vectors?

$\bullet$ A vector $X=(x_1,\cdots, x_m)$ is less then vector $Y=(y_1,\cdots,y_m)$ when $x_i\leq y_i$, for each $i=1,\cdots, m$, and for at least one $j$, we have $x_j<y_j$. $\bullet$ A vector ...
0
votes
0answers
45 views

NP-Complete: Prove this Problem is in NP (specific)

I'm trying to prove that this problem is in NP: Given $n$ dices, there are at least $m$ ways of rolling a given value $y$. Theoretically I need to argue that there is an efficient verifier for ...
1
vote
1answer
28 views

What is the approach to understand this algorithm?

Given $\{x_1, x_2,\ldots x_n\}$ where $x_i \in \{0, 1\}$ there is a binary equation $\varphi$ that is $x_{t_1}+x_{t_2}+\cdots+ x_{t_m}=0 \mod 2$ where $t_i \in \{1,2,\ldots,n\}$ for $x≥1$, ...
-2
votes
0answers
56 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
0
votes
0answers
13 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
0
votes
0answers
37 views

Recurrence for number of ways to write n as the sum

I'm trying to find the recurrence for this problem: ...
0
votes
0answers
19 views

A problem on random q-colourings of a graph for randomly chosen vertex

Here is an exercise from Olle Haggstrom's "Finite Markov Chains and Algorithmic Applications" from the chapter "Fast Convergence of MCMC Algorithms". The exercise is based on random $q$-colorings of ...
0
votes
4answers
62 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
1
vote
1answer
25 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
65 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 ...
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
25 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: ...
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 ...
0
votes
2answers
44 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
22 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 ...
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 ...