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)

2
votes
1answer
60 views

how to compute a^x %p

Hi I want to calculate $a^x mod p$ where p is prime and $x$ is large. What I know is that since $p$ is prime, it forms a cyclic group with order $p$ ie $ a^p$ $mod$ $p = a$. Thus, my problem will be ...
0
votes
0answers
34 views

2-approximation for TSP-metric

I got stuck with the following question: Consider the following heuristic: Start with a tour containing only one vertex. At each step, find the vertex outside the tour with the lesser distance to ...
1
vote
1answer
133 views

Prove that the “even” subset sum problem is NP-complete

I need to prove that the even subset sum problem is NP-complete. "Given a finite set of natural numbers and an even number $n$, decide whether a subset of the given set exists such that the ...
0
votes
1answer
124 views

Algorithm to find Frobenius number

I realize that such a question may have already been asked, and having looked at a few, I didn't really understand how to calculate a frobenius number. So, is there a general equation that can be ...
0
votes
0answers
47 views

Algorithm to check if a graph has exactly one perfect matching

What is an algorithm to check if a general graph has exactly 1 perfect matching? Or an algorithm to check whether a graph has more than 1 perfect matching?
0
votes
1answer
51 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ ...
1
vote
1answer
120 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
0
votes
5answers
103 views

Refresh summation formulas

I am trying to refresh on algorithm analysis. I am looking for a refresher on summation formulas. E.g. I can derive the $$\sum_{i = 0}^{N-1}i$$ to be N(N-1)/2 but I am rusty on the and more complex ...
2
votes
0answers
66 views

“Alice and Bob” problem with matrices

Alice has a binary matrix $A$, and Bob has a binary matrix $B$. Both matrices are of size $n \times n$. Alice and Bob want to check if the matrices are equal except for exactly $1$ entry. Alice has to ...
2
votes
1answer
951 views

Creating a Rubik's Cube Algorithm

So, I realize this isn't a very math-oriented question, but I thought it fit better here than anywhere else. Anyway, I was simply wondering how people come up with the many Rubik's Cube algorithms, ...
1
vote
1answer
15 views

Algorithm to find out on which position ZX is?

I am having the following problem. Lets consider the alphabet. From A-Z there are 26 letters. If its for example AA, then its ...
2
votes
1answer
139 views

Is the property reflexive, symmetric, anti-symmetric, transitive, equivalence relation, partially ordered given the relation below?

I'm working on this and I'm supposed to figure out if the following properties apply to the below relations. Properties are: ...
0
votes
1answer
34 views

Understanding the definition of the d-dimensional Hyperube

