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
3answers
834 views

How to find a “simple” fraction between two other fractions?

If we have two fractions $a = { a_1 \over a_2} $ and $c = {c_1 \over c_2}$ with $a<c$, how to find the fraction $b = { b_1 \over b_2 }$ , $a < b < c$ for which some measure of ...
1
vote
1answer
756 views

simple calculation using logs

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n\in\mathbb{N}$, insertion sort runs in $8n^2$ steps, while merge sort runs in ...
0
votes
2answers
212 views

How do you solve this simple logarithm problem?

I'm comparing efficiencies for the famous fake-coin algorithms. Specifically, I'm looking at a two-pile approach and a three-pile approach for a solution. I have found that, like a binary search, ...
2
votes
1answer
235 views

Methods of solving a problem regarding withdrawing and depositing from a bank account.

I have an imaginary bank account with an initial balance $x$. I can only withdraw $0\% < w\% < 100\%$ (of the current balance) or deposit $0\% < d\% < 100\%$ (of the current balance) at a ...
0
votes
1answer
121 views

Ranking System :S

My math experiences I had at school are not very advanced and I'm struggling with a calculation right now... I'm programming an image Search script for my company where you can find all pictures we ...
10
votes
3answers
7k views

Get Transformation Matrix from Points

I have built a little C# application that allows visualization of perpective transformations with a matrix, in 2D XYW space. Now I would like to be able to calculate the matrix from the four corners ...
4
votes
3answers
752 views

Heronian triangle Generator

I'm trouble shooting my code I wrote to generate all Heronian Triangles (triangle with integer sides and integer area). I'm using the following algorithm $$a=n(m^{2}+k^{2})$$ $$b=m(n^{2}+k^{2})$$ ...
1
vote
2answers
192 views

Algorithm to generate a fraction of winners based on a maximum number of players

I have some sort of a math issue : I have to implement an algorithm that randomly generates winners and losers based on : a maximum number of players a percentage of winners to reach Of course, ...
1
vote
2answers
688 views

Solution of Diophantine equation for polynomials

I'm trying to solve this polynomial Diophantine equation for $R$ and $S$: $ AR + BS = G $ where $A(x) = a_0x^{n_a} + a_1x^{n_a-1} + a_2x^{n_a-2} + ... + a_{n_a}$ $B(x) = b_0x^{n_b} + b_1x^{n_b-1} + ...
2
votes
1answer
94 views

determine the max flow function $f^*$ in a network given the maximum flow value

Suppose I have a Network N ( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out) ...
3
votes
1answer
313 views

Partitioning Points Into Regions

I have a list of points $p_1, p_2, ..., p_n$ in the plane where each point has a weight $w(p)$ and I want to partition the points into $k$ separate regions with the following constraints: The convex ...
0
votes
2answers
1k views

Pretty simple question about running time

What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
1
vote
1answer
1k views

Partitioning a set of integers into 4 subsets with equal subset sums

Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other. I am interested in ...
0
votes
1answer
108 views

How to find co-ordinates of a point from four points that can translate or rotate? All these points form a rigid body.

I have a rigid body that translates and/or rotates about an axis perpendicular to the screen. I have co-ordinates of four points on the rigid body. How can I get the co-ordinates of a unknown point on ...
1
vote
1answer
328 views

greedy algorithm on set cover

If I'm covering the interval [0,1] with sets which are themselves closed intervals, is there a covering where the greedy algorithm does not find the optimal solution? If the sets are not individual ...
2
votes
1answer
472 views

Find a maximum of difference without sorting.

Suppose that I have an unsorted array of real numbers $\{a_i\}_{i=1}^n$. We sorted it in ascending order and now we have array $\{b_i\}_{i=1}^n$. Let $N=\max\limits_{i=\overline{1..n-1}} ...
1
vote
4answers
3k views

Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N?

I need to write a program in C++ that finds all primes up to 2^32. I used a Sieve of Eratosthenes with multiple threads, but it only worked well up to about 10 million. After that it just takes too ...
1
vote
0answers
130 views

Trying to create an algorithm that takes into account multiple variables

I've hit a road block on how I can put what I have into a calculation that works. Simply I am trying to work out the "value" of each company that we have on my companies books. The information I want ...
5
votes
1answer
1k views

Min cut Max flow - Finding the cut with least vertices

Suppose a network $N = (G,c,s,t)$ where $c$ is real. How do you find all min-cuts? (or how do you find the cut with the least number of vertices) I've tried messing with the capacity, but since it ...
1
vote
1answer
143 views

Solving $ xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y)$ given $a,b,c$

Given $a$, $b$, and $c$, find the number of pairs of positive integers $(x, y)$ satisfying this equation: $$ xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y).$$ If $a=2, b= 1, c= 1$, then ...
0
votes
2answers
265 views

What's the fastest way to get an exact value for integrate a power of a polynomial?

Suppose we have two integers $a$ and $b$, and a polynomial in $x$, $p(x)$. What's the fastest way to get an exact value for $\int_a^b{(p(x))^n dx}$, with $n$ large? This is a more complicated ...
2
votes
3answers
953 views

How can I solve $8n^2 = 64n\,\log_2(n)$

I currently try to analyze the runtime behaviour of several algorithms. However, I want to know for which integral values $n$ the first algorithm is better ($f(n)$ is smaller) and for which the second ...
3
votes
2answers
126 views

No identical rectangles in a matrix

I have a matrix of dimensions N x M. Every cell has an integer. Now, I want for every 'rectangle', to verify that all its corners are not the same. Example: This matrix is fine: This matrix is not: ...
2
votes
2answers
104 views

Numbers which encode other numbers infinite times.

