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
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
26 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
47 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
9 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
21 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
48 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
50 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
27 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
42 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
31 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
44 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
27 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
37 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
18 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
34 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
51 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
14 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
44 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
43 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
36 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
18 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
51 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
15 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
12 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
97 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
13 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
42 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
25 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
33 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
48 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 $...