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)

10
votes
4answers
463 views

Application of computers in higher mathematics

Currently the main application of computers in mathematics seems to be to compute things, i.e. to solve equations, evaluate integrals, etc. It is at all possible to delegate the thinking of a ...
7
votes
1answer
460 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
5
votes
1answer
7k views

Finding XOR of all subsets

Moderator's note: this is an on going contest problem. Per usual protocol the answers have been hidden and the question is locked until the end date of the contest. (21.03.2014) Given a list ...
2
votes
2answers
6k views

Worst case analysis of MAX-HEAPIFY procedure .

From CLRS book for MAX-HEAPIFY procedure : The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row of the tree is exactly half full I fail to see this ...
11
votes
1answer
2k views

In-place inversion of large matrices

In Solving very large matrices in "pieces" there is a way shown to solve matrix inversion in pieces. Is it possible to apply the method in-place? I am refering to the answer in the ...
8
votes
2answers
357 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
7
votes
3answers
332 views

Algorithm for multiplying numbers

Background Today I had to explain to some kid how to multiply numbers with multiple digits in them. Then I recalled, that some other day I answered this question describing one of the numerous ...
7
votes
3answers
2k views

What's the proof of correctness for Robert Floyd's algorithm for selecting a single, random combination of values?

I read about it in a SO answer: Algorithm to select a single, random combination of values? ...
7
votes
1answer
1k views

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
6
votes
4answers
20k views

Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
6
votes
1answer
7k 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 ...
6
votes
3answers
4k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?
6
votes
4answers
542 views

Algorithm for constructing primes

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$? There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking ...
5
votes
2answers
328 views

Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
5
votes
2answers
4k views

Can someone explain the algorithm for composition of cycles?

Let $\sigma=(1\ 3),\ \tau=(2\ 4\ 5),\ \pi=(2\ 3\ 4) \in S_{5}$. Find $\pi\circ\tau\circ\sigma$. I know the solution is $(1\ 4\ 5\ 3)$. What i'm doing now is writing the permutations in the ...
3
votes
2answers
8k views

Is there a simple method to do LU decomposition by hand?

Today my professor in numerical analysis pointed out that in the exam we will probably have to do LU decomposition by hand. I'm understand how the decomposition works theoretically, but when it comes ...
3
votes
1answer
3k views

Convert a B-Spline into Bezier curves

I have a B-Spline curve. I have all the knots, and the x,y coordinates of the Control Points. I need to convert the B-Spline curve into Bezier curves. My end goal is to be able to draw the shape on ...
3
votes
1answer
282 views

Finding the topological genus of a triangulated surface

Given is a surface represented through a triangle mesh (as commonly used in computer graphics, with vertices, edges and faces). The surface is known to be "watertight", i.e. no missing faces. Is ...
1
vote
2answers
10k views

How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
13
votes
2answers
2k views

Median of distinct numbers

What is the least number of comparisons we need to find the median of 6 distinct numbers? I am able to find the answer to the median of 5 distinct numbers to be 6 comparisons, and it makes sense, ...
12
votes
2answers
987 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 ...
11
votes
3answers
452 views

Deducing correct answers from multiple choice exams

I am looking for an algorithmic way to solve the following problem. Problem Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
11
votes
1answer
7k views

When does a Square Matrix have an LU Decomposition?

When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
9
votes
1answer
453 views

Is there a binary spigot algorithm for log(23) or log(89)?

