Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
2
votes
1answer
45 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
86 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
1answer
35 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
39 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
69 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 ...
1
vote
1answer
117 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
121 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
26 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 ...
0
votes
0answers
22 views
Time complexity 2-opt method
I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method.
I can see that the complexity per iteration is in O(n^2) ...
2
votes
0answers
121 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
130 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
35 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
37 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 ...
3
votes
0answers
125 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
27 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?
0
votes
0answers
22 views
Given an X and a Y, how to find the equation
I've just been curious lately. If you have an X for lets say 0-50 and corresponding Y values, is there a way to determine the equation without just guessing and checking and trying to find a pattern?
2
votes
2answers
95 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 ...
1
vote
2answers
108 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.
4
votes
2answers
286 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
169 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
46 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 ...
3
votes
2answers
163 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. ...
0
votes
0answers
45 views
Find a path in directed acyclic weighted graph with constraints
Consider a directed graph with n nodes and m edges with weights that represent the distant between the nodes. There is a start node s and an end node e. We want to find the path from s to e that has ...
1
vote
1answer
37 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 ...
0
votes
0answers
26 views
Wrap Using Delaunay triangulation in 2D
I want to create a Wrap using the mesh created by Delaunay triangulation [Ruperts Algorithms] ? Example By Pinning few Points and by moving others.Can you suggest Algorithms/Papers/Books Related to ...
4
votes
3answers
91 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
50 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 ...
0
votes
0answers
113 views
Multivariable optimization Algorithm using Matlab
i am working on Multivariable OPTIMIZATION PROBLEM, where i have to optimize 5 impedance variables i.e. Z1,Z2,Z3,Z4 and Z5 (where range of all impedance lies 50 to 150 ohms).
for eg. my proposed ...
0
votes
0answers
5 views
Move a source polyline to a reference polyline (completely or partially)
We have some source lines (with low precision) need to be moved reference lines (with high precision). Following pictures gives the example for normal use cases. The red one is a source line and the ...
0
votes
0answers
38 views
Potential function in amortized analysis
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
2
votes
1answer
59 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
19 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
91 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
48 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
43 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
34 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
0answers
62 views
Tournament of the cakes
Funny programming problem that I can't solve since a couple of days. I would be very grateful for help:
There is a tournament of $n\le 50000$ cakes. $i$-th cake is described by three numbers ...
0
votes
1answer
65 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
61 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 ...
0
votes
0answers
19 views
SLP solution algoritm to implement/use in Java
Starting from the vector $\mathbf{s}_0$, determine $\mathbf{s}$, the solution of:
$$
\left\{\begin{array}[ll]
\text{min} & \nabla f(\mathbf{x})^\mathrm{T} \mathbf{s} \\
\text{s.t.} & ...
2
votes
2answers
64 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 ...
4
votes
1answer
119 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
72 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 ...
0
votes
0answers
27 views
At most O(nk) inversions question
I am working through some intro algorithms problems on my own, and do not understand the explanation to problem 2-2b, lemma 8, pg. 7-8, of why the possible range of elements which can be inverted with ...
4
votes
3answers
69 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:
$$
...
0
votes
1answer
36 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}$ ...
1
vote
3answers
50 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
68 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 ...
9
votes
1answer
123 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 ...
2
votes
0answers
198 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 ...
