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
1answer
73 views

Minimum moves to make all coins have Heads facing up

Given a circular list of coins with Tails facing up. In each move, if we flip coin at position $i$, coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: $H H H T T$ : if I flip ...
4
votes
2answers
210 views

Finding a recurrence for a sum

I am trying to implement the following sum using a programming language: $$\sum_{i=1}^N a^i i^r$$ where $N$, $a$ and $r$ are integers. The problem is, I cannot find a suitable way to do this. ...
1
vote
0answers
25 views

Show that splitting an edge in a flow network yields an equivalent network.

Need help with this question from my Intro to Algorithms book: Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge ...
0
votes
0answers
20 views

Minimum spanning tree of this graph

I'm trying to find a minimum spanning tree for this graph below using Krusal's and Prim's algorithm. This is what I got for each algorithm: Krusal: visited= ...
3
votes
0answers
63 views

Find a real number with even digits in a given base

A real number x ∈ (0,1) is called b-good if x converted to any base b >= 2 has all digits ...
2
votes
0answers
41 views

Dishwasher Unloading: Optimal Algorithm

Suppose you are unloading cutlery from a dishwasher containing $4$ types of cutlery: teaspoons, tablespoons, knives and forks. Each type has 8 pieces. You hang the cutlery on a rack with two sides. ...
5
votes
0answers
135 views

Apartness of reals and algorithm exctraction

I am trying to wrap my head around the notion of apartness in constructive mathematics and it turns out I lack understanding miserably. I would like to use as elementary notions as possible, in the ...
2
votes
1answer
24 views

find least multiple formed only of 1's of given number

The problem states that given a number find the least multiple formed only of 1's. If no such number exists then 0 will be the answer. For example for: ...
2
votes
2answers
18 views

Distance in a periodic system

I have two random points in a 3D unit cell and I want to write a computer program that calculates their distance. The system is periodic in all directions in the sense that a point in the unit cell is ...
0
votes
1answer
31 views

Prove that the following program terminates

I have tried searching for the following proof but couldn't find any result. The question is to prove that the following program will terminate when its input x is a positive integer. ...
0
votes
0answers
18 views

Algorithmic question about algebraic varieties and affinely independence

Let $f \in \mathbb{R}[x_1,\ldots,x_d]$ be a polynomial in $d$ variables. Then we can write $f$ as $$ f = \sum_{i=0}^m f_i x_1^i $$ where $f_i \in \mathbb{R}[x_2, \ldots, x_d]$. We may assume $m \neq ...
0
votes
1answer
35 views

How to determine the optimal waiting time?

You are working at a theme park ride and your job is to clip the tickets of guests as they get on the ride. There are some restrictions: Only one ticket can be clipped at a time. The average clipped ...
0
votes
0answers
19 views

What is the best time complexity for this case?

I only want to know if the following system has any integer solution or not. Actually, I do not need to know the solution(s), and only need to know the answer of question "Does the system have any ...
0
votes
1answer
61 views

Appropriate Graph Theory Concepts

I am working in a different domain and I have very basic information about the graph theory concepts. Trying to map my problem into graph theory and looking for the concepts and algorithms applicable ...
2
votes
2answers
68 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
0
votes
0answers
65 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
49 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
48 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
13 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
28 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
42 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
71 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
45 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
42 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
73 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 ...