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)

3
votes
2answers
481 views

Algorithm to determine if a Diophantine Equation has an infinite number of solutions

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether ...
3
votes
0answers
302 views

Approximation of a real number as a linear combination of two reals with coprime integral coefficients

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, give me an algorithm that will provide coprime integers $a$ ...
0
votes
2answers
164 views

Combinations Help

I have an application where I iterate through all k-combinations of a set of size n. For example here I have listed all k-combinations for when n is 4. Also I have separated each list of combinations ...
0
votes
1answer
221 views

Generating a random Eisenstein integer matrix whose inverse has Eisenstein integer entries

Thanks to a question I previously asked, I realized that a Gaussian integer matrix should have a determinant of $\pm 1$ or $\pm i$ for it to have an Gaussian integer inverse. From that, I gather that ...
1
vote
2answers
132 views

terrain generation help

I'm trying to make a 3D terrain generator. In doing so, I decided that I would use basic rectangles and then just turn them by having 4 points, 1 on each side, then turn the rectangle to fit in those ...
2
votes
0answers
185 views

calculate the rate of change

I am trying to calculate the change frequency for a set of data. Each bit of data has the date-time it was created. I would like to say for a specific set of data the change frequency is hourly, ...
6
votes
0answers
523 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
10
votes
1answer
653 views

Honest and Deceitful Professors Problem

I found this in An Introduction to Bioinformatics Algorithms. I've paraphrased for clarity. There are 100 professors. Some are honest, while others are dishonest. There are more honest professors ...
3
votes
1answer
313 views

Proof: BEST-IN-GREEDY-Algorithm for Matroids maximizes all Bottleneck-Functions over Bases

Let $(E,\mathcal{F})$ be a Matroid. Given is a Bottle-Neck-Function $$b(F)=\min\{b(e)|e\in F\}$$ I want to prove that the Best-In-Greedy-Algorithm maximizes every Bottle-Neck-Function over the Bases. ...
2
votes
3answers
295 views

Recursion equations: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$

What's the simplest way to prove that the solution for this recursion equation: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$ , is $T(n)=\theta (n)$? I think that it is $T(n)=\theta (n)$ because it is ...
3
votes
1answer
106 views

Average result of game

I'm trying to find the average result for a game where you have 12 items (containing a score), you can pick up to five of them, one of them is a multiplier, that when selected multiplies your result ...
6
votes
3answers
837 views

A balanced latin rectangle (more rows than columns)

In psychology we sometimes use balanced latin squares for the order of our tests to counterbalance first-order carry-over effects (fatigue, learning, etc.) . For our current study we want to pretest ...
14
votes
3answers
13k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
4
votes
1answer
139 views

Understanding an algorithm for computing a matrix polynomial

I'm trying to understand this algorithm by Charles Van Loan for evaluating a matrix polynomial $p(\mathbf A)=\sum\limits_{k=0}^q b_k \mathbf A^k=b_0\mathbf I+b_1\mathbf A+\cdots$ (where $\mathbf A$ is ...
6
votes
3answers
334 views

Efficiently testing if sigma(n) = m

I'm trying to write a function that efficiently solves this problem: Given positive integers m and n, determine whether $\sigma(n)=m$. Of course I'm looking for a faster technique than "factor n, ...
2
votes
1answer
118 views

Obtaining an asymptotic lower bound on a function

A follow-up question to this one basically Understanding a simplification in a theorem. If you want to see the original paper, see page 6/24 there. We are given that $2 < n \leq M \leq n^2$. Then, ...
2
votes
3answers
69 views

Generating a set based on some constraints

Simplified real world problem that came up yesterday. A new course on my university can be opened if all the attendants can be split into (one or more) groups of n±2 people, where n≥5. So for example ...
1
vote
2answers
74 views

Find an absorbing set in the table: fast algorithm