Let $g(x,n)$ be a function which chops off the first n digits of the binary decimal expansion of x. eg $g(0.1010111,2)=0.10111$ Is there a function $f(x)$ from the reals to the reals, such that for ...
7
votes
1answer
617 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
0
votes
1answer
648 views

What's the big $O$ for this summation?

What would the big $O$ (worst-case runtime complexity; I think it's big $O$?) be for an algorithm that takes this long? I generalized the run time with the summation and put it in wolfram alpha. ...
3
votes
1answer
5k views

Can QR decomposition be used for matrix inversion?

Is there any simple algorithm for matrix inversion (that can be implemented using C/C++)? Can QR decomposition be used for matrix inversion? How?
4
votes
1answer
174 views

How to find out if two solutions are equivalent or different?

Given 5 different numbers ($\in \mathbb N$) in a specific brackets pattern like: $$\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / x_5 = \text{result}$$ Only the brackets are ...
3
votes
4answers
2k views

Recurrence - Master Theorem - Asymptotic Question

Sorry if this question has been asked before, but I am trying to figure this out. I am using the CLRS text, Introduction to Algorithms. In the Recurrences chapter, in the Master Theorem section, the ...
0
votes
1answer
98 views

Different solutions under distributive and commutative equivalence

Given 5 numbers: $x_1, x_2, x_3, x_4, x_5 \in \mathbb N$ all the 4 operations: $+ - \times /$ a specific brackets pattern: $\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / ...
5
votes
2answers
102 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
-2
votes
3answers
175 views

Algorithm for counting [closed]

I want to count from 0 to n. And when I have reached n, adding 1 to n would give me 0 again. For example: 0, 1, 2, 3, 4, 0, 1, 2, ... Is there such an algorithm to do this? Edit: I need an ...
3
votes
2answers
455 views

How shall I understand this simple example of No Free Lunch theorem?

I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization: My understanding is that a cost function is a ...
3
votes
1answer
117 views

Existence of a general-purpose (almost) universal optimization strategy

From Wikipedia about interpretations of no free lunch theorem A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization ...
1
vote
1answer
97 views

What does it mean for a function to be part of a set in O-notation?

I'm trying to understand the concepts underlying the O-notation. The formal definition is: $ O(g(n)) = \{ f(n) \textrm{ such that there exist positive constants }c\textrm{ and }n_{0} \textrm{ such ...
1
vote
0answers
47 views

Material On Multiplicative Weights

I am interested in Multiplicative Weights algorithm, it's randomized version of weighted majority algorithm. The idea is very simple, you have a group of experts, each expect give your advice, your ...
1
vote
1answer
101 views

To encode the shape of an ordered tree into bit sequence more efficiently

Suppose we want to save the shape of an ordered tree of n node, each node has maximal 2 children. If it is a binary tree, we must use 2n bits. Since in our situation, we don't have left or right ...
0
votes
2answers
2k views

If $f(n) \in O(g(n))$, and $g(n) \geq 2$ then $\log{f(n)} \in O(\log{g(n)})$?

I need your help in following problem Using the definition of $O$ symbolism, show that given two functions $f(n)$ and $g(n)$ that $g(n)\geq2$ is true $f(n)=Ο(g(n))$, then it would also be true that ...
1
vote
1answer
720 views

properties of the Greedy Algorithm (Graph Colouring)

So I have shown, that for all n $\in N $ there is a graph $G$ with n vertices such that the Greedy Algorithm will colour it in exactly 2 colours. Further I have shown that for a Graph with diameter ...
1
vote
1answer
1k views

Cartesian product of n sets

I'm currently writing a little application in which I would like to create all permutations of n sets. For example I have the following sets (arrays): ...
0
votes
1answer
658 views

Existence of Vertex Ordering in Greedy Algorithm to get “optimal” colouring

I am trying to prove that for any Graph there is an ordering of the vertices, sucht that the Greedy Algorithm will colour the vertices in such a way that it uses the Chromatic number of colours. I am ...
1
vote
1answer
115 views

RSA calculations

I can not find a solution to the following problem. The problem is: We have an algorithm A for a decision problem that answers yes or no and for every input it gives the right answer with ...
0
votes
3answers
846 views

Finding a perfect square

How can I find the first perfect square from the function: f(n)=An²+Bn+C? B and C are given. A,B,C and n are always integer numbers, and A is always 1. The problem is to find n. Example: A=1, B=2182, ...
3
votes
1answer
292 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
2
votes
2answers
258 views

Traditional Marriage GS female pessimality

In the context of stable matchings I am currently trying to understand the Gale-Shapely Algorithm (traditional marriage algorithm). I have proved it s correctness and I have shown that its male ...
10
votes
1answer
2k views

For what coinage systems does a greedy algorithm not work in providing change?

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins. However, for a coinage system with 12 cent coins, a greedy ...
2
votes
1answer
300 views

Algorithm to find the total resistance between 2 vertices of a graph

Assume we have a graph, and resistors are placed on the edges. I want to know if there is an algorithm that find the total resistance between any 2 vertex. i have a hard time finding any description ...
0
votes
2answers
552 views

How many different Pairs are there?

Consider, F4(y) = the number of digits 4 in decimal representation of the positive integer y and F7(y)=the number of digits '7' in decimal representation of the positive integer y. For the given ...
1
vote
1answer
100 views

Partial sums usage.

We have an array $A[1..N]$ with unknown values and a set of intervals $[L_i, R_i]$. For each interval we know sum $S_i$ of values in the array $A$ in the given range $[L_i, R_i]$. So the question is ...
4
votes
2answers
98 views

algorithm transfer one coin matrix to another coin matrix

Description: There are $mn$ ($m \leq 100$, $n \leq 100$) coins on the desktop forming an $m\times n$ coin matrix. Every coin either face upward, or face backward, represented by 0 or 1. Rules of the ...