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

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
11 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. ...
3
votes
0answers
27 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$ ...
-2
votes
0answers
8 views

Algorithm to count the number of accommodation options 8 knights on a chessboard X - Y [on hold]

yesterday I was asked a question, Algorithm to count the number of accommodation options 8 knights on a chessboard X - Y" And I have no idea how to do this. Thx for help
0
votes
1answer
29 views

Time complexity for inner loop

What's the time complexity for this code? ...
0
votes
0answers
13 views

Eppstein's k-Shortest Paths Algorithm

I was trying to work on a variation of Eppstein's k-Shortest Path Algorithm. Is there an Java-based implementation available for use somewhere, or maybe can someone help me with implementing it? I ...
2
votes
1answer
21 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
19 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 ...
-5
votes
0answers
39 views

I think I invented an algorithm and now I need a website to check if it already exists. [on hold]

without publishing an algorithm, how can I check if it is novel? By that I mean is there any place I could go to find if an arbitrary algorithm, using specialized input syntax for maths, exists? ...
0
votes
0answers
35 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
27 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$, ...
-1
votes
0answers
43 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
10 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
28 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
57 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$ $ = ...
0
votes
0answers
39 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
20 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
2answers
19 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
51 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
62 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
34 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
19 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
19 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
11 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
30 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
19 views

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

Sort the following functions according to their rate of growth - link here
-1
votes
0answers
22 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
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
41 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
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
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
11 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
21 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
21 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
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 ...
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: ...
-1
votes
0answers
12 views

Francis implicit QR algorithm [closed]

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
10 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
18 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
43 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
24 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 ...