The Bailey-Borwein-Plouffe formula yields a binary spigot algorithm for π, and related formulas give the bits of log(2) and those of the logarithms of some other integers. I got stuck (over a year ...
8
votes
3answers
877 views

$3 \times 3 $ Magic Square of Squares

On picture below is three-by-three magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the ...
7
votes
3answers
150 views

Knight move variant: Can it move from $A$ to $B$

Given a $N\times N$ "chess" board (Let $N = 10^{100}$) and a knight at $(0,0)$. Can the knight go to the position $(x, y)$ with jump $[a, b]$ moves ? jump $[a, b]$ mean: the knight on ...
7
votes
1answer
147 views

Bounds on the gaps in a variant of polylog-smooth numbers.

Sorry for the long intro. I think the explanation motivates the question and puts it in context. But if you want to skip the story, then just move on to the grey boxes; they should contain enough ...
7
votes
3answers
749 views

Counting primes

Let $\pi(x)$ be the number of primes not greater than $x$. Wikipedia article says that $\pi(10^{23}) = 1,925,320,391,606,803,968,923$. The question is how to calculate $\pi(x)$ for large $x$ in a ...
6
votes
5answers
330 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
6
votes
1answer
872 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
6
votes
1answer
3k views

how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors

How does one diagonalize a large sparse symmetric matrix to get the eigenvalues and the eigenvectors? The problem is the matrix could be very large (though it is sparse), at most 2500*2500. Is there ...
5
votes
3answers
2k views

One number divisible by all prime factors of another?

Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
5
votes
1answer
720 views

Efficiently calculating the logarithmic integral with complex argument

My number theory library of choice doesn't implement the logarithmic integral for complex values. I thought that I might take a crack at coding it, but I thought I'd ask here first for algorithmic ...
4
votes
2answers
796 views

Russian Peasant Method for multiplication

What exactly happens with the remainder in this algorithm? I don't understand why it is "dropped". Example: $$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline ...
4
votes
2answers
746 views

Upper bound for the partial sum $\sum k \lg k$ via summation?

In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound: $$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} ...
4
votes
3answers
400 views

Is there an algorithm to find the roots of high-order polynomials?

It is not generally possible to determine the roots of a polynomial whose grade is bigger than 4 in terms of roots and basic operations. But I heard, that it is possible to give a criteria whether a ...
4
votes
1answer
2k views

Factoring large integers without a cluster

What is the best program to factor large arbitrary-form integers on a single computer, or on a few disjointed computers? "Best" is obviously subjective, but what do you recommend? I'm working on a ...
2
votes
3answers
107 views

Finding XOR of all even numbers from n to m

Problem : Given a range $[n,m]$, find the xor of all even numbers in this range. Constraints : $1 \le n \le m \le 10^{18}$ How do we solve this problem? P.S. I asked this question at stackoverflow ...
2
votes
2answers
98 views

Santa is secretly deranged! or, how to hand-generate assignments for a gift exchange?

Consider a standard Secret Santa/gift exchange game draw. We have a pool of $n$ people, each of whom is supposed to be assigned another member of the pool to find a gift for, without the recipient ...
2
votes
1answer
165 views

Are there any sets other than the usual in which we can apply Sturm's axioms?

As we all know, Sturm's axioms have completely solved the problem for finding the number of roots in an arbitrary interval $[a,b]$, using the derivative and forms a Sturm set. Now my question ...
10
votes
2answers
765 views

What would be the shortest path between 2 points when there are objects obstructing the straight path?

How would an algorithm find the shortest distance between 2 points on a horizontal 2d plane , especially when a straight path is not possible? Could it be something on the lines of calculating least ...
10
votes
2answers
11k views

How to calculate the number of decimal digits for a binary number?

I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but... Given a number represented in binary, it's ...
9
votes
2answers
951 views

Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
9
votes
1answer
4k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
7
votes
3answers
4k views

Finding prime factors by taking the square root

I'm trying to solve the third Project Euler problem and I'd like a little help understanding a mathematical concept underlying my tentative solution. The question reads: The prime factors of ...
7
votes
0answers
392 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
6
votes
1answer
505 views

Count expressions with 1s and 2s

Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * ...
5
votes
1answer
258 views

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed? We define $f(n)=m$ where the digits of $m$ and $n$ are reverse. Such as ...
5
votes
1answer
234 views

How to find the value of positive integers $a$-through-$h$

If the equation $(x-a)(x-b)(x-c)(x-d)(x-e)(x-f)(x-g) = hx$ has seven positive integer roots, and $a,b,c,d,e,f,g,h$ are positive integers too, how can we find them?
5
votes
2answers
504 views

Sparse basis for linear subspace

Suppose I have a linear subspace of some vector space, e.g. described as the column space of some big matrix. How would I algorithmically find a basis of that same subspace where the basis matrix is ...