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
112 views

Is there a term for $O( (m+n) \log{mn})$ time algorithms?

Is there a term for $O( (m+n) \log{mn})$? I remember seeing it often in some context but can't remember.
0
votes
3answers
78 views

how to calculate an integer x let x^2+2mx-n is a square number?

Let m, n be positive integers. Let $x^2+2mx-n=p^2$ for some p which is a positive integer. How does one solve for x? Sorry forgot this: x must be an integer.
2
votes
3answers
99 views

Is there any fast way to get the number of a certain day in a week

I'm realy sorry, if this question is a bit stupid... But this is my first time on mathematics stackexchange. Do you guys now for example, how to know the number of monday in a year?
2
votes
2answers
4k views

Runge-Kutta algorithm for a given ODE system

consider the system given by: $$x'_{1}=9x_{1}+24x_{2}+5\cos t-\dfrac{1}{3}\sin t$$ $$x'_{2}=-24x_{1}-51x_{2}-9\cos t+\dfrac{1}{3}\sin t$$ with initial values $$x_{1}(0)=\dfrac{4}{3}$$ and $$x_2(0)=\...
2
votes
2answers
3k views

Meaning of amortized analysis of an algorithm

From Introduction to Algorithms by Cormen et al: In an amortized analysis, the time required to perform a sequence of data structure operations is averaged over all the operations performed. ...
0
votes
1answer
405 views

How to solve this recurrence $T(n)= 7 T (n/2) + 2 \log (n)$?

Solve this recurrence equation $T(n)= 7T (n/2) + 2 \log (n)$? Could you please help me to solve it because I have been stuck on it for 2 nights. Thanks in advance.
1
vote
0answers
190 views

Why genetic algorithm find maxima/minima of a function

I don't know if this is the right place to ask for an answer to this question. If not, I would migrate the question with no problem. Anyway I use genetic algorithm quite often to find maxima and ...
3
votes
3answers
258 views

0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost (weight),...
1
vote
1answer
8k views

Convert a n by n matrix to upper triangular

How can we mathematically and algorithmic-ally convert a $n\times n$ matrix to a upper triangular matrix
0
votes
1answer
582 views

Pancake Sort in (n-1) flips

I've read in most places that the minimum number of flips in the worst case scenario required to sort a stack by any algorithm is between $15n/14$ and $18n/11$. But I read here: It was shown in ...
6
votes
1answer
925 views

Faster arithmetic with finite continued fractions

I was curious about different representations of rational numbers and came across the finite continued fraction (see wp:Finite_continued_fractions ). Note: I will refer to traditional rational ...
0
votes
1answer
742 views

Graph Theory: Clique concepts

I was trying to solve a basic clique problem but i have stucked at some following points: ...
34
votes
1answer
2k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
1
vote
1answer
54 views

Median-of-k elements

Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$. Then out of ...
4
votes
1answer
2k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
1
vote
2answers
119 views

Bijection $f : \mathbb{N} \rightarrow \mathbb{A}$ from naturals to algebraics

I'm doing a presentation on Godel's paper "What Is Cantor's Continuum Problem?", and would like to include a computational demonstration of the countability of the algebraic numbers. I'm looking for ...
2
votes
1answer
3k views

Finding common terms of two arithmetic sequences using Extended Euclidean algorithm

I have a problem which could be simplified as: there are two arithmetic sequences, a and b. Those can be written as a=a1+m*d1 b=b1+n*d2 I need to find the ...
2
votes
0answers
412 views

Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $$||f-G_m(f,D)||>Cm^{-1/2}|f|_{H}$$ ...
1
vote
1answer
636 views

Hamiltonian path in a tournament

Exercise: Suggest an effective algorithm finding Hamiltonian path in tournament with $n$ vertices using adjacency matrix T[1..n, 1..n]. Firstly, I proved that such path always exists. It was an easy ...
1
vote
1answer
409 views

How to solve/transform/simplify an equation by a simple algorithm?

MathePower provides an form. There you can input a formula (1st input field) and a variable to release (2nd input field) and it will output a simplified version of that formula. I want to write a ...
1
vote
3answers
473 views

Order of magnitudes comparasions

I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ...
0
votes
3answers
88 views

Big-O compared to a new Operator

I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
4
votes
1answer
436 views

Puzzle : Birds on a circular wire

