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)

6
votes
1answer
150 views

How to check if a polytope is a smooth Fano polytope?

Question: We say that a convex lattice polytope $P\subset \mathbb{R}^d$ is a smooth Fano polytope if: The origin is contained in the interior of $P$ The vertices of every facet of $P$ are a ...
8
votes
2answers
4k views

Finding irreducible polynomials over GF(2) with the fewest terms

I'm investigating an idea in cryptography that requires irreducible polynomials with coefficients of either 0 or 1 (e.g. over GF[2]). Essentially I am mapping bytes to polynomials. For this reason, ...
4
votes
1answer
499 views

Finding the smallest prime number that divides $Fib(n)$ but not any other $Fib(k)$ smaller than $Fib(n)$

Let $F(n)$ be $n$-th Fibonacci number.$$F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3 \text{ and so on. }$$Given a positive integer $n \gt 2$,Find the smallest prime number $P$ such that $P$ ...
1
vote
1answer
555 views

Square-free Integers Factorization

Suggest an algorithm for factorizing an integer such that each of its factor is square-free. Thanks,
1
vote
2answers
244 views

A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$. I am inquisitive about how to approach this one?
7
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
3
votes
3answers
523 views

Encrypting algorithm

I know there are some encrypting algorithm that once the text (the message) is encrypted there is no way to decrypt it. I can think one way of doing this: using as encryption key the current date at ...
0
votes
1answer
183 views

Lattice simplification

Update: There is an answer on same question I posted on Stack Overflow. I'm working on data structure for graph cut algorithm. Problem is to make different cuts on shortest paths. I made data ...
2
votes
2answers
142 views

Development of a specific hardware architecture for a particular algorithm

How does a technical and theoretical study of a project of implementing an algorithm on a specific hardware architecture? Function example: ...
26
votes
4answers
9k views

Calculator algorithms

Does there exist a good reference on the algorithms used by calculators, especially on the trigonometric and transcendental functions? I would still like to know how Casio generates its random ...
6
votes
2answers
334 views

Which features would be interesting for a mathematician in a fractal program?

Many years ago I wrote this fractal generator: http://uberto.fractovia.org/ It was shareware but then I put it as open source. It's written in Delphi, a language that I don't use anymore. So I'm ...
2
votes
1answer
80 views

Question regarding Dynamic Programming for Audio Recognition

Currently I am implementing a DTW (Dynamic Time Warping) algorithm for my project. As some will know it has the complexity of O(n^2). Considering a sound file of length 1-h with 44100 sampling. How ...
0
votes
1answer
152 views

Can someone tell me what “min” means in this context?

I am attempting to write a function (programming, not mathematics) which calculates the shortest distance between two points on a toroid. I got the following formula from StackOverflow, but I don't ...
3
votes
2answers
2k views

Finding index of a Fibonacci number: any mathematical solution possible?

The problem: Given a Fibonacci number,find its index. I am aware of the standard solution 'generate-hash-find'. I am just curious if there is ...
1
vote
5answers
103 views

Algorithm to find figures using input points

I have just discussed with student and he told me him task, and I think it is interesting. The task. There are file with points like: ...
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 ...
16
votes
4answers
7k views

Determining whether a symmetric matrix is positive-definite (algorithm)

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition. The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky ...
2
votes
1answer
1k views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull
2
votes
1answer
2k views

Help understanding the proof that 2SAT is in P

I have read this paper and the wikipedia summary here and even this homework problem, but I do not understand how 2SAT is in P. Here is my concern: the idea is that we start by setting a random ...
4
votes
2answers
111 views

Algorithm for discarding geographically disgregate points

The context: I'm working on geocoded documents. This is, documents have latitude and longitude attributes, as well as some other geo attributes such as an address. Right now, I'm performing text ...
5
votes
3answers
664 views

knapsack algorithm that looks too good to be true

I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset ...
1
vote
1answer
539 views

Marching tetrahedra (or cubes) on a non-orthogonal 3D grid

I have data for points of a 3D grid. The points of the grid are generated from three nonorthogonal vectors: each grid point has coordinates $\mathbf{q}_{ijk} = i \mathbf{a} + j \mathbf{b} + k ...
9
votes
2answers
872 views

Can we reduce the number of states of a Turing Machine?

My friend claims that one could reduce the number of states of a given turning machine by somehow blowing up the tape alphabet. He does not have any algorithm though. He only has the intuition. But ...
5
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 ...
3
votes
2answers
236 views

Rounding trouble in a calculator's square root function

I made the following observation following a suggestion from a friend. This question is about the Microsoft calculator program implemented on Windows. Since I don't have access to any other calculator ...
0
votes
2answers
218 views

