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
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
55 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 ...
0
votes
1answer
44 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
56 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
35 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
53 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
218 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 ...