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)

3
votes
5answers
65 views

How to prove that $\sum_{i=j}^nn-i = \sum_{i=1}^{n-j}i$?

Trying to solve question 2-3 from Skiena's Algorithm Design Manual which asks to find the runtime of the following loop: ...
1
vote
1answer
19 views

Is the set of numbers of computable functions f(x) = c recursively enumerable?

Consider the set of numbers of computable functions such that is $f(x)$ defined, $f(x) = c$ for any $x$. Is this set enumerable or co-enumerable? (Or neither). A bit of my thoughts on it. We can take ...
1
vote
0answers
19 views

Pollard Rho - DLP Algorithm Implementation

I am working with Pollard Rho Algorithm DLP. I have developed in Java and Python the way to calculate the table to find the collisions, and then using congruences and some others tricks I am getting ...
1
vote
0answers
20 views

Determine if fitted line is actually one line

I am trying to fit multiple lines through many data points in 3d space. My working method is sequential RANSAC, which now is fast enough and fits some lines, but produces some lines that don't fit one ...
0
votes
0answers
55 views

count arrays with pairwise gcd as some integer (was a previous question by other user but no answer yet) [closed]

Array must contain N elements. Each element in array must be less than given number M. Greatest common divisor of all its elements is equal to a given integer D.
1
vote
0answers
26 views

Interpolating discrete data with completely monotone analytic functions

Suppose we have a positive integer $n$ and a finite list of real numbers $\{a_1,\,a_2,\,\dots,\,a_n\}$. We want to find a real-analytic function $f:[1,n]\to\mathbb R$ such that $f(m)=a_m$ for all ...
1
vote
1answer
24 views

Showing equivalence of 2 Big O notations

I have the task to show that the following two big O definitions are equivalent. My first thought was that it has to be equivalent because the set of natural numbers excludes all broken rational ...
0
votes
2answers
53 views

Division n items into k boxes prove that it is NP-Complete

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem. We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
1
vote
1answer
26 views

Karatsuba multiplication for $x = 123 , y = 100$

Given the numbers $x = 123$ and $y = 100$ how to apply the Karatsuba algorithm to multiply these numbers ? The formula is xy=10^n(ac)+10^n/2(ad+bc)+bd As I ...
1
vote
1answer
17 views

Simultaneous equations change expression variables

I have a deceptively simple-looking problem. $$A + B = A'\\ C + D = B'\\ A + C = C'\\ B + D = D'$$ On LHS $4$ variables $A, B, C, D$ On RHS $4$ variables $A', B', C', D'$ Is it possible to ...
0
votes
0answers
29 views

How to determine a matrix when the sums of rows and columns are given

I was given a $5\times30$ matrix with each element of the matrix can only take 0 or 1. It is given that the sum of each row is 8 and the sum of the first 20 columns equals to 1 while the sum of each ...
0
votes
1answer
16 views

Binary Heap Question interpretation

In the question in the link below, how do I tell weather to draw out a binary min heap or a binary max heap? Am I misunderstanding the question? Binary Heap Question
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
0
votes
0answers
70 views

100 people standing in a circle.

I've got this problem on my Graph algorithms exam and I still can't solve it!Here is the problem: At first there are 100 people sitting at a round table and neither one is enemies with their ...
1
vote
1answer
19 views

Fourier transform form angle-valued functions

I'm trying to analyze the power spectrum of a 2D map, which is a map of the orientation of a field. Before going to discrete problem, I had difficulties finding out the Fourier transform of such kind ...
2
votes
0answers
19 views

levenshtein distance: iterative vs single calculation

I had a list of 1100 words and sought to cluster them based on a levenshtein distance of 2. This reduced the list to 900 words. Running the calculation again reduced the number to roughly 800, and ...
1
vote
1answer
30 views

Sigma notation for following nested loop

How may the following programming statement be written as summation? ...
-1
votes
4answers
77 views

How would I find the sum of this infinite series? [closed]

Any help with steps would be much appreciated. I know how to solve simpler versions of this problem but can't seem to figure this one out. Thank you! $$\sum_{n=1}^\infty \frac{2n}{5^{3n}}$$
2
votes
1answer
320 views

Count arrays with each array elements pairwise coprime

Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that : Each of the element in array, $1 ≤ A[i] ≤ M$ For each pair i, j ($1 ≤ i < j ≤ N$) $GCD(A[i], A[j]) = ...
0
votes
0answers
17 views

Convert Levenshtein Distance to percents

This is my first post here so please bare with me. I would like to ask if is possible to convert Levenshtein Distance to percents? There is similar question on StackOverflow which does have several ...
0
votes
1answer
18 views

How should t be chosen such that the running time function $\Theta(n(t+n^{1/t}))$ has a minimum rate of growth?

Question Suppose we have an algorithm whose running time is $\Theta(n(t+n^{1/t}))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen ...
13
votes
3answers
1k views

How to solve this algorithmic math olympiad problem?

So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... I was stuck with this very interesting algorithmic problem: Let $n$ be a natural ...
0
votes
0answers
54 views

Yale College's Housing Draw Problem — Convex optimization techniques on a modified stable marriage problem?

I'd like to run various optimization techniques on this variation of the stable marriage problem I formulated. Ideally, I'd be able to convert the problem I constructed into one that is more ...
0
votes
1answer
50 views

