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
2answers
45 views

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

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
20 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 ...
1
vote
0answers
46 views

Scrambled Sobol

I need to do a Monte Carlo simulation in high dimension (up to 1000) where using plain Sobol (with Kuo's direction vectors) as a random number generator is not good enough. Therefore I am ...
0
votes
0answers
29 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
25 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
29 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
12 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
15 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
13 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
18 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
48 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
8 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
64 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: ...
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
153 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
52 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
5 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?
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
29 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
21 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
49 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
27 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 ...
4
votes
4answers
46 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
41 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
142 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
36 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
28 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
45 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
71 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
114 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
32 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
23 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
19 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
27 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
30 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
50 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 ...
0
votes
0answers
12 views

Minimizing component-wise convex functions

I want to minimize a function $f(\vec x,\vec y)$, whereby $\vec x$ and $\vec y$ are vectors. If I hold $\vec x$ constant, $f(\vec x,\vec y)$ is convex with respect to $\vec y$, and the reverse is true ...
0
votes
1answer
24 views

Devising an $n$-place mastermind variation algorithm

A few days ago I came across such a problem at the contest my uni was holding: Given the history of guesses in a mastermind game using digits instead of colors in a form of pairs $(x, y)$ where $...
0
votes
1answer
51 views

Algorithm for getting consecutive line segment edge points from midpoints

So I have a rectilinear grid that can be described with 2 vectors. 1 for the x-coordinates of the cell centres and one for the y-coordinates. These are just points with spacing like x spacing is 50 ...
1
vote
0answers
46 views

Simplify $f(x)=\Gamma(n/2)/(\Gamma(1) \Gamma(n/2-1))$… a Rational Expression using the Gamma Function.

I was reviewing a document about an algorithm wherein it is stated that $f(x)$ is a probability density function: (1)$$ f(x)=\frac{\Gamma(\frac{n}{2})}{\Gamma(1)\Gamma(\frac{n}{2}-1)}\frac{2}{n-2}\...
3
votes
0answers
53 views

How quickly can we find a value that has large multiplicative order modulo $n$?

If we're trying to find an element modulo $n$ that has multiplicative order at least $\sqrt{n}$, how quickly can we do this? We don't know if $n$ is prime or composite, only that $n$ definitely has a ...
3
votes
1answer
28 views

Is a shape 'polarizable'?

Given a point $p$ inside a shape $S$ described as an $n$-vertex polygon, let us say that $S$ is polar with respect to $p$ if S can be described by a polar equation $r(\theta)$ with $p$ as the origin. ...
-1
votes
1answer
56 views

Time complexity (in Θ –notation) in terms of n [closed]

I am struggling quite a bit trying to solve these and any help would be greatly appreciated. a) ...