Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

1
vote
2answers
55 views

Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server ...
1
vote
1answer
76 views

Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
0
votes
1answer
43 views

Number Triangle pattern

I have a number triangle as follows: $$\begin{array}{|c|c|c|} \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 0 ...
1
vote
1answer
137 views

finding if two binary quadratic forms represent the same integers

I am currently working with quadratic forms for a given discriminant D; to get all primitive forms (one for each equivalence class) I found this website : ...
3
votes
2answers
204 views

Algorithm for creating binary rational numbers

I read here an algorithm to convert a decimal rational number to binary by multiplications by 2, but although it's very simple to carry on, I still haven't managed to explain myself why it works. ...
2
votes
1answer
534 views

Determining the ratios needed in gear reduction

I am trying to work out the math behind building a gear box for turning a gear a specific RPM from a small motor. Given that a typical DC hobby motor turning at 200 RPM, and a target in the final ...
5
votes
0answers
62 views

Decoding of Gabidulin code

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
0
votes
2answers
89 views

Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges

Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph. The algorithm I have ...
1
vote
3answers
57 views

Generate numbers that add up to X

I have isolated the algorithm of a keygenme, but I am running into difficulty with creating the keygen. The key has a length of seven digits, and the sum of each of the digits in the key must be ...
0
votes
1answer
33 views

Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
0
votes
2answers
59 views

Using Euclid's Algorithm prove..

Using Euclid's Algorithm prove that the fraction $\frac{24n+5}{18n+4}$ is in lowest terms. Is this solution going to be correct as a proof? Thanks for help!
1
vote
1answer
108 views

How to use FFT algorithm

Given a set of n particles electric charge carriers founds on the points (1,0), (2,0), .... (n,0) on a plane. The particle charge that found in point (i,0) is noted as Qi. the force that act on the ...
1
vote
1answer
54 views

Proving an asymptotic run time is faster than another using L’Hôpital’s

I'm working on a problem: Show using L’Hôpital’s Rule that a running time of $n\log(n)$ is asymptotically faster than (i.e., little-oh of) a running time of $\frac{n^2}{\log(n)}$.` I suppose a ...
0
votes
0answers
17 views

Summation inside a range

I was a bit bored so I decided to create a program with a function that takes three variables: Upper, Lower, and ...
0
votes
1answer
39 views

Running time and standard deviation of Marsaglia and Bray's Polar Method

I have some trouble calculating the standard Deviation and the mean running time of the polar method by Marsaglia and Bray. More specifically the repeat portion of the algorithm. In this case the ...
0
votes
1answer
63 views

Obstacle course and line intersection

In my computer class I'm learning about computational geometry and I have a problem to solve but can't understand how to get to the solution. Imagine I have a $10$ by $10$ board and on top of that ...
1
vote
0answers
67 views

Algorithm for finding irreducible polynomials in finite field extension

Let $K(\alpha_1,\ldots,\alpha_n)/K$ be a finite field extension and suppose we know ${\rm irr}(\alpha_1,K),\ldots,{\rm irr}(\alpha_n,K)\in K[x]$. My question is: given an arbitrary element $\lambda\in ...
2
votes
2answers
74 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
-3
votes
1answer
56 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
2
votes
2answers
74 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
9
votes
3answers
345 views

Finding 1000th 5-smooth number

Smooth numbers are natural numbers that are products of only small prime numbers. They have some applications in cryptography. A number is 5-smooth if its only prime factors are $2,3$ or $5$. ...
3
votes
1answer
1k views

What initial guess is used for finding n-th root using Newton-Raphson method?

I would like to know what is an optimal initial guess for use with Newton-Raphson method when finding n-th root. I develop some program which uses GMP C++ library. GMP manual says: The initial ...
0
votes
3answers
325 views

Wolf cabbage and goat using dijkstra.

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. ...
2
votes
1answer
152 views

Number of Basic Operations - Grade School Multiplication Algorithm

I am currently taking an online course and am confused by this question regarding the Number of Basic Operations. Problem: Count the number of these basic operations performed as a function of the ...
4
votes
1answer
56 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
3
votes
2answers
191 views

Sum of multiplication of all combination of m element from an array of n elements

