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)

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
159 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 ...
20
votes
4answers
5k 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) ...
0
votes
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
720 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
547 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.
2
votes
3answers
244 views

Math/CS Algorithm Analysis Question

I've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me. Please note, I'm not asking you to do this problem for me, just to make ...
1
vote
2answers
651 views

Question about the “Cat in the Hat” problem

I'm looking at the Cat in the Hat problem. Can anyone explain to me how a simple math logic is used to derive this equation? $$\left(\frac{N}{N+1}\right)^{M-1} = \frac{B}{A}.$$
0
votes
1answer
86 views

Derived equation [duplicate]

Possible Duplicate: Question about the “Cat in the Hat” problem I'm looking at the Cat in the Hat problem. Can anyone explain to me how a simple math logic is used to derive ...
0
votes
1answer
191 views

Need an algebraic formula for this algorithmic problem

I'm not sure if there is a given term for this problem but I'm trying to find the number of iterations required to complete this type of pattern: Consider two patterns/lists: ...
4
votes
1answer
254 views

How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some ...
21
votes
2answers
807 views

Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely, $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$ This is Theorem 4 ...
3
votes
0answers
231 views

Finding position in a tree based on node number

Let us assume my tree starts with $1$ node, then each node has $2$ nodes beneath it. Let us also assume the top node of the tree is numbered $1$, and node $2$ and $3$ are directly beneath it. An ...
0
votes
1answer
116 views

Unbiased (random?) selection algorithm

Let say we have the following set $S = \{x_1, x_2, x_3, ..., x_n\}$ where $x_i$ is a real number between $0$ and $1$. Now I want to find an algorithm that randomly generates a subset of $S$, free to ...
9
votes
2answers
348 views

Finding upper segments of intersecting parabolas

I have multiple parabolas ($y = ax^2 + bx + c$) which may intersect with each other (or some of them may not intersect). I am trying to find upper segments of these parabolas, e.g. bold part in the ...
2
votes
1answer
3k views

How to find the center of mass of a complex 2d shape

So I'm hoping someone could help me get a solid algorithm for finding the center of mass of 2D shape without density, based of a set of vertices. Please explain in simple terms that a ...
3
votes
1answer
603 views

Boxcar Recursive Method for Finding Standard Deviation

I'm trying to develop a real time algorithm for finding level areas of an electrical signal. To do so I need to find the variance for a particular rolling time interval. From John Cook's blog and ...
2
votes
1answer
144 views

Get matrix coords from a single index and matrix dimensions

Having a set of ordered numbers $$ \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \} $$ If you put them in a matrix so the index is at the same time the content Matrix dimension $=$ row x col $= 3\times ...
3
votes
2answers
149 views

The fundamental group of $K_{3,3}$ — relationship between its generators and embedding into manifolds

So I've been reading this wonderful PDF textbook on algebraic topology: http://www.math.uchicago.edu/~may/CONCISE/ConciseRevised.pdf In particular, I'm very interested in the chapter on graphs. This ...
5
votes
1answer
255 views

Is there an efficient algorithm to determine the parity of the longest path in a graph?

Finding the longest path in a graph is intractable problem. Th decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in ...
2
votes
0answers
96 views

Probabilistic analysis of two algorithms

Let $f$ be a binary function programmed at random; i.e. for any $x$ in its domain, $f(x)$ equals some $n$-bit value initially chosen at random. Such a function has the nice property that for any two ...
2
votes
1answer
79 views

Specific solvable cases of TSP

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog ...
2
votes
1answer
378 views

variable update operator , using “correct” mathematical notation

In a text describing mathematically an algorithm, there is a vector $y_l$ (local y-axis) which is computed, but must be subsequently adjusted to avoid numerical drift. I've considered a few ...
5
votes
1answer
179 views

Algorithm for computing the rank of the fundamental group of a graph?

I've been learning a bit about applications of algebraic topology to graph theory and I'm interested in figuring out how to compute the fundamental group $\pi_1(X,x_0)$ of an arbitrary graph ...
2
votes
2answers
895 views

Bound for divisor function

