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
0answers
28 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
17 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
73 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 neighbor....
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
33 views

Sigma notation for following nested loop

How may the following programming statement be written as summation? ...
-1
votes
4answers
81 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
342 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
29 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
56 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 "calculus-...
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} + ... + \frac{1}{2013*...
0
votes
0answers
29 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
58 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
41 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
33 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
53 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
24 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
21 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
29 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
vote
0answers
47 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
29 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
39 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
43 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
16 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
19 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
109 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
31 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
26 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.
1
vote
0answers
32 views

Any efficient approach to find the minimal vectors?

$\bullet$ A vector $X=(x_1,\cdots, x_m)$ is less then vector $Y=(y_1,\cdots,y_m)$ when $x_i\leq y_i$, for each $i=1,\cdots, m$, and for at least one $j$, we have $x_j<y_j$. $\bullet$ A vector $X\...
0
votes
0answers
47 views

NP-Complete: Prove this Problem is in NP (specific)

I'm trying to prove that this problem is in NP: Given $n$ dices, there are at least $m$ ways of rolling a given value $y$. Theoretically I need to argue that there is an efficient verifier for ...
1
vote
1answer
28 views

What is the approach to understand this algorithm?

Given $\{x_1, x_2,\ldots x_n\}$ where $x_i \in \{0, 1\}$ there is a binary equation $\varphi$ that is $x_{t_1}+x_{t_2}+\cdots+ x_{t_m}=0 \mod 2$ where $t_i \in \{1,2,\ldots,n\}$ for $x≥1$, $i=1,2,\...
0
votes
0answers
14 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
0
votes
0answers
38 views

Recurrence for number of ways to write n as the sum

I'm trying to find the recurrence for this problem: ...
0
votes
0answers
19 views

A problem on random q-colourings of a graph for randomly chosen vertex

Here is an exercise from Olle Haggstrom's "Finite Markov Chains and Algorithmic Applications" from the chapter "Fast Convergence of MCMC Algorithms". The exercise is based on random $q$-colorings of ...
0
votes
4answers
63 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
1
vote
1answer
25 views

Graph Theory - Minimization by degree problem

I'm a 3rd year Math undergrad and I decided to take an algorithms extra class. This question was a bonus one on my mid-term and I still have no idea on how to approach it. Given $n$ vertices, each ...
0
votes
0answers
42 views

Equality of two functions.

I have a specific question, from a paper given below. Here I got an answer of question: When two functions are called equivalent?.It helped me to understand the first and the second steps of the ...