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)

0
votes
0answers
64 views

Are there exact methods to solve the Path cover in bipartite graphs?

We consider a simple graph $G =(V; E)$. The well known Path Cover problem is NP-complete on all graph classes on which the Hamiltonian path problem is NP-complete, including planar graphs, bipartite ...
0
votes
0answers
48 views

Simple curve fitting smoothing algorithm

Is there any conditionally simple algorithm to obtain a best fit (equation) for points set? I have a few points for which I want to have a "smooth" function is constructed that approximately fits the ...
1
vote
2answers
25 views

Robust matching of values to a uniform sequence

I have a sequence of $N$ real numbers $X_i$ that are deemed to be equally spaced. $N$ is small (say $10$ to $20$). Two problems can arise: the spacing isn't perfectly uniform, it can vary in a ...
1
vote
2answers
34 views

Optimal step for drawing Bezier curve

Bezier curves are parametric in the sense that for each dimension their polynomials share common parameter $t$ [1]. To draw a Bezier curve on screen one could increment $t$ by tiny step and calculate ...
0
votes
2answers
29 views

Need help figuring out substitution with recurrence equation. [duplicate]

I need help with an Algorithm text book problem. The problem is the following T(n) = 2T(n/2) + n We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an ...
1
vote
1answer
29 views

Shortest path in a hypercube graph

A* algorithm is one of the algorithm which produces a shortest path in a given graph. I am interested in knowing, is there any property of d-dimensional hypercube which allows the parallel computing ...
0
votes
0answers
24 views

Is there a solution/algorithm for a one-directional stable marriage problem?

I'm working on an application to assign summer camp kids to activities. The program input is a list of campers, and a ranked list of each camper's preferred activities. For example, Alice might rank ...
1
vote
1answer
30 views

Shuffling the columns of a matrix

Suppose I have an $N\times k$ matrix: $$\begin{bmatrix}a_{1,1} & \cdots & a_{N,1} \\ \vdots & \ddots & \vdots \\ a_{1,k} & \cdots & a_{N,k} \end{bmatrix}$$ Is there a ...
0
votes
1answer
21 views

Average score for a Quiz based on recent performance

A quiz always has 10 questions. Correct answer results in 1 mark. No negative marking. A user can take the quiz as many times as he likes. I want to show his 'Average Score' based on last 5 quiz ...
0
votes
0answers
44 views

Substitution method for solving recurrences

I am new to math.stackexchange and I need help understanding Substitution method for solving recurrence. This is the original problem T(n) = 2T(⌊n/2⌋) + n Our guess is T (n) = O(n lg n) so we need ...
0
votes
0answers
12 views

Is this a Combinatorial Optimization problem with Multiple Constraint Satisfaction?

Given n-dimensional data consisting of over 20000 samples with 200 dimensions, using this as an example: ...
0
votes
0answers
26 views

Efficient method to compute grand sum of a Vandermonde matrix?

Is there a computationally efficient method to calculate the sum of all elements (grand sum) of a Vandermonde matrix? Each row can be quickly calculated using the formula for a geometric progression. ...
0
votes
1answer
16 views

Normalizing data collected over varying time slots

First, it's been a while since I have done any 'maths'. I have data collected from sensors over possibly varying timeslots (Only one sensor can collect at a time). I am attempting an algorithm that ...
2
votes
1answer
40 views

Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.

Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$. ...
0
votes
1answer
34 views

Is there an algorithm to generate these specific sequences of numbers?