$f(x) = f(x-1)*b \to f(x) = c_1 b^{x-1}$

I'm trying to teach myself mathematics. I only started last year with a previous knowledge of basic arithmetic. I often make a detour into regions featuring problems that are a bit too deep for me. ...
1
vote
0answers
100 views

Minimum rectilinear net

I'm looking for an algorithm to solve this problem: Given set of n points on 2D euclidean space, create a net of rectilinear edges, so that: Every two points are connected with shortest edge, and ...
2
votes
3answers
356 views

Partitioning a graph (clustering of point sets in 2 dimensions)

I am given $n$ points in 2D.(Each of say approximately equal weight). I want to partition it into $m$ clusters ($m$ can be anything and it is input by the user) in such a way that the center of mass ...
3
votes
0answers
155 views

The $n$-shortest lattice vectors problem in $\mathcal{R}^2$

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows: Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a ...
11
votes
4answers
2k views

How can one efficiently generate n small relatively prime integers?

The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost ...
3
votes
2answers
475 views

shadow simulation from buildings

is it possible to calculate shadow areas of buildings or simulate shadows of buildings in a city, using the heights of these buildings and the sun angle and azimuth? the basic light tracing concept ...
2
votes
1answer
343 views

Looking for an algorithm for grouping based on preferences

I am looking for an algorithm that "describes" the following situation: 15 - 22 people are combined into groups of 4 or 5 based upon stated preferences of who they wish to be grouped with. Each ...
2
votes
3answers
249 views

Expected time of tree search algorithm on random input

We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm ...
4
votes
2answers
11k views

How do you calculate percentile?

Say I have the following numbers: 10 10 9 5 4 4 4 1 How do i go about calculating the percentile for each score? Is there a standard formula for figuring this ...
2
votes
3answers
2k views

What are the prerequisites for combinatorics?

I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
2
votes
1answer
1k views

Gauss Jordan elimination - count of steps for $N \times M$ equation

I am having some problem wrapping my head around an assignment. I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear ...
1
vote
1answer
3k views

Calculating the Savitzky-Golay Coefficients

I am working on a signal-smoothing algorithm for personal interest. I understand the basic concept of the Savitzky-Golay algorithm but I would like to understand how the coefficients were discovered. ...
1
vote
5answers
656 views

Computing GCD of all permutations (of the digits) of a given number

Consider a number say N = 345 The Permutations are :{{3, 4, 5}, {3, 5, 4}, {4, 3, 5}, {4, 5, 3}, {5, 3, 4}, {5, 4, 3}} The GCD of all of them is 3 which is the answer.Please suggest a suitable ...
7
votes
5answers
2k views

The least prime greater than 2000

I'm a bit curious as to how "real" mathematicians would solve this problem. "Find the least prime number greater than 2000." Of course, I can always go brute force: ...
4
votes
1answer
624 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 ...
3
votes
1answer
506 views

Algorithm for shortest path on manifold

What are some algorithms used for finding the shortest path between 2 points on a (riemannian) manifold (the manifold may have a smooth boundary)? So far I've had 3 ideas, none of which seem that ...
1
vote
3answers
3k views

How to (efficiently) compute the sum of the digits of evey number lying between two given numbers?

Given two integers A and B , how to efficiently compute the sum of all the digits of every number int the set $\{N | A \le N \le B \} $. For example: A = 100 and B = 777, then the required answer ...
4
votes
2answers
5k views

Number of common divisors between two given numbers

How can I compute the number of common divisors of two naturals ? For example,if we consider (12,24) the answer is 6 i.e ...
1
vote
1answer
410 views

How to calculate a Bézier curve with only start and end points?

This animation from Wikipedia shows basically what I want to accomplish, however - I'm hoping to have it flipped around, where it starts progressing more towards the destination and "up" (in this ...
1
vote
1answer
232 views

Finding a Pattern Between Latin Squares

I manually arranged two complete latin squares from ordered pairs of 4 and 6 like so: ...
12
votes
1answer
574 views

Use of FFT in the multiplication of multinomials

I'm aware that one can use a Fast Fourier Transform (FFT) to take the cost of multiplication of two polynomials of degree N from O$(N^2)$ to O$(N \ln N)$ (which is an amazing reduction when dealing ...
5
votes
1answer
424 views

Balancing a Latin Square

I'm searching for an algorithm that forms a balanced (or quasi-complete) latin square, in which every element is a horizontal neighbor to every other element exactly twice, and a vertical neighbor to ...
4
votes
1answer
1k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
3
votes
3answers
408 views

Help me understand linearly separability in a binary SVM

I have a question pertaining to linear separability with hyperplanes in a support vector machine. According to Wikipedia: ...formally, a support vector machine constructs a hyperplane or set of ...
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, ...