Suppose I have an array {1, 2, 3, 4} and m = 3. I need to find: ...
1
vote
0answers
41 views

How to find the length of the union of Isosceles triangles

I am given N number of right angles triangles all of which are also Isosceles triangles. For each triangle, I am told where they start on a number line and where they end on a number line with end ...
1
vote
1answer
48 views

How to find the size of the largest collection of orthogonal rows

Given a non-square matrix $M$ over the reals, how can you find the size of the largest collection of orthogonal rows?
2
votes
2answers
859 views

Simple algorithm for generating Poisson distribution

I found a very simple algorithm that draws values from a Poisson distribution from this project. The algorithm's code in Java is: ...
-1
votes
1answer
189 views

MAX-HEAPIFY - why the worst case is when the bottom level is “half full”?

In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says: The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row ...
2
votes
2answers
205 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
1
vote
1answer
42 views

Collapse paths in a directed graph algorithm

Let's say there are 4 people: A, B, C and D. A owes B \$100, B owes C \$75, C owes A \$10, C owes D \$85, and D owes B \$1. That can be reduced to: A owes B \$26, A owes D \$64, and C owes D \$20. ...
1
vote
0answers
21 views

Show that the running time of the build_heap function is $O(n)$

I'm not entirely sure whether this question fits on math.stackexchange, but since it's basically a question about asymptotic running time, I thought I'd try to post it here. In case it's not ...
1
vote
0answers
27 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
1
vote
1answer
49 views

Looking for optimisation algorithm

I have a problem and need to find proper algorithm to tackle it. Basically, I have a finite set of items I, each having N distinct and discrete properties like color, shape, material i.e. I = [P1, ...
1
vote
2answers
90 views

Matrix decomposition definition

Wikipedia says "In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different ...
1
vote
1answer
52 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
2
votes
0answers
34 views

Combinations of Choices

I have a pretty hard problem to solve here, and I have no idea how to start. I have X kind of fruits and 5 colors (let's say Red, Green, Yellow, Blue and Purple). Each fruit can be available in ...
0
votes
0answers
20 views

Ranking posts according to attention gained over a given period of time

This is my 1st question here, I am a software dev but almost a complete newbie when it comes to math, I am trying to solve a handful of challenges using my primitive knowledge so any side notes, tips, ...
0
votes
1answer
76 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
2
votes
0answers
23 views

Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example). I'm ignoring the decision problem, because I am doing two things that ...
0
votes
1answer
77 views

How to quickly find if point lies between 2 non-intersecting segments?

Let's say we know that point P(x1, y1) lies in between Xa and Xb on the cartesian coordinate system. How to quickly check if it is contained within 2 non-intersecting segments that originate from line ...
0
votes
2answers
37 views

Satisfiablity 2

Im trying to work out whether the following clause is satisfiable: {x, y},{x,¬y},{¬x, y},{¬x,¬y},{x, z},{x,¬z},{y, z},{y,¬z} My basic understanding is to work ...
1
vote
0answers
82 views

Absolute values nested multiple times

Is there any algorithm to quickly determine "zero points" (i.e. points with undefined derivation) of absolute values functions which are nested multiple times? I do know, that any part of this ...
1
vote
1answer
77 views

Karatsuba Method

For polynomials $f(x)$, $g(x)$ of degree $d = 2^{r-1}-1$, how do I check that multiplying $f(x)$ and $g(x)$ by the Karatsuba method requires $3^{r-1}$ multiplications in the field $F$?
0
votes
2answers
438 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
1
vote
2answers
4k views

How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
1
vote
1answer
68 views

Given a collection of ordered sets, find minimal order-preserving superset

Say I have some collection of ordered sets $C = \{S_i\}$. Is there an efficient way to determine the minimal ordered set $S^*$ such that each of the original $S_i \subseteq S^*$, with order ...
2
votes
3answers
50 views

How to combine Unitary Matrices in a clever way?

I am trying to implement genetic-type algorithms on unitary matrices. Hopefully I should be able to use this question for the mutation part. But I am having an issue with the cross-over step. So here ...
3
votes
3answers
77 views

Examples of “eventually reaches y under iteration” other than the Collatz problem

The Collatz conjecture states that iteratively applying the map $$f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$ to any ...