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)

5
votes
2answers
442 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 ...
2
votes
1answer
977 views

Balancing weights with weights

We have a collection of items of weight $d_i$, $$d_1, d_2, ..., d_k, \quad k \le 100$$ where some of the weights may be equal. Let $$ n = \sum_{i=1}^k d_i $$ I need to figure out quickly if this ...
3
votes
1answer
3k views

Quick algorithm for computing orders mod n?

Is there a fast way to compute the order of $a \pmod n$ without computing potentially all the powers of $a$ up to $n-1$? For example, in computing the order of $87 \pmod {101}$, the naïve way could ...
1
vote
0answers
88 views

Questions about interpolating translated points from a grid

I would like to do the following transformations on a very low resolution bitmap (64x64 pixels). I am doing this transformation on a computer images, but it has nothing to do with computers, you can ...
1
vote
1answer
136 views

Strategy to maximize no. of balls from N boxes

If you have N boxes each containing distinct number of balls and you are allowed to choose at most ...
1
vote
1answer
105 views

A special case of the minimum number of multiplications used to compute a product of matrices

A fact about complexity of algorithms for computing the product of matrices was brought up to me that was very interesting I was not aware of. I still am not sure what the optimal bound is on the ...
0
votes
2answers
120 views

Set of data that needs to be weighted to be put on the same scale. Possible with this data?

I've never posted on this forum, so I hope this question is valid... I have sets of data that are composed of these values (simplified) ...
18
votes
0answers
1k views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
3
votes
2answers
1k views

Schönhage-Strassen multiplication

I am trying to implement the Schönhage-Strassen algorithm (SSA) for multiplying large integers, but it only gives the right result if all $\delta_j$ are zero. I'll explain what I mean by this: SSA (...
0
votes
2answers
87 views

Finding optimal path for evaluating expressions

I am creating a program which needs to do the following: I have equations like the following and based on the input I get I should able to calculate the values of $x$, $y$ and $z$ $$x = a + b$$ $$y =...
2
votes
2answers
414 views

Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've ...
20
votes
1answer
499 views

Extracting individual race results from Mario Kart final scores

In Mario Kart, one "cup" involves 4 races, and after every race each racer gets points awarded based on what place they came in (better rank means more points). After playing it enough I grew curious ...
4
votes
1answer
201 views

Algorithm for keeping a concrete version of Euclid's argument simple

(My actual question is at the very bottom of this posting.) Suppose you're teaching a course in mathematics-for-liberal-arts majors and it's the last math course they'll ever take. It has almost no ...
3
votes
2answers
1k views

Find the minimum number of links to remove from digraph to make it acyclic

As the title says, I am looking for a way to find the minimum number of links to remove from a directed graph to make it acyclic. I am looking both for the minimum number, as well as an actual set of ...
1
vote
1answer
97 views

Line segment k-intersection

Could you please help me to design the following algorithm: I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course ...
1
vote
0answers
498 views

Complexity of divide and conquer algorithms?

I have two datasets with $n$ and $m$ points. To find the match I have to compare each point in one data set with the other data set which makes the complexity $O(m\times n)$. I did some heuristics and ...
5
votes
3answers
959 views

How to approach number guessing game(with a twist) algorithm?

I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
1
vote
0answers
106 views

Graphs: the best path

Assume we have a path in an undirected cyclic weighted graph. Assuming we have an engine that can find a path from node A to node B in such a graph, is there an easy way/algorithm to figure out if the ...
4
votes
2answers
275 views

Rota's “lure of the algorithm”?