Please see the picture bellow about the definition of the nodes of the d-dimensional Hypercube. Could anyone please tell me what does that notation means. I get confused with the superscript after the ...
0
votes
0answers
58 views

Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
0
votes
1answer
38 views

Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
2
votes
2answers
248 views

Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
1
vote
1answer
56 views

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=\Theta(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ ∀$n$.

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=Θ(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ $∀ n$. Is the above true or false. I would say its false but honestly its a guess and i ...
1
vote
0answers
21 views

Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$ \leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I ...
1
vote
0answers
127 views

Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be: $ x*y = (x \uparrow y) \bmod n $ where $ \uparrow $ is the symbol for tetration. ...
1
vote
2answers
399 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
0
votes
0answers
31 views

Complexity of and an algorithm for finding ideals of a ring?

One of the problems that has been a roadblock in my understanding of ideals has been how one would find them. One way of finding an I of some ring R would be to say $ \forall x \in I, \forall r \in R ...
0
votes
1answer
970 views

How many 10-bit strings with more 0’s than 1’s?

I have to pick the answer from: a.512 b.386 c.256 d.252 e.none of these The number of bit strings of length 10 with n 0's (or n 1's in fact): is C(10,n) , where C(a,b) = a! / [(a-b)!b!] is the ...
4
votes
2answers
85 views

What is the value of the following? $3^{302} \mod 5.$

I have to choose from a. 0 b. 1 c. 2 d. 3 e. 4 I think its e. 4 because $$3^{302} = 3^{300} \cdot 3^2 = 3^{4\cdot 75} \cdot 3^2 = (3^4)^{75} \cdot 3^2.$$ Applying Fermat's Little Theorem to ...
3
votes
1answer
116 views

Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$

Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$. Given $n+1$ values ...
0
votes
1answer
76 views

Working out a formula for a series of numbers which are NOT an X-Y set

I need to find a formula, which can calculate the value of M from the given value, O. The values are as follows: O0, 1, 2, 3, 4, 5, 6, 7, 8 … M1, 2, 4, 8, 16, 32, 64, 128, 256 … Note that the values ...
0
votes
1answer
108 views

An efficient algorithm to pair chess players in a team tournament

I found this question on a website. Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of $M$ players, numbered $1,2,\dots,M$. You have $N$ ...
0
votes
2answers
81 views

$O(n^{\log(n)}) $ time algorithms

Is $O(n^{\log(n)}) $ time algorithm considered of exponential time ? Is it applicable ?
1
vote
0answers
82 views

Ideal shrinking of discrete randomness source

I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to ...
1
vote
2answers
200 views

Given a Cayley table, is there an algorithm to determine if it is a dihedral group?

Showing that it is a group is simple enough, but is it possible to determine if it is a dihedral group or not just by looking at the Cayley table?
1
vote
1answer
39 views

find the polynomial if we know its output

$f$ is a polynomial of integral coefficient.Now suppose we have a computer program to find out its output taken in $\mathbb{Z}$.Is it possible for us to find out this polynomial in finitely many ...
1
vote
0answers
41 views

Mathematical formulation of Algorithms

Is there a way to formulate the definition of algorithms mathematically, so that the effectiveness and completeness of algorithms is justified.
0
votes
1answer
88 views

Properties of the relation R on the set of all real functions

So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: Reflexive Symmetric Anti-Symmetric Transitive ...
2
votes
2answers
103 views

Time complexity (in Θ-notation) in terms of n?

Can someone please help me with this problem? Any help would be much appreciated? Thanks in advance!! ...
4
votes
1answer
75 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
0
votes
1answer
53 views

The maximum length of a line contained inside a convex polygon

I have a convex polygon. What algorithm do you suggest to find the maximum length of a line with a specific slope that is contained inside the polygon. The direction of the line is shown with blue ...
0
votes
1answer
47 views

Intersect and Trim lines with a polygon

I have defined a Polygon. I want to intersect and trim a list of other Lines with the Edges ...
2
votes
1answer
163 views

What is the time complexity (in Θ-notation) in terms of n?

Consider the following algorithm, where $n$ is a parameter. ...
0
votes
1answer
24 views

Scale position on weighted vector

I have a logic problem in a software I'm writing that I can't identify a way to resolve. Maybe it's just simple math and I'm overthinking. In this software, the user select several colours in a ...
2
votes
2answers
105 views

How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
2
votes
0answers
134 views

Flow reduction by removing a set of k edges

I am trying to find an algorithm which recieves as input: 1) a Flow network N(G,c,s,t) in which the capacity of an edge is either 0 or 1 (i.e. Exists or not). 2) a positive integer k The output ...
0
votes
0answers
25 views

Is there a algorithm to extract the minimum number of Cartesian products from a set of formulas?

For example, we have a set of formulas as below: B*2*j B*3*i B*3*j C*2*j C*3*i C*3*j D*2*i D*2*j D*3*i D*3*j And we could have three Cartesian products to ...
1
vote
1answer
56 views

Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
0
votes
3answers
96 views

Algorithm for Fundamental theorem of arithmetic

What is a good algorithm for decomposing a number into a product of primes? What would be its time complexity?
0
votes
0answers
52 views

Algorithm to draw a 2D graph of bounds connecting points

I have a list of triangles, facets of a 3D convex hull, and I'd like to represent the relations between those facets on a 2D diagram, a bit like a puzzle, where each face is (for matter of simplicity) ...
1
vote
1answer
1k views

Solve non-linear equations of 3 variables using Newton-Raphson Method iterms of c,s and q.

The three non-linear equations are given by \begin{equation} c[(6.7 * 10^8) + (1.2 * 10^8)s+(1-q)(2.6*10^8)]-0.00114532=0 \end{equation} \begin{equation} s[2.001 *c + 835(1-q)]-2.001*c =0 ...
2
votes
1answer
82 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
0
votes
1answer
68 views

Concrete Example of Maximum Likelihood Estimator

I was reading this article, about how seatgeek creates its algorithm for choosing the optimal seat: http://chairnerd.seatgeek.com/the-math-behind-ticket-bargains Most of it is straightforward up ...
0
votes
2answers
48 views

Improving an algorithm for defining a matrix

I am making a program of combinatorics. There is a step where I give an integer n and I want n positive or zero integers $a_i$ so that $\sum \limits_{i=0}^{n-1} a_i=\frac{n(n-1)}{2}$. I would like ...
2
votes
1answer
69 views

Algorithm - iterative method

I'm stuck on an exercise on algorithms, can you help me with this exercise? Solve this recursion using iterative method. $$T(n) = \begin{cases}1 & n=1;\\ 2, & n=2;\\ T(n-2) + n/2,& ...
1
vote
0answers
83 views

3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...