How to compute the sum of a $\frac{1}{n(n+1)}$ serie? [duplicate]

I'm solving few math puzzles to train myself for a local math contest, and I'm stuck with this problem : Compute the sum of : $$\frac{1}{2*1} + \frac{1}{2*3} + \frac{1}{3*4} + ... + ...
0
votes
0answers
28 views

Is this Feasibility problem NP-hard?

I am trying to solve a combinatorial optimization problem (a feasibility problem) and I have very little idea of solving such problems. The problem is as follows: Solve for $\phi$; \begin{equation} ...
1
vote
1answer
46 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
0
votes
0answers
34 views

Mathematical algorithm to assign robustness rating to Betfair Exchange Odds

The question I am asking also requires a bit of odds knowledge. Basically I need to come up with an algorithm/method that will assign a robustness rating to the Back And Lay Prices for each horse on ...
28
votes
1answer
2k views

How can we turn any number into a prime number by simply adding more digits?

How can we turn any number (where the number is > 2) into a prime number by simply appending more digits? I'm referring to the right side of the number. So 4 is not a prime number But If I append ...
3
votes
1answer
32 views

Best way to find if a subgraph has a cycle

I am implementing Kruskal's algorithm to find a minimal spanning tree of a connected graph $G$. If $H$ is a subtree of $G$, does anyone know a smart way of checking if $H+e$, where $e$ is an edge of ...
0
votes
1answer
46 views

Guess my number game (Plus Minus)

There is a number guessing game played by two players. The rules and procedures are the following: Let's say that we are playing the game with 4 digits. This is not fixed and not a strict rule of the ...
1
vote
0answers
22 views

Enumerate 'one number from each set' from a set of sets in order of increasing sum.

This question is somewhat similar to: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums but has a significant difference in that instead of enumerating all subsets of a set, ...
1
vote
1answer
20 views

Can geometric programs be solved more efficiently than general convex optimization problems?

I want to solve an optimization problem for which I have already proven that it is feasible and convex. Introducing further variables and considering a special case of the problem, I can formulate it ...
0
votes
0answers
28 views

Algorithm Identification

Background I'm currently working with a system that has a 4-dimensional function. Currently, an algorithm is used to speed up calculation of the final value via interpolation, and two of the ...
-1
votes
0answers
21 views

Fibonacci sequence algorithm function calls

Given the following pseudo code which is used to calculate Fibonacci numbers, how would you be able to determine roughly how many function calls are made by the program to calculate ...
1
vote
0answers
42 views

Still not clear why longest path problem is NP-hard but shortest path is not?

I've heard/read many times that shortest path problem is P, but longest path problem is NP-hard. But I have a problem with this: we say longest path problem is NP-hard because of graphs with positive ...
0
votes
1answer
25 views

Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
0
votes
1answer
32 views

Pattern finding algorithms

I am working on a server that will update a list each day. The list will look like the following example. ...
0
votes
2answers
34 views

Distinguishing between unimodal and bimodal normal data

I have a large number of data sets that have either a unimodal normal distribution or a bimodal normal distribution. I'm not a statistician by any means, so I'm quite limited in my experience. For ...
1
vote
0answers
5 views

Fast square of a row-stochastic matrix

I would like to implement the square $M^2$ of a row-stochastic matrix $M$. Running time is critical. Are there any known algorithms that exploit the special nature of $M$ and are faster than the usual ...
0
votes
0answers
14 views

Can the time complexity of maximum-flow algorithm using fattest path method be represented by |V| and |E| only?

I've got a problem with "fattest path" heuristic in Max-Flow algorithms. ( http://www.eecs.berkeley.edu/~luca/cs261/lecture10.pdf ) The problem is 'prove or disprove that the time complexity can be ...
0
votes
0answers
19 views

Understanding McAfee's Double Auction algorithm

I'm making a java program that implements the double auction mechanism described in this paper: http://vita.mcafee.cc/PDF/DoubleAuction.pdf I took some screenshots of the text in order to save time. ...
0
votes
0answers
20 views

Looking for conditions on generator sets of the form $\{a,b \}$ and $\{a,b,c\}$ on the group $\mathbb{Z}_2^3 \rtimes S_3$

Let $G$ be the group $\mathbb{Z}_2^3 \rtimes S_3$ with the natural action of $S_3$ on the coordinates of $\mathbb{Z}_2^3$. I want to know if there are subsets of $G$ of two elements or also 3 elements ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
0
votes
1answer
14 views

Time complexity for loop with pow and log n advancement.

So, I'm analyzing this loop. And I'm not sure of the time complexity. ...
7
votes
1answer
103 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
0
votes
1answer
30 views

Time complexity for inner loop

What's the time complexity for this code? ...
1
vote
1answer
14 views

Given a ray and line segment, compute radius of smallest circle satisfying certain criteria

Given a ray and a line segment, (efficiently) compute the radius of the smallest circle satisfying the following criteria: The circle contains the origin of the ray. The center of the circle lies on ...
2
votes
1answer
23 views

What is the algorithm used by Matlab for computing the Bessel function?

I am quite curious about the algorithm behind. It is definitely not the power series expansion, right? So, what is the trick? I cannot find it in the help file of Matlab.