# Tagged Questions

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).

271 views

110 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 ...
756 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 ...
14k 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 ...
114 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 ...
813 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 ...
4k 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?
434 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 ...
259 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 ...
3k 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 ...
989 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 ...
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 ...