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
1answer
44 views

self teach algorithms [closed]

What are some good resources to self teach the subject of Algorithms for someone with background in mathematics? That is, does there exists a more theoretical and abstract approach versus practical ...
0
votes
0answers
21 views

First Intersection Of Periodically Repeating Intervals

I have a set of coupled tasks, let's say $M$ of them. The $ith$ coupled task is represented as the following 3-tuple $\{A_i,D_i,B_i\}$ where $A_i$ represents the time it takes to perform the first ...
0
votes
1answer
43 views

A game: When can you merge two directed graphs?

I am trying to consider the conditions under which you can win the following directed graph game: Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $...
2
votes
0answers
35 views

Find smallest vectors in submodule of $\mathbb{Z}^n$

I have a $\mathbb{Z}$ submodule in $\mathbb{Z}^n$ given by a basis. I'm trying to get the smallest elements, where the norm used for smallest is not very important, lets say $\ell^1$ or $\ell^\infty$. ...
1
vote
1answer
32 views

NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself?

Translated exercise: Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses extra information $...
0
votes
0answers
26 views

What would be the formula to get the position of a combination, instead of a permutation ,given an index in this example

Let be an array A = {a,b,c,d,e,f} of six elements and we want three elements at the time, so the total number of permutations with repetitions will be: 6^3. Now to get the position of those ...
1
vote
1answer
41 views

Number of integer solutions of an equation $x^3 + y^2 = k$ [closed]

Given equation $$x^3 + y^2 = k$$ How can one count efficiently a number of integer solutions?
1
vote
0answers
19 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
1
vote
1answer
55 views

Maximum number of non-intersecting lines

Given a polygon with $n$ vertices as $P_1,P_2,\ldots,P_n$ and a point $A$ in 2D space, what algorithm can I use to determine how many of the segments $\overline{AP_i}$ do not intersect an edge of the ...
0
votes
1answer
21 views

How to efficiently sample $y$ in intervals of $\Delta x$ in an “ascending” cubic Bézier curve?

For a cubic Bézier curve defined by control points $\boldsymbol{P_0}$, $\boldsymbol{P_1}$, $\boldsymbol{P_2}$ and $\boldsymbol{P_3}$ with the formula $\boldsymbol{B}(t) = (1 - t)^3\boldsymbol{P_0} + ...
0
votes
1answer
17 views

Is given statement decidable or undecidable?

A given non-terminal A in a given grammar CFG is ever used in the generation of word.-Decidable/undecidable? My attempt: It should be decidable problem, We can solve this problem using membership ...
1
vote
1answer
14 views

An algorithm to decide if a context-free language like $L_1$ and a regular language like $L_2$ have common members

A context-free language (CFL) is a language generated by some context-free grammar (CFG). A regular language (also called a rational language) is a formal language that can be expressed using a ...
1
vote
0answers
20 views

Has it been proven that an asymptotically fastest multiplication algorithm even exists?

According to https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm, The Schonhage-Strassen algorithm which runs in time O(n log n log log n) was discovered and it was conjectured that the optimal ...
2
votes
1answer
103 views

Calculating large exponential probabilities

Earlier today there was Youtube video attempting to solve a problem for a certain game. In it he tries to calculate the probability of certain events happening which narrows down to this equation: $P(...
0
votes
0answers
21 views

Red-black tree insert

I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees): http://i.imgur.com/IKMCkVf.png And I do know that the correct one is number three from the ...
-1
votes
1answer
37 views

Algorithm to order and partition a set of of (n,m) pairs with constraints.

I ran into this problem while looking at Google API distance matrix service. Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for ...
0
votes
1answer
23 views

Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
1
vote
2answers
14 views

Max Flow Minimum Cut - after removing an edge

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut. Why is it must be that the max flow after removing $e$ is exactly $|...
1
vote
1answer
44 views

Data structure for a symmetric $n\times n$ matrix

Suppose you are given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and consider the computation of the matrix vector product $A u \rightarrow v$ where $u\in\mathbb{R}^n$ is given and $v\in\mathbb{R}...
0
votes
0answers
26 views

Computing unknown matrix norm

Suppose that we have a unknown vector norm but there is a machine that get a vector and correctly tell us the norm of the vector. Is there any algorithm to compute the matrix norm corresponding to ...
0
votes
1answer
34 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
2
votes
1answer
49 views

Finding numbers at least half the sum

Let $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$ be positive real numbers, and $A=\sum_{i=1}^na_i, B=\sum_{i=1}^nb_i$. Is there an efficient algorithm (i.e. polynomial time in $n$) that finds a subset $...
2
votes
1answer
52 views

Center of mass of convex polyhedron.

Given a set of 2d points we can find it's convex hull. Now I'm going to explain an algorithm I thought of and you guys let me know where I've gone wrong (because it probably is wrong) So our goal ...
1
vote
2answers
50 views

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected graph?

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected, unweighted graph?
3
votes
1answer
217 views

Conjecture about Rabin-Miller pseudo prime test

