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)

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
18 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
42 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
11 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
22 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
15 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
33 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
33 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
114 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
69 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
votes
0answers
154 views

need mathematical expression for the below [on hold]

Want to convert below algorithm into a mathematical model:- General points 1. Let there be a Connected Directed Graph. G = (V, E) V vertices or nodes E edges. This graph can be seen as a network ...
1
vote
1answer
36 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) ...
0
votes
0answers
21 views

Graphs and MST proof [closed]

Given a graph $G$ with the set $S$ which the distance between each vertices is $w_i$. Now we add $k$ vertices to $G$. Is it possible that $W\{MST(s+k)\} < W\{MST(s)\}$? $W$ is the sum of edges ...
3
votes
0answers
60 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
52 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 ...
-2
votes
0answers
81 views

C++: Finding roots of a polynomial ring.

I need a library (can be used in C++) that finds the roots of polynomial over $\mathbb{Z}_p$ where $p$ is a large prime number. So I can give it an array of coefficients that are big integers in the ...
1
vote
1answer
37 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
31 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
26 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
65 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
29 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
56 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
46 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 ...
2
votes
2answers
42 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
20 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
29 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
53 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
67 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
82 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
28 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
316 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
115 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
34 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 ...
-1
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
25 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
21 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
0answers
63 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
15 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
24 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 ...
2
votes
1answer
42 views

Puzzle: Determining the structure of a bipartite graph

Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway. Each switch on one end of the hallway has ...
0
votes
1answer
66 views

Is there an O(1) operation to find the Nth digit of Pi?

I'm afraid that 10 minutes of googling isn't finding references to a paper that I thought existed. I remember seeing some years ago a reference to a paper that claims to have proven an algorithm that ...
-1
votes
1answer
44 views

Calculating distance between two squares of a board

Given an $n\times n$ board, for example a chess board 8x8, with the squares ordered in a Little-Endian Rank-File Mapping. Is there a direct way to calculate the distance between two squares using ...
2
votes
0answers
15 views

Accelerated Gradient Descent V.S Nonlinear Conjugate Gradient Descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has ...