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

How to express the following algorithm more concisely

I have the following algorithm which needs to be expressed more concisely using mathematical symbols and I need help for that. The algorithm accepts a square matrix and a related set of integers ...
5
votes
1answer
154 views

A trivial but maybe nonetheless non-trivial method of inferring primality

The topologist J. H. C. Whitehead (not to be confused with his famous uncle) said it is naive to think a theorem is trivial merely because its proof is trivial. Hence I'm wondering if a certain ...
0
votes
2answers
243 views

What is wrong with my algorithm (finding if the origin is within a triangle's interior)?

I am working on Project Euler Problem 102 and I thought I had a solution, but it seems I do not. Now, don't give me the solution. I know I'm on the right track. What I want to know is why my method ...
1
vote
0answers
619 views

Finding maximal set of vertex disjoint augmenting paths in Hopcroft Karp

In trying to implement the Hopcroft-Karp algorithm I have run into something I do not quite understand. In the step where you find the maximal set of vertex disjoint augmenting paths. How does one ...
1
vote
1answer
83 views

Find a path in G which cross all the edges in $A\subseteq E$

Given a directed graph $G=(V,E)$ and a subset $A\subseteq E$. I need to find an efficient algorithm to find a path (it doesn't have to be a simple one) which cross all of the edges of A, or inform ...
3
votes
0answers
182 views

Simulation and Stochastic Processes

Supposing we want to take a sample from the distribution $p(x)=cp^*(x)$ where $c$ is the normalization constant and $p^*(x)$ is given by $$p^*(x)=0.5\exp(-(x-\mu_1)^2)+0.5\exp(-(x-\mu_2)^2).$$ ...
2
votes
2answers
260 views

What exactly happens, when I do a bit rotation?

I'm sitting in my office and having difficulties to get to know that exactly happens, when I do a bit rotation of a binary number. An example: I have the binary number 1110. By doing bit rotation, ...
7
votes
1answer
240 views

Tuning the birthday paradox

I have limited access to a collection $X_1,\ldots,X_m$ of sets of positive integers. Each $X_i$ is "moderately large" (a brief survey has found them to contain about $10^6$ elements in each set), but ...
2
votes
2answers
119 views

Formula for the number of 0's in an alternating 0-1 matrix

I was working with a piece of code when I stumbled across a matrix, which is similar to this: $$\begin{matrix} 0&1&0&1&0&1&0&\cdots\\ ...
2
votes
1answer
119 views

Selecting and Grouping a set of points in a 2D plane

I am currently working on a project that requires to solve the following problem: Let's say that each time a user access a specific resource on the network from his mobile device, a system stores his ...
0
votes
1answer
157 views

Algorithms and Simulation

Supposing we want to take a sample from a $N(0,1)$ distribution and i can take a sample from a $N(0,σ^2)$. (a) Construct a disposal/rejection algorithm with function $N(0,σ^2)$, which generates a ...
2
votes
1answer
223 views

Am I using dynamic programming correctly in my solution to this problem?

A homework question states: The task is to move a player along a path of n squares starting a square 1 and moving forward each step. At any point you can do one of three things. Push a ...
3
votes
3answers
390 views

Calculating $\pi(x)$ , a new idea?

I am asking myself if instead of working with the primes in the calculation of $\pi(x)$ up to $x$, we instead work with the composite numbers and then using a simple subtraction to get $\pi(x)$. After ...
2
votes
3answers
2k views

Recurrence equation $T(n)=3T(\sqrt{n}) +1$

I need to find an exact solution to the following recurrence using substitution (change of variables). $$ T(n) = 3T(\sqrt{n}) + 1, \quad \text{ when } n > 2, $$ and $$ T(2) = 1 .$$ I can't get ...
1
vote
2answers
575 views

Counting inversions in lists algorithmically

I want to extract useful info from some data and this makes me think how to do it efficiently. I will try to explain the problem with math terms. If we have a sequence of numbers $A=(a_{1}\space ...
5
votes
1answer
6k views

Detecting polygon self intersection

I'm looking for the algorithm that determines the fact that a polygon has self intersection or hasn't. I'm not needed in calculation of the intersection points coordinates or how many intersection ...
9
votes
1answer
232 views

Matrix algorithm convergence

Suppose I start with a $n \times n$ matrix of zeros and ones: $$ \begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 ...
2
votes
2answers
179 views

weighted ratings

I have a form where users can rate presentations and they can say how knowledgeable they are on the subject. The range for both sets is 1-5. (1 being lousy and 5 being great) So for example, a user ...
1
vote
0answers
69 views

What is the most efficient algorithm for constructing an irreducible polynomial?

Theorem: Assuming that the generalized Riemann hypothesis is true, there is a deterministic polynomial time algorithm to find an irreducible polynomial of degree $n$ over $\mathbb{F_p}$ The ...
1
vote
1answer
49 views

Approximation of closest k-coloured points?

I'm a working software engineer faced with the following problem: I have a set of points on a 2d plane. Each point can have one of $k$ different colours. I wish to select one point of each colour that ...
1
vote
1answer
158 views

Find an optimal 4-tuple which satisfies a boolean expression

(I have post a question with bounty for several days (Find a best 4-tuple which fulfils a variable boolean formula), but unfortunately got no answer yet. Here I simplify it to a smaller problem and ...
0
votes
1answer
228 views

reliable formulas/algorythms to find approximate number of primes up to a value and fast deterministic ways to check if a number is prime

I'm new to this place and I have two problems. I'm writing a program and I need to know: (A) A formula/algorithm for the approximate number of prime numbers up to a number. Example: let's say that I ...
3
votes
2answers
2k views

Efficient algorithm to find maximum of a unimodal sequence

We have $a_{1}<a_{2}<\dots <a_{p}$ and $a_p > a_{p+1}>\dots>a_{n}$. We want to find the maximum element $a_{p}$ of a unimodal sequence reading as few elements is possible. I want to ...
3
votes
3answers
753 views

Graph theory- Deleting a vertex from a graph

Given an undirected connected graph $G=(V,E)$ and two vertices $s,t \in V$ . We know that the length of the shortest path from s to t is bigger than $V / 2 $. I would love your help with proving ...
0
votes
1answer
75 views

inapproximability within $1+n^{\epsilon}$

I am a bit confused with the notation of an optimization problem not being approximable within a factor of $(1+n^{\epsilon})$. What exactly does this mean? I am confused because if I (as a user of ...
0
votes
2answers
523 views

Design an $O(n)$ deterministic algorithm to find the approximate median of an array

We have an unordered sequence $A$ which consists of $n$ different numbers $A[1],A[2],A[3],\dots, A[n]$. One member of $A$ is named an approximate median if $A$ contains at least $n/4$ members ...
2
votes
2answers
101 views

Which oracles does Relativization apply to?

In 1975, Baker, Gill, and Solovay presented a landmark paper on Relativizations of the P ?= NP question. My question is fairly simple. Does their theory hold for all oracles? I ask this because I'm ...
6
votes
1answer
1k views

Why is sorting pancakes NP hard?

An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with ...
9
votes
2answers
131 views

Efficient method for detecting a convex body in $\mathbb{R}^n$

Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The boundary between $K_1$ and $K_2$ is ...
2
votes
1answer
178 views

How does the backward/forward algorithm work if there is no end?

I'm using Jason Eisner's spreadsheet to understand HMM more better. There's a box at the top that have a transition matrix. I see the Cold day and Hot day options, but don't understand why there's a ...
0
votes
1answer
853 views

Is this Hermite interpolation correct?

Someone can explain this hermit interpolation algorithm with example? Thank you, ...
0
votes
1answer
75 views

Geometry: problem with defining the vertices of a tunnel around a given path

I'm trying to create some kind of demo that rushes through a tunnel. I have made a random path generator that creates smooth looking paths in 3D space (just some 3D points) Now I would like to ...
3
votes
3answers
239 views

reversible, reflexive function with unique cardinality

I'm looking for a function where f(x1, x2) = f(x2, x1), but f(x1, x2) CANNOT equal any other f(xi, xj). Also, f() must also be reversible, so I could calculate xi from f(xi, xj) and xj. Can anyone ...
0
votes
1answer
162 views

Find a best 4-tuple which fulfils a variable boolean formula

I am looking for an algorithm... I have a kind of boolean formulae which contain $\wedge$, $\vee$, $+$ as arithmetic operator, relational operators ($<, >, \ldots)$, 4 integer constants $c_0, ...
1
vote
1answer
103 views

What is the maximum value of the minimum number of balls per bin?

$S$ people, $N$ bins, each person has a given subset of bins he can cover, each person is given $t$ balls. Question: What is the maximum value of the minimum number of balls per bin? i.e., allocate ...
4
votes
1answer
644 views

Is there a simple algorithm to generate unlabeled graphs?

While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
18
votes
4answers
10k views

Non-power-of-2 FFT's?

If I have a program that can compute FFT's for sizes that are powers of 2, how can I use it to compute FFT's for other sizes? I have read that I can supposedly zero-pad the original points, but I'm ...
1
vote
0answers
85 views

What exactly is a “representation singularity”?

I've heard the term "representation singularity" in a few contexts about numerical instability of algorithms to find Gröbner bases, but I can't seem to find a precise definition for what it actually ...
3
votes
4answers
730 views

Is there an algorithm to recover a crossword grid based on the clues alone?

Suppose that we have access to only the clues of a crossword puzzle along with the number of letters that the answers are supposed to be. Is there an algorithm that we can use to reconstruct the ...
3
votes
2answers
3k views

How to construct magic squares of even order

Could someone kindly point me to references on constructing magic squares of even order? Does a compact formula/algorithm exist?
1
vote
4answers
341 views

Figuring out probabilities with Hidden Markov Models

I'm really new to Math so sorry in advance if this question does not make sense. Also I cross posted this on stats.stackexchange.com also. Background: I'm trying to learn about hidden Markov models ...
5
votes
1answer
232 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
3
votes
4answers
2k views

The tricky time complexity of the permutation generator

I ran into tricky issues in computing time complexity of the permutation generator algorithm, and had great difficulty convincing a friend (experienced in Theoretical CS) of the validity of my ...
2
votes
3answers
818 views

What is numerical step by step logic of SVD (singular value decomposition)?

After this previous question, we want to perform a numerical approximation to the singular value decomposition $\mathbf A=\mathbf U\mathbf \Sigma\mathbf V^\top$. But we can operate only with matrix ...
5
votes
1answer
2k views

Shortest path algorithm used with Google Maps

Maybe posting this question here is wrong, if so I'm sorry and please close this topic. I was wondering which shortest path algorithm is used by Google Maps to find the minimal route between two ...
1
vote
2answers
61 views

Is there a way to find $P(H_h)$, $P(E_\epsilon|H_\eta) (1 \leq \epsilon \leq e)$ and $P(E_\epsilon) (1 \leq \epsilon \leq e)$?

The problem: If we have $P(H_\eta|E_1,E_2,...,E_e)(1 \leq \eta \leq \mathbb{H})$ and $P(E_1,E_2,...,E_e)$ for all True and False values of $E_\epsilon(1 \leq \epsilon \leq e)$ and ...
4
votes
3answers
1k views

What is step by step logic of pinv (pseudoinverse)?

So we have a matrix $A$ size of $M \times N$ with elements $a_{i,j}$. What is a step by step algorithm that returns the Moore-Penrose inverse $A^+$ for a given $A$ (on level of ...
3
votes
1answer
924 views

Actually applying Simon's Algorithm

I'm trying to wrap my head around Simon's Algorithm (the quantum computing one), and all I can find on the internet is the formal defition: nobody actually ever does it with real input. However, I do ...
5
votes
2answers
389 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
0
votes
2answers
3k views

How to get/approximate distance between 2 close points (given in latitude/longitude)?

I have 2 points with their latitude/longitude coordinates and I know that they are in a X miles radius circle (let's say 10 miles radius) somewhere on earth where it's populated (I mean not near the ...