Consider a $m\times n,m\leq n$ matrix $P = (p_{ij})$ such that $p_{ij}$ is either $0$ or $1$ and for each $i$ there is at least one $j$ such that $p_{ij} =1$. Denote $s_i = \{1\leq j\leq n:p_{ij} = ...
1
vote
0answers
59 views

The hardness and usefulness of average-case analysis

I know that in general it is hard to analyze the average-case (time) complexity of an algorithm. It is challenging to make meaningful assumptions about the distribution of the inputs and/or sometimes ...
4
votes
4answers
323 views

Relationship between degrees of continued fractions

I'm trying to compute the values of differing degrees of continued fractions like $\sqrt 2$, e and other similar fractions. My theory was to take the reduced fraction at an arbitrary depth and the ...
1
vote
2answers
503 views

Cube numbers ending on number X

Let's have some number X which we will call "ending" or "suffix". How to find number which cubed have suffix or ending equal our X? I think good hint is that this number X always ends with odd number ...
7
votes
2answers
539 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
2
votes
1answer
297 views

Matrix column permutation under constraint

Apologize if you've read my question on Mathoverflow, I'm very curious about whether there's an answer to this. In coding theory, there are parity-check codes whose parity-check matrices H are ...
2
votes
2answers
299 views

Computing Stirling cycle and subset numbers with minimal storage

I know that the Stirling cycle numbers $\left[{n}\atop{k}\right]$ and Stirling subset numbers $\left\{{n}\atop{k}\right\}$ both satisfy recursion relations on both $n$ and $k$: ...
4
votes
2answers
461 views

Optimization without knowing function's form or derivative

I understand that this question may not have a corresponding answer. We are developing a control algorithm using dynamic programming. Effectively we are change one input variable and then plot the ...
6
votes
1answer
235 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
6
votes
3answers
3k views

“Closest pair of points” algorithm

I'm having a problem understanding why I just have to consider the next 7 points in the Closest pair of points - algorithm. Can someone explain it in greater detail?
2
votes
1answer
112 views

Calculate appr. weight of hamilton cycle

can i approximate the weight of a hamilton line in a complete weighted graph without implementing any algorithm like NN or calculate the MST? I know the average distance of each node and the metric ...
2
votes
3answers
142 views

Get Point Cloud from Complete Weighted Graph

Is it possible to calculate the x,y position of a node in a complete weighted graph with euklidic metric when i have the weight of every edge in the graph? it would be really usefull for me to plot ...
2
votes
1answer
244 views

Kruskal and Prim

Can someone explain why Kruskal's algorithm and Prim's algorithm are each a special case of the general algorithm for minimum spanning trees? The general algorithm: Let A be the set of selected ...
2
votes
2answers
344 views

Formula to generate a score from 1 to 100 based on 2 percentages?

I am trying to come up with a formula that will result in a score of 1 to 100 (never anything lower or higher). I have two numbers that I can use to come up with this score, a specific percent and an ...
4
votes
2answers
4k views

Implementation of Monotone Cubic Interpolation

I'm in need to implement Monotone Cubic Interpolation for interpolate a sequence of points. The information I have about the points are x,y and timestamp. I'm much more an IT guy rather than a ...
3
votes
1answer
1k views

Coloring a 3-colorable graph with $O(\sqrt{n})$ colors in polynomial time

I am considering the following problem. You are given a graph $G$ that is 3-colorable. You would like to obtain (in polynomial time) a proper coloring for it that uses $O(\sqrt{n})$ colors . My ...
4
votes
2answers
192 views

Finding sets that do not intersect. Approximation algorithm

I am trying to solve the following problem. Let $S$ be a set and $F \subset {S \choose k}$ that is $F$ is a subset of the set of all $k$-sets of $S$. A set $M \subset F$ such that no two elements ...
1
vote
1answer
245 views

Lower bound for the complexity of linear programming

Since it is known that you can sort $n$ numbers by solving a certain kind of linear program - doesn't this imply a lower bound on the complexity of solving linear programs in general via the lower ...
4
votes
5answers
575 views

good resources for getting started with algorithms

I am reasonably mathematically competent and use algorithms regularly in computing, however I have started reading through 'introduction to algorithms' but find I need to understand a few more basics ...
2
votes
1answer
307 views

Exhaustively generating irreducible polynomials over a Galois field

I'm working on generating de Bruijn sequences using a non-binary LFSR (as described in [1]). One problem I'm running into is finding all irreducible polynomials which can be then used to parametrise ...
0
votes
2answers
1k views

Specific fitness function for genetic algorithm

I have a program that assign students to different courses using a genetic algorithm. To get the best assignation I have a fitness function that evaluates the distribution of the students and their ...
2
votes
0answers
475 views

algorithm for the intersections of a line and an ellipse in 2D

I am looking for an algorithm for finding the intersection of a line and an ellipse. I have the line in the form $ax+by+c=0 \qquad(1)$ and the ellipse in the form $Ax^2+Bxy+Cy^2+Dx+Ey+F=0 ...
4
votes
6answers
465 views

Applications of algebra to algorithms

Can you give examples of algorithms possessing the following two properties: 1. Solving a non-algebraic problem. 2. Relying on results in algebra. For example, the paper ...
1
vote
5answers
353 views

“Plotting” an equation

I have an equation like $$ (x - a)^2 + (y - b)^2 = r^2 $$ that represents a circle. I need to "plot" it very basically with a programming language. Computer graphics coordinate generally use the ...
2
votes
1answer
641 views

Ordering of multiplication table

this is my first post and I hope its succinct and relevant enough to post here. I'm working on finding the largest number in a multiplication table (n by n) that satisfies a certain property. In ...
7
votes
1answer
203 views

How to study results of Diophantine equation?

I finally managed to learn a bit of number theory and Diophantine equation(with the help of Arturo Magidin's great answer in what type of math is this?). But I'm wondering what's the next step after? ...
3
votes
2answers
183 views

Convex hull for convex polygons

Is there something tricky about that? Or I should use some of the standard convex hull algorithms ? I mean, I don't see anything different between creating convex hull for a set of points and creating ...
2
votes
0answers
1k views

QR with column pivoting

Golub and van Loan's algorithm 5.4.1 for QR factorization is suitable as a rank revealing algorithm. The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
2
votes
2answers
202 views

Deciding whether a given number is a totient or nontotient

The following algorithm decides if a number $n>0$ is a totient or a nontotient: ...
2
votes
1answer
311 views

how to fit a plane through a set of 3D lines

I know how to fit a 2D line through a set of points but how can I fit a plane through a set of lines? My lines are almost intersecting at a 3D point. I am interested in suggestions for an a ...
9
votes
1answer
459 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 ...
6
votes
2answers
1k views

How/why does this noise function work?

How/why does this noise function work? ...
0
votes
2answers
47 views

What are the algorithms to calculate shortest routes in a bi-direction graphic?

If I have a graphic $A\rightarrow B$ weight $10$ $B\rightarrow A\qquad 11$ $B\rightarrow C\qquad 20$ $C\rightarrow D\qquad 5$ $D\rightarrow C\qquad 16$ $D\rightarrow B\qquad 9$ $D\rightarrow ...