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

Differentiating unimodal and bimodal normal distributions

I have a large number of data sets that have either a unimodal normal distribution or a bimodal normal distribution. I'm not a statistician by any means, so I'm quite limited in my experience. For ...
1
vote
0answers
432 views

Levenberg-Marquardt training

I am trying to do simplified version of Levenberg-Marquardt alg. for NN with one hidden layer. I found this article: Efficient algorithm for training neural networks with one hidden layer I am not ...
1
vote
0answers
4 views

Fast square of a row-stochastic matrix

I would like to implement the square $M^2$ of a row-stochastic matrix $M$. Running time is critical. Are there any known algorithms that exploit the special nature of $M$ and are faster than the usual ...
0
votes
0answers
11 views

Can the time complexity of maximum-flow algorithm using fattest path method be represented by |V| and |E| only?

I've got a problem with "fattest path" heuristic in Max-Flow algorithms. ( http://www.eecs.berkeley.edu/~luca/cs261/lecture10.pdf ) The problem is 'prove or disprove that the time complexity can be ...
0
votes
0answers
24 views

Determining a good genome for a genetic algorithm to alter neural network characteristics?

I am developing an application to run a genetic algorithm over the input characteristics of a neural network. I am currently looking for help finding a good "genome" to use along with good example ...
0
votes
1answer
39 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 ...
-5
votes
0answers
14 views

$T(n)=2T(\frac{n}{2})+5n^3$, $T(1)=1$ where $n=2^k$ [on hold]

Solving recurrences relations. result should be in clear form of $n$
1
vote
1answer
1k views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
0answers
17 views

Understanding McAfee's Double Auction algorithm

I'm making a java program that implements the double auction mechanism described in this paper: http://vita.mcafee.cc/PDF/DoubleAuction.pdf I took some screenshots of the text in order to save time. ...
0
votes
0answers
14 views

Looking for conditions on generator sets of the form $\{a,b \}$ and $\{a,b,c\}$ on the group $\mathbb{Z}_2^3 \rtimes S_3$

Let $G$ be the group $\mathbb{Z}_2^3 \rtimes S_3$ with the natural action of $S_3$ on the coordinates of $\mathbb{Z}_2^3$. I want to know if there are subsets of $G$ of two elements or also 3 elements ...
0
votes
0answers
13 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
0answers
24 views

Derivation of backward probabilities $\beta_i(s_i)$ of a Hidden Markov Model (message passing). Any help in completing it?

I am trying to formulate in a recursive manner the backwards probabilities $\beta$ of a Hidden Markov Model where $w_i$ are the observed symbols and $s_i$ are the latent states. Is the following ...
0
votes
0answers
5 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
13 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
52 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
0answers
15 views

Eppstein's k-Shortest Paths Algorithm [on hold]

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

Time complexity for inner loop

What's the time complexity for this code? ...
0
votes
1answer
35 views

Algorithm for the independent domination number

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
4
votes
2answers
766 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
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.
0
votes
4answers
61 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
0answers
22 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 ...
-2
votes
0answers
49 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: ...
-5
votes
0answers
43 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
43 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$, ...
0
votes
0answers
34 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
11 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
22 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 ...
8
votes
3answers
10k views

Fastest prime generating algorithm

What is the fastest known algorithm that generates all distinct prime numbers less than n? Is it faster than Sieve of Atkin?
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? ...
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
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 ...
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?
2
votes
1answer
409 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
0
votes
2answers
22 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 ...
3
votes
2answers
63 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. ...
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 ...
-1
votes
0answers
37 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
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 ...
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
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
42 views
-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.
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
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 ...