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)

8
votes
2answers
630 views

Do irrational number contain infinite/every patterns of sequences?

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
3
votes
2answers
625 views

What does it mean to “have a multiplicative inverse of modulo 10!”?

Here's the question: What's the smallest integer > 1 that has a multiplicative inverse modulo 10! (that is, 10 factorial)? What does that mean? I understand that: We say that x is the ...
1
vote
2answers
3k views

What does it mean for a function to be polynomially bounded

There is a definition in my notes and says, When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in ...
1
vote
0answers
210 views

Non overlapping areas algorithm

One of my fellow members on stackoverflow has posted a question thread which concerns how to write a mathematical equation to calculate the exposed areas of a window from a group of windows (like on ...
2
votes
1answer
94 views

How can I prove big-oh relation between $\log_2(\log_2 n)$ and $\sqrt{\log_2 n}$

How can I prove big-O relation between $f=\log_2(\log_2 n)$ and $g=\sqrt{\log_2 n}\,$? I want to find the constants, $c, N$ such that $\ g(x) \leq cf(x)$ for all $x>N$.
3
votes
2answers
617 views

Linear equation system in modular aritmetic

Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe. $$4x_1 - ...
1
vote
2answers
85 views

How to identify the slowest prime number in Sieve of Eratosthenes Algorithm

how can one find the slowest prime number to be identified by using the using Sieve of Eratosthenes Algorithm? Is there a formula to finding this number? or an explanation how this could be found? ...
1
vote
1answer
57 views

Balancing two sets while items in one are unmovable

I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference ...
3
votes
1answer
96 views

Checking condition for all roots of polynomial

A couple of months ago I found this problem, and I think I will never find theory which will help me solving it, on my own, so I'm asking for a help. It's very interesting, I think: For a given ...
2
votes
1answer
2k views

Recursive Inverse Fast Fourier Transform (FFT)

Given a polynomial $A$ in point-value form consisting of the 4 points $(1,5)$, $(i, -1-2i)$, $(-1, -7)$ and $(-i,3-2i)$. Using the recursive inverse FFT algorithm to interpolate, I want to find the ...
0
votes
4answers
614 views

Solving recurrence relations (change variable etc.) problems

I have been given $$f(1) = 3\\ f(2) = 8\\ f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$ How would I go about solving this? I've tried working so hard to get this to no avail. If someone can ...
0
votes
1answer
42 views

algorithm to minimise pairwise product sqaureroot

Suppose I have an array of elements A[n]. I wish to minimize the square root of pairwise product expression sqrt(m1*m2) , where <...
10
votes
3answers
1k views

Is The Clique Algorithm by Ashay Dharwadker correct?

When you write "clique algorithm" in Google www.dharwadker.org/clique/ appears as a 2nd result. Citation from abstract: We present a new polynomial-time algorithm for finding maximal cliques in ...
2
votes
3answers
233 views

How can {→,⊕} be complete when {¬,⊕} isn't?

Please provide an example with {→,⊕} that can't be realized with {¬,⊕}. I can't think of what I can't realize with {¬,⊕}. I have a simple model where I think the bottom is more like YES ⊕ NO (and ...
1
vote
1answer
71 views

Finding optimal recipe proportions

Is there a mathematical optimisation technique or algorithm that could, at least in principle, be applied to find optimal ingredient proportions for a given recipe using a minimal number of ...
0
votes
1answer
53 views

Prove the following “connected” problem

There are $n$ people in the room, some know each other and some don't. If $i$ knows $j$, then $j$ knows $i$. Suppose that for every four different people there exists one who knows the remaining three....
3
votes
0answers
1k views

Two closest points in Manhattan distance

I'm wondering about Manhattan distance. It is very specific, and (I don't know if it's a good word) simple. For example when we are given a set of $n$ points in this metric, then it is very easy to ...
0
votes
1answer
89 views

Block diagonalization of a symmetric square boolean matrix

I have a symmetric square matrix with elements from $\{0,1\}$. How can I block diagonalize it only swapping lines and columns or detect it's not possible?
2
votes
2answers
118 views

Is it true that $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$? [closed]

Is $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$ true? I found it's true but I don't know what to use it for besides refactoring. How interesting is the statement A→B if not ...
2
votes
2answers
603 views

Regular Languages Algorithm?

I need help proving the following question: Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length. So far, I know ...
1
vote
2answers
513 views

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out :( There are T(0) = d and T(1) = e, Thanks in advance.
5
votes
3answers
2k views

programming brain teaser

Given a programming language where you could make as many variables up as possible and you could only perform these three operators find b-1. ...
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?
1
vote
0answers
735 views

Complexity of SVD

I am working with $SVD$. Here they noted that, it's complexity is $O(n^3)$. I know that we need to find three matrices $ U,V,S $. i.e., If A is a matrix of order $m*n$ then $svd $ of A is $A=U_{m*m}...
10
votes
4answers
15k views

Difference between formula and algorithm

What is the difference between the terms formula and algorithm in mathematics? I haven't seen the definition of formula anywhere. I know that algorithm means that Turing machine halts for every input. ...
1
vote
1answer
88 views

Calculating a minimum connected subgraph containing a fixed set.

Let $(V,E)$ be a connected, planar graph, and let $S \subset V$ be some desired set of vertices. What is the fastest algorithm, if it exists, to calculate a connected subgraph of $(V,E)$ which ...
4
votes
4answers
455 views

Algorithm to partition sum between buckets in all unique ways

The Problem I need an algorithm that does this: Find all the unique ways to partition a given sum across 'buckets' not caring about order I hope I was clear reasonably coherent in expressing ...
4
votes
1answer
67 views

Game in switching bits

I found an interesting problem: We are given $n$ bits in a row, some of them are equal to $1$, and some of them are equal to $0$. This is our starting combination. And we are also given the ending ...
3
votes
2answers
230 views

Checking Sudoku - sufficient sums

Are the following condition sufficient for checking if solution of Sudoku with (extended output) is valide : sum of values in each row, column and subsquare is equal to 45 and sum of squares of ...
1
vote
0answers
34 views

Algorithm for approaching zero delta.

I'm working on translating an old program for a gas-mixing furnace, and I have a logic problem that I believe I need help on the math with. I have the specimen temperature ($T$), a variable called ...
2
votes
1answer
2k views

How to calculate $ 1^k+2^k+3^k+\cdots+N^k $ with given values of $N$ and $k$? [duplicate]

Here $ 1<N<10^9$ and $0<k<50$ So we have to calculate it in order of $O(\log N)$.
8
votes
2answers
59 views

Having $A_1=a+b+c$,$A_2=a^2+b^2+c^2$, $A_3=a^3+b^3+c^3$ - how to get $a,b,c$?

Perhaps I'm just a bit dense at the moment - I've re-read some of my notes from monthes ago concerning elementary symmetric polynomials, and I find that I've no idea how to approach the "inverse" ...
4
votes
2answers
52 views

Graph with words on edges

I'm practising solving programming problems. Here I have some problems: We are given a directed graph $G$ with $n\le 100$ nodes and $m\le 1000$ edges, which edges are labelled (labels are also ...
1
vote
0answers
79 views

Statistical significance test in polygaussian fitting, using Levenberg-Marquardt

I have a set of dihedral angle values that I have fitted using a polygaussian function via the Levenberg-Marquardt algorithm http://en.wikipedia.org/wiki/Levenberg-Marquardt. Specifically, the ...
0
votes
1answer
206 views

Properly matched parentheses with restrictions

I'm practicing solving programming problems, and I can't manage with this one since a week: For a given $n\le2000$ and sequences $L,R$ with values in $\left\{1,2,...,2n \right\}$ count the number ...
5
votes
1answer
284 views

finite field to rational fraction

Suppose I have a number $n\in\mathbb F_p$, i.e. an element of the finite field obtained by arithmetic modulo some (odd) prime $p$. I'm looking for a way to find a simple description of $n$ as a ...
2
votes
2answers
86 views

Expected number of 1s for a random integer

For an integer $K$ randomly chosen from $0,1,...,N$. What is the expected number of ones in $K$'s binary representation? A special case of the problem is when $N=2^k - 1$, in which the expected ...
5
votes
2answers
566 views

Is there a branch of math studying music algorithms?

I have found 2-3 search engines for scientific studies, things like algorithms, thesis, piece of researches and stuff like that; I'm really surprised to see a lot of applications for the math ...
0
votes
1answer
201 views

Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$ To solve this and find a Θ bound, i tried the following: I ...
5
votes
3answers
191 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $$ T(n) = 2T(n/2) + \log_2 n. $$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: $$ T(...
0
votes
1answer
51 views

Probability of getting distinct numbers out of two differently distributed variables.

Assume you have $X$ and $Y$. They both take the same values, but they have different distributions, for example: $X$, $Y$ can be: $\{1,2,3\}$ $X$ has probabilities: $\{\frac{2}{7}$ ,$\frac{2}{7}$,$\...
1
vote
3answers
108 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
1
vote
3answers
230 views

Help with Big O and Big Omega problem.

this is a homework problem: 1) $$ \text{Let }f(n) = n^2+5000 \text{ and } g(n) = 5(n^2) + 100.\text{ Prove formally that }f(n) = \theta (g(n)) $$ My attempt: a)Prove f(n) is $ O(g(n)) $: When $ n &...
10
votes
1answer
235 views

permutation search game

Arrange the natural numbers $1$ through $n$ in a random order (the order is unknown and has a uniform distribution). Now make a sequence of guesses as to which number is in which slot, one number and ...
4
votes
0answers
355 views

Algorithm for generating homeomorphically irreducible trees of size n

In this video they talk about generating all the homeomorphically irreducible trees of size 10. I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
0
votes
1answer
70 views

What is the complexity (\Theta version) of the function $\sum = 3i^{\frac{3}{2}}$

What is the complexity ($\Theta$ version) of the function $$\sum\limits_{i=1}^n 3i^{\frac 3 2}$$ I think that it is just $\Theta(n^3)$ because the $n^3$ grows faster then the constant or the square ...
7
votes
5answers
232 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
3
votes
1answer
100 views

Placing cards in an arc (by using $x ^ 2$)

In a card game I have currently the hand at the bottom placed in an ugly linear corner, but actually would like to change that to an arc: Unfortunately my math skills are very rusty now (at the age ...
1
vote
2answers
975 views

Maximum weight-matching in a tree

I'm practicing solving algorithm problems and can't manage with this problem: We are given a tree with $n$ vertices by the list of $n-1$ tuples: $\langle a_i, b_i, w_i\rangle$, where $a_i\neq b_i, ...
2
votes
2answers
4k views

Time complexity of a modulo operation

I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this? A ...