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
0answers
14 views

Exam Recurrence and Complexity [on hold]

I have an exam coming up in a few days and my prof gave us a couple questions we should know as he will make new questions based on these topics the explanations must be in-depth because it will be a ...
0
votes
1answer
8 views

Why is the running time of the trial division $O(f \cdot (log N)^2)$?

I saw this being cited in a few paper,but none of them seems to explain why this is the case. Maybe because it is quite trivial, but I am not sure why exactly... Here $f$ is the size of the factor. I ...
0
votes
1answer
20 views

Intuition behind this algorithm for finding an Eulerian circuit in a graph?

An Eulerian circuit of a directed graph $G = (V,E)$ is a path that travels through every edge in $E$ exactly once. This algorithm finds such a circuit if it exists. (I am interested in the directed ...
-2
votes
2answers
39 views

What can be a good programming algorithm to solve the given equation other than the brute force? [on hold]

Find all $x$, $y$ and $z$ for $n=100$; $$x^2 + y^2 + z^2 = n$$ $x,\ y,$ and $z$ should be positive integers.
0
votes
1answer
17 views

Determining when two binary strings represent the same necklace or when one binary string is periodic

An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes ...
0
votes
0answers
24 views

Chinese Postman Problem - open walk variation

Consider the following variation of the Chinese postman problem (also known as the route inspection problem). Instead of finding the shortest closed walk which traverses each edge at least once, find ...
0
votes
0answers
21 views

number of inversions in permutation if subarray of permutation is reversed?

I have permutation(P) of numbers 1 to N (<=10^5) . Suppose I can reverse the subarray of ...
0
votes
1answer
27 views

Fast way of suming up polynoms

You probably will think that this question is more about algorithms, but actually i'am searching for right formula. What i want to do is to compute $(A^n + A^{n-1} + .. + A + 1))$ mod $(10^9 + 7)$ ...
0
votes
0answers
8 views

Acyclic orientation of a mixed graph with minimization of the critical path

I already asked this question as a guest but I was not able to edit it or add comments after I registered with my e-mail address. A apologize for asking the same question again. A mixed graph is a ...
0
votes
0answers
14 views

Finding and proving upper bound of specific function

Following function is given: $$ f : \mathbb{N{}} \rightarrow \mathbb{R^+} , n \mapsto \begin{cases} n! & \text{for } 1 \leq n \leq 17\\ 2^{2^n}& \text{for } 18 \leq n \leq 42 \\ \log_2 n &...
0
votes
0answers
12 views

Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
0
votes
0answers
15 views

Genetic algorithm optimize and minimize

I'm using a Genetic Algorithm to increase a certain value and decrease another. I'm trying to find the best parameters for a trading strategy. There are 2 values important for me. The netto profit ...
0
votes
3answers
46 views

How do I find Big O notation for this function?

How do I find Big O notation for this function? $$ n^4+100\cdot(n^2)+50 $$ In the book I am following, I got the following solution: $n^4+100(n^2)+50 \leq 2(n^4) \ \forall \ n \geq 11$ $n^4+100(n^2)+...
0
votes
0answers
7 views

Morphological operations with even sized structuring elements

The well-known morphological operations, such as dilation/erosion, opening/closing, top-hat... , widespread in digital image processing, are defined by means of so-called structuring elements. For ...
-1
votes
1answer
20 views

how to get the angle of arc ??

dart game board is divided into sectors by 30 degrees like pizza slice. the given is (x, y) coordinates, and I need to find where coordinates are lying on. how can I get the angle just with ...
1
vote
1answer
61 views

approximate greatest common divisor

I try, without success, to create an algorithm that can compute the average greatest common divisor of a series of integers. For example, I have the following numbers: ...
-3
votes
0answers
27 views

How to correctly UPDATE the Centroids in the Fuzzy C Means (FCM) algorithm?

ATTENTION TO THE MODERATORS: In a previous time, my question was arbitrarily moved to stackoverflow forum, despite my inquiring to not do it, then it later was deleted from that forum by another ...
2
votes
0answers
10 views

Is there a known optimal solution for searching an ordered list with non-uniform query cost?

Let $D$ be the set of integers from $1$ to $n$ inclusive for $n \geq 1$, and let $$f(i) = \begin{cases} 0& i \leq k \\ i - k& i > k \end{cases}\,\,\,\forall\, i \in D$$ for some $k \...
6
votes
0answers
142 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
1
vote
1answer
42 views

Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
0
votes
0answers
4 views

What is the difference between a MIMO and multiple MISO fuzzy logic classifiers?

If I have 10 independent inputs and 5 independent outputs, can I say that a multiple MISO fuzzy logic classifiers equal to the function of a MIMO fuzzy logic classifier?
-3
votes
0answers
32 views

Algorithm for transpose matrix [closed]

Morning I have to do an algorithm of the transpose of matrix time by vector. Ex:Algorithm of $A^t$×$B$ Where $A = (a_{ij})_{n\times n}$ is a matrix and $B=(b_{i1})_{n\times 1} $ is a Vector ...
0
votes
0answers
28 views

Finding integer solutions to quadratics in the form [duplicate]

In a set containing two different types of elements the probability of randomly choosing two elements of the same type can be expressed as: $$\ \frac nm * \frac {n-1}{m-1} = \frac 1x$$ Where n is ...
2
votes
0answers
23 views

Algorithm similar to the Euclidean algorithm

Given a prime number $p$, and an initial number $1<a<p$, what would be the upper bound on the iteration number of the following algorithm? (1) if $a=1$ then stop (2) else replace $a$ by $p - a\...
1
vote
0answers
28 views

How to calculate water discharge [closed]

I asked this question on stackoverflow and stack community recommended me to ask my question here. I want to know how can I calculate water discharge when I am given values of river cross section, ...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...
0
votes
0answers
23 views

Connected undirected graph, finding a cycle [closed]

For a connected undirected graph $G$ and three edges $x, y$ and $z$, find whether there is a cycle in $G$ that contains both $x$ and $y$, but not $z$. The algorithm must run in linear time.
0
votes
0answers
44 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
2
votes
1answer
38 views

Algorithm for finding the representation of an integer as a sum of two squares

We know that an integer $n$ is the sum of two squares if and only if all its prime divisors $p$ of the form $p \equiv 3 \pmod4$ have an even exponent in the prime factor decomposition of $n$. My ...
0
votes
0answers
13 views

(Time series) outlier detection algorithm

I'm looking for a good outlier detection algorithm. The idea is pretty simple: every two hours, some data comes in, I compute some value(s) and add them to the ones I already computed. The objective ...
1
vote
0answers
22 views

Proving that problem of finding the winner in symmetrical game is in NP

Recently, I've stuck in quite an interesting problem. Here's its full description: Consider a connected, non-directed, weighted graph G. In some $v \in V(G)$ stays a chip. Two players are playing ...
3
votes
4answers
37 views

Suppose the integers $m^2$ and $n$ are relatively prime. Show that $m$ and $n^2$ are relatively prime.

My attempt so far: Since $m^2$ and $n$ are relatively prime, $am^2 + bn = 1$ for some integers $a$ and $b$. I know that I will have to use this to somehow prove that $cm + dn^2 = 1$ for some ...
0
votes
3answers
39 views

How to find the modulo multiplicative inverse?

"Find the multiplicative inverse $(\overline {47})^{-1}$ in $\mathbb{Z}_{53}$" My attempt so far is to use the Euclidean algorithm to establish that (-1/6)(47) + (1/6)(53) = 1 However I'm not ...
6
votes
1answer
52 views

Circle packing – How to get the minimum length?

In an a past admission paper from a local university, I came across a problem I couldn't solve. Given $n$ circles with their respective radii $r_1, r_2, \dotsc , r_n,$ we are to find the minimum ...
0
votes
0answers
32 views

Minimizing a function including max functions

Consider the following problem. Let $\mathcal{N} = \{1,2,\ldots,N\}$ and $\mathcal{N}^i = \mathcal{N}\setminus \{i\} $. For each $i \in \mathcal{N}$ and for each $S \subset \mathcal{N}^i$, we have a ...
4
votes
2answers
21 views

Iterative function of $f(n)=2n$

In Cormen's book (chapter 3, page 58), it is shown that for iterative functions: $$f^{(i)}(n) = \begin{cases}n & \text{if }i=0,\\ f(f^{(i-1)}(n)) & \text{if }i > 0.\end{cases}$$ I have ...
0
votes
0answers
35 views

Given set of points in 3D, find group of points closest to each other

Given a set of any 8 points in 3D space. I want to find a subset of points that are closest to each other. Application: Assume in a 3D space, I have any 8 colors(represented in RGB). I know how to ...
0
votes
0answers
23 views

Order nodes in a graph to minimize edge crossing

Given an undirected graph, is there any efficient algorithm to order the nodes into a sequence $\langle v_1, v_2, \ldots, v_n \rangle$ s.t. the number of edge crossings is minimized? Two edges $(v_i, ...
2
votes
1answer
62 views

Derangement combination calculation

For the traditional classic problem of derangement (https://en.wikipedia.org/wiki/Derangement), there is a formula $n! = (n-1)(!(n-1)+!(n-2))$, which calculates current results based on previous ...
2
votes
1answer
113 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
0
votes
1answer
29 views

Pairwise comparison algorithm

I am interested in performing pairwise comparisons -calculating the euclidean distance between each pair and find the pairs with the highest distance- efficiently. The pairs to be compared should not ...
0
votes
1answer
20 views

Modeling the maximum number of moves in Tower of Hanoi problem

What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).
1
vote
1answer
25 views

2 variables “variable weighting” function

I have two variables $X,Y \in [0,1]$ and want to output some kind of weighted indicator based on these two. X is a raw indicator value where a low value indicates good health, and Y measures ...
0
votes
0answers
12 views

Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...
0
votes
0answers
19 views

Efficient algorithm to list all sequences that sum up to a constant value

We are given A set of T numbers S1, S2,....ST An integer called Range This means 1st number can take on (2*Range+1) values (S1-Range,S1-Range+1,...S1, S1+1,....S1+Range) Similarly 2nd, ...Tth can ...
1
vote
1answer
24 views

Topological sort into a limited number of bins, each with limited capacity

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together ...
1
vote
0answers
28 views

AI Parameters for Tetris-like Game

I am building an AI to play a variation of Tetris. The rules are changed in that there are 19 different types of pieces, rotation is not allowed, and the pieces can be placed anywhere in a 10X10 grid. ...
2
votes
1answer
44 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...