The problem is taken from my course on randomized algorithms : There is a circle made of wire. n birds (assume n>2) occupy uniformly random position over it (visualize each bird occupying a point on ...
20
votes
2answers
18k views

Explanation on arg min

would someone be so kind to explain this to me: Especially the arg min part. (it's from the k-means algorithm)
0
votes
0answers
88 views

Solve $Ax = b$ where $b$ are labels instead of values

Suppose, there is a system of linear equations $Ax = b$, where $A \in R^{m \times n}, m>n$ and $b_i \in \{l_1,....,l_k\}$, i.e. each $b_i$ is a label instead of being a real number. To solve this, ...
10
votes
2answers
881 views

What would be the shortest path between 2 points when there are objects obstructing the straight path?

How would an algorithm find the shortest distance between 2 points on a horizontal 2d plane , especially when a straight path is not possible? Could it be something on the lines of calculating least ...
4
votes
1answer
421 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
3
votes
2answers
411 views

Computing orbit representatives for a group action

Consider the following classic problem in combinatorics: how many neckleces with $n$ black/white beds are there up to rotations? You can formulate the question in the language of group theory: acting ...
0
votes
1answer
418 views

Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta)

I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big $\Theta$ relations. Notice that I should prove the following using the defintion and not any complex ...
5
votes
1answer
276 views

Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
2
votes
1answer
878 views

Sub-Graph of a Minimum Spanning tree

I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question. Currently my thinking leads me to believe that since ...
1
vote
0answers
22 views

Splitting data based on 2 factors

I have two sets of data assigned to each parameter. Lets say they are weight and age. If I have 10 people, I want to split them into two groups of 5 each such that each of the groups combined weight ...
12
votes
2answers
631 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
2
votes
3answers
315 views

why $m$ power by $n$ equals sum of $n$ numbrs

$$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$$ (a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are $m$ and $n$. I know that this is true, ...
1
vote
1answer
320 views

What are the differences between the random walk and the gaussian random walk?

I know the random walk mobility model, but I can not understand what are the differences with respect to gaussian random walk. In other words, I know how to implement the two-dimensional random walk: ...
0
votes
0answers
62 views

maximizing sum of a 3 numbers to

There are n lines of length 90 inches which need to be cut at 1/2 places so that the new parts formed after cut have a total length as close as possible to 90. ...
0
votes
1answer
681 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
0
votes
1answer
341 views

Kruskal's algorithm proof

I'm having trouble understanding part of the proof of Kruskal's algorithm. In the notes that our professor gave us, he has this: Ok so this is missing some things. Unfortunately the lecture does ...
4
votes
2answers
979 views

Enumeration of partitions

The Stirling number of the second kind $S(n,k)$, where $S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$ Gives the number of unique unlabeled, ...
0
votes
1answer
134 views

Multiplying Polynomials with fewer coefficient multiplications

Not sure how this works! Apparently it can be done in 5-6 multiplications Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.
0
votes
1answer
94 views

Marching cubes - where does the isosurface cut the edge?

I am currently trying to figure out the insane marching cube algorithm (a.k.a. "3D contouring" or "Surface reconstruction"). According to Paul Bourke, The position that it [the isosurface] cuts ...
1
vote
0answers
88 views

Optimized Algorithm for Distance Matrix Solution

I've been looking for an optimized algorithm for solving a distance matrix (a hollow, skew symmetric matrix), but I haven't been able to find anything but papers discussing repopulating sparse ...
1
vote
1answer
213 views

Algorithm to find a derivation in propositional calculus

Does such a algorithm exist? I mean given a set of axioms and a rule of inference (e.g. modus ponens) it should create a full derivation of a given theorem (or state that it's impossible). The ...
2
votes
1answer
168 views

Bubble sort in two passes

In "Mathematics for the analysis of algorithms", I find the following problem. How many permutations on $\{1 \dots n\}$ can be sorted by at most two bubble sort passes? The book later goes on to ...
1
vote
1answer
216 views

N piles of hidden cards of known marginal probability distribution, then a card is revealed in one of the piles.

I am currently trying to use probability theory to help solve a programming problem involving Monte Carlo Tree Search with Information Sets and have hit a roadblock. The problem can be described as ...
1
vote
1answer
351 views

Finding all spanning trees of a strongly connected directed graph

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested program/...
2
votes
1answer
362 views

Probability - Expected value of a $n$ random selection

Given an integer $n$, one does $n$ random selections with repetition one after the other. For each selection there are two possibilities a success $X$ and a failure $O$. For each selection $i\le n$ ...
1
vote
1answer
233 views

Topological sort of a subgraph

If I have a graph $G$ and a subset $G'$, for all topological sorts $S$ over $G$, is there a topological sort over $G'$ that is a subset of $S$? As a software optimization I want to pre-compute $S$ ...
2
votes
2answers
59 views

Is there any way to split a number with multiplication of some prime number

I am looking for an algorithm which helps me split a number $N$ as such: $$N=p_1^a p_2^b \cdots p_n^z$$ where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ ...
3
votes
1answer
1k views

Computational Complexity of Modular Exponentiation

The following was posted from a lecture: "($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method. $Z_1 = a \bmod N$ $Z_2 = (aZ_1) \bmod N$ $Z_3 = (aZ_2) \...