Quoting Gian-Carlo Rota (from the Foreword to Richard Stanley's Enumerative Combinatorics Volume I), "In mathematics, however, the burden of choice faced by the writer is so heavy as to turn off all ...
0
votes
1answer
383 views

Max Hamming Distance [duplicate]

Possible Duplicate: Comp Sci Math; Hamming Distance I have been set a task: What is the maxium possble Hamming distace between two noes from level i in an n-cube? Provide an explanation for ...
1
vote
1answer
715 views

Questions about cracking playfair using a 'shotgun climbing hill' method

I see this page before. Cracking Playfair code And I download the C file in it.However,I am still confused about the code. How to evaluate a solution? What does this mean? ...
1
vote
1answer
121 views

Algorithm to compute mesh from intersection of infinite halfspaces

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG (...
3
votes
1answer
4k views

Is it possible to make the Breadth First Search Algorithm recursive?

I'm a student an I see the BFS Algorithm for graph exploration. I see the DFS algorithm too and this one is easily thinkable in a recursive mode. But is it possible for the BFS? Thanks.
6
votes
4answers
2k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...
3
votes
0answers
297 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
3
votes
1answer
841 views

Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold

Suppose we have a graph $G$ = ($V$, $E$) where each vertex $v_i \in V$ has a benefit $b_i$ and each edge ($v_i, v_j$) $\in E$ has a weight of $w_{ij}$. I would like to find a subgraph of $G$ that ...
3
votes
1answer
132 views

write the rank function for “untangling line segments” problem

How to write a rank function in math for this problem? Initially: there are 2n points on the Euclidean plane. The points are grouped in pairs with a line segment connecting each pair. Action: the ...
0
votes
1answer
979 views

How many solutions does an equation system with binary values have?

I have an equation system with binary values ($0$ and $1$). After doing a gauss-elimination, I can calculate the determinant by anding the entries of the main diagonal. If it is $1$, it's trivial to ...
1
vote
2answers
188 views

Finding edges that are not part of any perfect matching

Given a balanced bipartite graph, what is, or is there, an efficient algorithm for finding all edges which are not part of any perfect matching in the graph?
1
vote
0answers
138 views

optimize the expected value of a process

There are $a_i$ balls painted with number $i$. For example if we have balls painted with 1,1,1,3,2. we have $a_1 = 3$, $a_2=1$, $a_3=1$. In total there are $m$ balls painted with number $1,\ldots,n$. ...
0
votes
1answer
70 views

Formula to recalculate variables from real numbers range to non-negative range

I'm struggling with this for quite some time now. I'm trying to recalculate values uniformly distributed in real numbers range to numbers in non-negative range. Length of non-negative range can vary (...
9
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
1answer
141 views

Algorithm analysis, finding a constant c and a point n?

Say for example I say that: $$ 2n^2 + n - 8 \quad\text{is}\quad O(n^3) $$ To prove this I must find a constant $c$ and a point $n_0$ for which $n^3$ is an upper bound of the equation. This is ...
6
votes
2answers
535 views

Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app. I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within ...
1
vote
2answers
383 views

Is this time complexity example correct?

This is probably not the best worded question but here goes. I've been reading a text book trying to get my head around time complexity. I understand the most of it, but this example has threw me. ...
0
votes
1answer
64 views

Discreet bounding/mapping function with convergence/uniformity

Firstly, I was sent here from cstheory.stackexchange.com's FAQ, please tell me if this too is the wrong board (this board's FAQ indicates that I have to goto stackoverflow ??) This is my first ...
3
votes
1answer
608 views

Directed Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?

Consider a directed graph with each edge assigned a nonnegative weight D that reflects the difficulty of passing over that edge (perhaps modeling an obstacle course). Define the difficulty of a ...
6
votes
1answer
1k views

What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
5
votes
2answers
395 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
2
votes
1answer
199 views

Cooley-Tukey FFT with arbitrary radices

The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by ...
0
votes
3answers
1k views

What does this notation mean: $\lg^{\ast} n = \min \{ i \ge 0 \,:\, \lg^i n \le 1 \}$?

For my algorithms course I am studying the definition of the iterated logarithm function (and functional iteration in general) and I don't quite understand the set notation used (it's been quite a few ...
2
votes
1answer
182 views

Determining the round players will meet in a knock-out tournament

Given a knock-out tournament with $2^n$ players, I am looking for a formula or algorithm to calculate the round player A will meet player B. For the case $2^n=16$. Player 7 will meet player 8 in ...
7
votes
1answer
1k views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
0
votes
0answers
208 views

Patterson Algorithm

In the proof of Theorem I(c) from this paper (pdf) (original zip), there is a proposition that says: So by our choice of $g$ we get $\theta/p \mid \psi/p$ whence $\theta \mid \psi$. (this is ...
22
votes
5answers
8k views

How does one compute the sign of a permutation?

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula $${\rm sgn}(\sigma) =...
1
vote
1answer
1k views

solving modulo equation

How to solve this $$x^a \equiv b \pmod n$$ I need to be able to find $x$, given $b$. $a$ is always $23407534262244700$ and $n$ is $465992738619896000$. Someone mentioned I can use Fermat and ...
3
votes
0answers
771 views

Project Euler Problem 338

I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
4
votes
1answer
720 views

Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
4
votes
1answer
91 views

Proving that $n^n \notin O((n+1)!)$

How does one show that $n^n \notin O((n+1)!)$ without using limits? I've recently been trying to prove such results without limits, and this is one case that is still bothering me.