f(1) = [1] f(2) = [2,1,1] f(3) = [3,2,1,1,2,1,1] f(4) = [4,3,2,1,1,2,1,1,3,2,1,1,2,1,1] ... f(n) = ... The lengths of the lists f(n) are $2^n - 1$ (Mersenne ...
9
votes
1answer
120 views

Non-computable function having computable values on a dense set of computable arguments

A rational complex number is a complex number whose both real and imaginary parts are rational numbers. Note that a rational complex number is a finitary object that can be an input or an output of an ...
1
vote
2answers
72 views

Algorithm for finding graph levels

I have found an algorithm to separate a graph in its different levels, but as I don't know its name, and I couldn't find it anywhere else I don't trust it 100%. It goes like this: ...
1
vote
1answer
39 views

Find the number of vertices that belong to all the maximum matchings of a general connected graph .

The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well. An O(VE) ...
3
votes
0answers
74 views

Is Risch algorithm learnable by a human being?

I've discovered a few months ago about the Risch's algorithm. It seems to be the best thing we have to find antiderivatives. Some days ago, I've found lectures on the integration of elementary ...
0
votes
0answers
56 views

How to calculate relation between Beats (as in BPM) and variance of the energies?

I'm working on an implementation of a Beat Detection algorithm and I can't find a relation between the statistical variance of the energies in 1 second of audio decoded as PCM and the threshold value ...
4
votes
1answer
21 views

Number of ways to choose rows with inclusion condition

I have a large collection of lists consisting of 1's and 0's, each list the same length. I call each list a row. I want to know the number of ways to select rows such that their cumulative OR results ...
1
vote
1answer
39 views

how to calculate the number of less comparisons in this algorithm

I have this algorithm The teacher asked us what is the number of the less that compare : He said that the number is: I am trying to find out how did he know that, I did this 1- The ...
3
votes
0answers
33 views

How to generate a function with multiple variables to fit experimental data?

I am researching methods to increase the accuracy of an algorithm that is currently used to analyse radiation patterns as they hit our sensor. (For the non-physicists, we will mainly see Alphas, ...
1
vote
2answers
27 views

Prove that the number of edges is a multiple of 3 if each vertex has a degree that is either a multiple of 6 or 9

So if G is an undirected graph where the degree of each vertex is a multiple of 6 or 9 i have to show that the number of edges is a multiple of 3. where I am having trouble, I said that if the ...
1
vote
1answer
70 views

How to find the least number with maximum trailing zeroes when multplying with numbers containing 4 or 7 only!

Example: 15 -> 15*4=60 - minimum number with max trailing zeros 125 -> 125*4*4=2000 400 -> 400 will be the answer as its the minimum number with max trailing zeros. Can you think of any other ...
0
votes
1answer
30 views

Gradient descent with linear perturbation

Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient ...
0
votes
0answers
46 views

Meaning of equation about maximization of the correspondence score between two collections

I am trying to interpret the following: $x$ is an indicator vector such that $x(a) = 1$ if candidate assignment a represents a corresponding pair of nodes and $0$ otherwise. We aim to find an ...
3
votes
2answers
58 views

Showing $\lg(n!) = \Omega(n\lg n)$

I saw this equation in "Introduction to Algorithm" 3th edition in page 58 : $$\lg(n!) = \Theta(n\lg(n))$$ If $\lg(n!) = \Omega(n\lg(n))$ and $\lg(n!) = O(n\lg(n))$ then we can prove that. I can ...
0
votes
1answer
20 views

What is the largest number of people that can attend a meeting at one time?

From a given list of ranges, what is the fastest algorithm to find the largest number of ranges that overlap at a single point (or range). For example, given a list of times a group of people are ...
3
votes
1answer
59 views

Dependency of submatrix used in a combinatorial strategy .

This is a verification post , Please inform if anything is undefined or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment. Introduction: Given a matrix A ...
3
votes
2answers
44 views

Variation of Division Algorithm

How to derive this version of the division algorithm . For integers a, b with b ≠ 0 there exist unique integers q and r that satisfy a = qb + r, where -1/2|b| < r ≤ 1/2 b. I started off with ...
1
vote
0answers
21 views

FFT procedure for evaluationg a polynomial at $N$ Fourier points

The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. Algorithm (FFT - fast Fourier transform). Input arguments. $ \ ...
0
votes
2answers
41 views

Reversing Rotation + XOR

I have this cypher which is as follows : Take 2 numbers : A=1011 and B=1010 if the ith bit of X is 1 then shift Y* i times to the left. So in the end you will get ...
5
votes
1answer
70 views

An algorithm for filling a moving truck

I was recently helping a friend move. I stood in the moving truck as other people brought boxes and furniture pieces from inside the house. My job was to arrange these items in an efficient way inside ...
0
votes
1answer
35 views

How do I find if a series of integers is (somehow) regular

[DISCLAMIER]: please be patient and low profile: no math background here :) I have a database of transactions, i.e. a list of purchases made by different customers. What I have to figure out is ...
2
votes
1answer
73 views

Calculation of product of all coprimes of number less than itself

Is there any fast way or formula to calculate product of all coprimes of a number less than itself? How can we do it without finding all coprimes manually? Note : I have to find actually (product) ...
4
votes
1answer
84 views

Algorithm to find shortest path to net values across nodes

I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$ Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
0
votes
1answer
76 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
1
vote
2answers
34 views

A graph with $V$ vertices has at most $V(V-1)/2$ Edges

I am reading about graph theory. A graph with $V$ vertices has at most $V(V-1)/2$ Edges Proof: The total of $V^2$ possible pairs of vertices include $V$ self-loops and accounts twice for each edge ...
0
votes
0answers
31 views

Efficient Test For Commuting Matrices

I know that if $A$ and $B$ are two Hermitian matrices, then $A B= B A$ if and only if their eigenspaces coincide [1]. In order to apply this test one need to compute eigenvectors of both $A$ and $B$ ...
4
votes
1answer
330 views

Expected value when die is rolled $N$ times

Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
0
votes
2answers
190 views

To fast invert a real symmetric positive definite matrix that is almost similar to Toeplitz

It is well known how to solve a Toeplitz system Ax = b, of a matrix A, n x n elements, ...
0
votes
0answers
39 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
0
votes
0answers
18 views

Average operations on a hashtable

Suppose we are given an empty hash table of size $n$, where collisions are resolved by re-hashing (open addressing). Next, $n/2$ items are randomly inserted into the table using a hash function that ...
0
votes
1answer
26 views

Show that running time of Quick Sort is $\mathcal O(n^2)$ when array contains distinct elements and is sorted in descending order

I'm trying to study running time for various algorithms. Now I have QuickSort. How exactly is the running time of an algorithm calculated, I know how quick sort works and the Asymptontic notations. I ...
0
votes
1answer
23 views

Target coordinates given estimate distance from multiple points

I have a device that emits a probe signal, let it be called X. The location of the device is unknown. I have multiple readings of the probe signal in different GPS coordinates spread over an area , ...
0
votes
0answers
15 views

How to compute whether an almost homomorphism is positive or negative when it isn't 0?

A function $f:\mathbb Z \to \mathbb Z$ is almost a homomorphism if there is a $C \in \mathbb N$ (called the additive constant) such that for all $x, y \in \mathbb Z$ $$f(x+y)-(f(x)+f(y)) \le C$$ For ...
0
votes
1answer
94 views

Is there a general solution to the water-bucket logic problem?

Having an infinite supply of water and two containers, one for 3 liters and one for 5 liters, how would you measure 4 liters? Each step in the solution can be one of three things: Fill up a container ...
0
votes
0answers
19 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
3
votes
0answers
27 views

Need to calculate number of valid domain names between two other domain names

A domain name can be 2 to 32 characters in length. The first character can be the characters 'a' through 'z' The last character can be the characters 'a' through 'z' or '0' through '9' The ...