I have been searching for a bound of the divisor function $d(n)$, meaning the number of divisors of n. So far I have found that it can be bounded by $$ d(n) \le e^{O(\frac{\log n}{\log \log n})}$$ ...
0
votes
2answers
190 views

Algorithm to randomly place circles at least $D$ distance away from one another

I'm trying to work out how to write an algorithm to randomly place circles of $R$ radius, in a $2D$ rectangle of arbitrary dimensions, such that each placed circle is at least $D$ distance away from ...
1
vote
0answers
84 views

First hitting time for generalized Pólya urn

I have looked around the literature but I've not found a clean answer to the following. Imagine that you have a generalized Pólya urn (GPU) in the sense of Pemantle's survey (Section 2.1 in ...
4
votes
3answers
160 views

Is there any algorithm for this (simple problem?)

I have a table like this: ...
4
votes
2answers
198 views

Construction of a basis

I know that for a vector space $\mathbb R^n$ one can use the Gram-Schmidt process to construct its basis. But what if the vector space is over some arbitrary field? I am thinking of the following: ...
9
votes
2answers
3k views

Generate Random Latin Squares

I'm looking for algorithms to generate randomized instances of Latin squares. I found only one paper: M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. ...
1
vote
1answer
133 views

Checking if all elements are prime

I've often come across problems where (as a subproblem) I need to decide whether a list of numbers contains only primes or at least one nonprime. Is there an efficient way to do this? Right now I ...
4
votes
1answer
2k views

Mathematical model for solving minesweeper situations

Suppose there's a minesweeper board like the following: 1 1 1 A B C Where A, B, C is an unrevealed square which could contain a mine. This can be represented ...
5
votes
2answers
1k views

Tranforming 2D outline into 3D plane

I am writing a program where I would like to allow the user to draw 4 connecting lines, such as: And convert this shape into a 3D plane. Is this possible? Is there an existing algorithm to do so? ...
5
votes
2answers
225 views

An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have. Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm ...
1
vote
1answer
2k views

shortest path between two vertices in a graph

I realize this is a very basic question, but I am amazed that I didn't find much useful information on the web: Given a (directed/undirected) edge weighted graph G, and two of its vertices u,v, is ...
1
vote
1answer
797 views

Algorithm for finding limits of compositions of simple functions?

There are two questions: Define the set $S$. Compute the limit of functions $f/g$ for functions $f,g\in S$, where $S$ is defined in the following way. All constant function are in $S$, $f(n) = ...
2
votes
1answer
221 views

Asymptotic upper bound of Bisecting trees

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced ...
13
votes
4answers
9k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
5
votes
1answer
533 views

What kinds of optimization problems can be solved by greedy algorithms accurately?

I was wondering what kinds of optimization problems can be solved by greedy algorithms accurately? I don't understand the following quote from Wikipedia: Greedy algorithms can be characterized ...
12
votes
2answers
899 views

Partition a binary tree by removing a single edge

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a ...
1
vote
0answers
98 views

Computing a generating set of the kernel of a module

Given a generating set of a $\mathbb{Z}$-module $M \subseteq {\mathbb{Z}_k}^n$, is there a known algorithm to compute a generating set of $\{u \in {\mathbb{Z}_k}^n \, : \, \forall v \in M \quad v ...
6
votes
1answer
292 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
11
votes
2answers
4k 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 ...
5
votes
1answer
2k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
4
votes
1answer
698 views

Unscramble images without trying all permutations

I try to write an algorithm that unscrambles images that were before scrambled by mixing up small blocks: My idea is that in the bottom image there are more "sharp" corners compared to the image ...
28
votes
3answers
12k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
0
votes
1answer
75 views

What is the correct seminormal representation of (23) corresponding to the [22] partition of S4?

I am studying an undergraduate thesis, called A Fast Fourier Transform for the Symmetric Group, by Tristan Brand, one time a student at Harvey Mudd College. Source: ...
1
vote
2answers
2k views

Velocity Measurement Error Estimate

I have 2 position estimates (along with their measurement error) and a difference in time between estimates. I estimate velocity using ...
2
votes
0answers
108 views

What does it mean if a sequence is indexed beyond its bounds?

I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences. Part of the algorithm involves ...