I tested the Rabin-Miller pseudo prime algorithm using a single test value and found that the number of false calls depends on the size of the number to test, reducing to a (conjectured) negligible ...
1
vote
1answer
9 views

Big Omega number theory representation

Source-https://en.wikipedia.org/wiki/Big_O_notation Is the highlighted portion in red right? $\forall$$n_0$ $\exists$$n>n_0$ It should be opposite(for all and for some should be interchanged)...
1
vote
0answers
5 views

Hurst exponent Algorithm not well defined? What to do in this case?

The R/S algorithm is well known for finding the Hurst component of a given data set. I have one query about whether it is well defined? Suppose in a given partition, all of the values were equal to ...
0
votes
0answers
35 views

Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with $$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ((a_1,a_2,\...
0
votes
0answers
16 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
1
vote
1answer
21 views

Relation between powers of inverse modulo n.

Recently, I was studying enchanced euclidean algorithm. I am wondering if there is some way to calculate inverse of $a^2$ (and higher powers) modulo $n$, knowing inverse of $a$ modulo $n$. For example:...
1
vote
0answers
18 views

Calculate random distribution of triangles within a rectangle. [closed]

I am a programmer trying to find a solution to a problem regarding images and JavaScript. I want to create a function that when given an image will calculate a random set of triangles of different ...
3
votes
0answers
195 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
0
votes
1answer
40 views

What is the order of

What is the order of the following: $$\frac{(33x^{7}+6)(x^{2}+3)}{\sqrt{x^3+7x^2-x+5}}$$ Would it be $$\Theta (x^{\frac{17}{2}})$$
3
votes
1answer
21 views

Prove that it is sufficient to check $\lceil \log(k) \rceil$ pairs to tell if a set of integers is pairwise coprime

I am reading chapter 31 of Introduction to Algorithms (CRLS) and I encountered some difficulties while solving 31.2-9. I managed to prove the first part of a problem, but I can't prove the generalized ...
0
votes
0answers
34 views

Solving system of nonlinear equations via iteration

I will give an example to illustrate the question: Assume I have the system: $$ xy + x + y = 7\\ x^2 + y^3 = 9 $$ and I want to solve for $x$ and $y$. It is a fairly common approach to rearrange ...
1
vote
0answers
12 views

Maximize the mutual permutation disparity

I am trying to work on a problem that needs me to find the top-k most disparate permutations for a n-tuple (hence n! possible choices). The disparity measure between two permutations I'm thinking of ...
2
votes
0answers
94 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ $(...
1
vote
1answer
30 views

Algorithm to check if number x exists in matrix

I have the task to develop an algorithm which checks if a specific number x exists in an int-array[][]. Further the 2-dim array entries have following terms: $$array[i][j] \leq array[i][j+1] \space \...
0
votes
0answers
6 views

Dynamic Biased Randomized Selection Algorithm

I'm looking to implement an algorithm that picks items from a list randomly, albeit in a biased way. Say I have a value priority for each element in that list. I would like an element with higher ...
3
votes
2answers
95 views

How can the policeman catch the gangster?

I try to solve the following problem (Moscow Mathematical Olympiad, 1978) There is a town with six streets: four sides of a square and two its middle lines. Policeman tries to catch a gangster. If ...
-4
votes
2answers
86 views

computer algorithm VS mathematical algorithm [closed]

I really dont understand the difference between computer algorithm and mathematical algorithm. Do you know? I tried finding a solution but I failed.
0
votes
0answers
45 views

Construction of Permutation Group (bounded order) from a Set of Permutation

Given a set of permutation $S$. It has $|S|$ (The cardinality of $S$) elements. Consider a subset $A\subset S$. We can construct a group using $A$. One possible algorithm could be- We start ...
0
votes
0answers
7 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
0
votes
0answers
24 views

What is the lowest order of linear ODE that cannot exist any general algorithm for solving all the aforementioned order differential equations?

What is the lowest order of linear ODE that cannot exist any general algorithm for solving all the aforementioned order differential equations? There are general algorithms that already can solve the ...
0
votes
0answers
72 views

Algorithm to calculate shortest time in which two people can collect K items from N cities.

There are N cities connected via M bidirectional roads. Each road connects exactly 2 different cities and has a travel time associated with it. There are K different items in these cities. Given the ...
3
votes
0answers
34 views

Find most varied match assignments for a 4-player card game

I'm a programmer and confronted with a particularly hard (at least for me) problem I couldn't find an answer for. This is not a school task or anything. It is something I need personally. I've ...
1
vote
0answers
54 views

About a geometric algorithm to compute $\sin$ based on the unit circle

In an old post I have found a user which claims to have a geometric algorithm to compute trigonometric  functions for an angle between $0^\circ$ and $90^\circ$ based on the unit circle. Here's the ...
0
votes
0answers
29 views

solving mathematical function using genetic algorithm

I want to solve a mathematical function(ex: f(x) = 2x*x+3x) which I want to implement using genetic algorithm. I was following through lecture in the given link . But couldn't understand few things ...
1
vote
1answer
34 views

Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be $8$. ...
2
votes
2answers
24 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...