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)

6
votes
0answers
151 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
48 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?
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
19 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
26 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
44 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
69 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
30 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
22 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
18 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
49 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
23 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
50 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
52 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) ...
0
votes
0answers
32 views

Modified version of SubsetSum

Let $L=\{(y_1,...,y_n,S,p)\ |\ \exists I\subset[n]\ s.t. \ |I|=p.\ \sum_{i\in I}y_i=S\}$. and $\forall\ 1\leq i\leq n\ :y_i \text{ is a positive integer}$, Assuming $\mathcal{P}\neq\mathcal{NP}$. ...
-1
votes
1answer
39 views

Finding the Time Complexity in Big theta notation [closed]

sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ...
0
votes
0answers
20 views

Online algorithm for reduced row echelon form

Rough Definition of "Online Algorithm" In computer science an online algorithm is used to calculates a function of a set, but is fed its inputs incrementally instead of at once. As a rule they ...
2
votes
1answer
48 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
0
votes
0answers
28 views

Doesn't the recursive Fast Fourier Transform violate f(-x) =/= f(x) for odd functions?

When you recursively split into $Y_{even}$ and $Y_{odd}$, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm ...
2
votes
1answer
38 views

Asymptotic lower bound of this function

Suppose that $n$ is an even number. Let $$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$ Can we find some function $g(n)$ (e.g. $\log(n)$ or $n^\alpha$) such that $f(n)=\Omega(g(n))$? ...
0
votes
0answers
19 views

Enumerating (some) combinations of elements subject to a constraint

Consider this variant of the knapsack problem: I own an outdoor goods store, and hikers come from miles around because of my amazing variety of products for sale. There are 4 popular hikes in the ...
0
votes
0answers
35 views

algorithm problem: MxN matrix such that each element is from {0,1}

the question is the following: let $A$ be a matrix $m \times n$ such that each element is either $0$ or $1$ and each row has exactly $5x$ "$1$"s in it and each column has $5y$ $1$'s in it ...
-1
votes
1answer
54 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
30 views

calculating max n so that a has nth root over $\mathbb{Z}$

is there a nice (fast) way to find the maximal n so that for $a \in \mathbb{Z_+} $, $a^{1/n} \in \mathbb{Z}$ ? The only algorithmn which i know is brute Force. Greetings
0
votes
0answers
16 views

Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
1
vote
0answers
51 views

Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
1
vote
1answer
47 views

What is the required group theory knowledge needed to understand Verhoeff's algorithm?

The Wikipedia page tells me I need to understand permutation groups and dihedral groups. Can someone clearly outline what exactly the perquisites of understanding this is and how much time I'll take ...
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 ...