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
30 views

Finding a primes combination of a number

Okay. So I wanted to do a simple program which would take a number from the user, and then it would list all the combinations (multiplications) of a prime numbers or their powers, which would give the ...
0
votes
2answers
56 views

Recursive matrix multiplication strassen algorithm

I am having a hard time doing 4x4 matrix multiplication using strassen's algorithm. First I computed the product of two 4x4 matrices using default matrix multiplication (https://matrixcalc.org) I ...
10
votes
3answers
59 views

Calculate the number of integers in a given interval that are coprime to a given integer

We can calculate the number of integers between $1$ and a given integer n that are relatively prime to n, using Euler function: Let $p_1^{\varepsilon1}\cdot p_2^{\varepsilon2} \cdots p_k^{\varepsilon ...
-4
votes
1answer
48 views

Buy Get Offer Calculation?

I have some clarification regarding any equation to do some logic like Buy 2 Get 3 Offer with repeat (means if i buy 4 then 6 to be off) If i add 2 quantities of product to cart then another 3 ...
1
vote
1answer
19 views

Calculating variance for a window of samples which already contains pre-calculated variances

In a previous answer, the following solution was given for calculating the variance from a stream of sample values (from Knuth via John D. Cook): $$ \begin{align*} m_k&=m_{k-1}+\frac{x_k-m_{k-1}}...
1
vote
0answers
23 views

For What Families of Subgraphs, the Subgraph Isomorphism Problem Can be Solved in Polynomial Time?

Are there families of subgraphs that are arbitrarily large and are still easy to match in a larger graph ? By a "family" I mean a graph sequence $\mathcal{G}=\{G_1,G_2,\ldots,G_n,\ldots\}$ which is ...
0
votes
0answers
42 views

Infinite sums and squaring the plane, or sort of

This question is regarding two algorithms for squaring/almost squaring the plane. the Henles' method of squaring the plane. pdf here my method of tiling $n^2$ squares. I worked out* a simple gap-...
0
votes
0answers
19 views

Pseudocode and loop invariant of the searching problem

I hope it's apt to ask questions about algorithms here in MSE. Prelude: I am absolutely new to formal understanding of algorithms, though I had been overusing the word "algorithms" in programming ...
1
vote
1answer
25 views

Existence of a fixed point for a linear stationary iterative method

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose ...
0
votes
0answers
30 views

What does 2n + 1 in long multiplication mean?

Having got some basics down in regard to addition and explaining it in terms of primitive operations, I am now again stuck on understanding the more complicated long multiplication. I have read in ...
2
votes
2answers
39 views

Mills Test Running Time

Can Miller's Test be replaced with the bound below in hopes that it would make a faster general-purpose primality test (compared to ECPP). If $n$ is an $a$-SPRP for all primes $a$ $<$ ($\log_2 n$)...
1
vote
0answers
12 views

For each of the functions, how to calculate a subgradient of the function at a given $x$.

We have $$f(x)=1/2||Ax-b||_2+||x||_2$$ where $A\in \mathbb{R}^{m\times n}$ and $x\in \mathbb R^n$ and $$f(x)=\inf_y||Ay-x||_\infty$$ where $A\in \mathbb R^{m\times n}$ and $x\in \mathbb R^n $
0
votes
1answer
43 views

Find a path from $s$ to $t$ with smallest “bottleneck”

Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ ...
0
votes
2answers
28 views

Recurrence: Theta of t(n) = 4t(n-1) -15

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with. ...
0
votes
1answer
21 views

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees ...
2
votes
1answer
33 views

A correct expression for Hardness?

I'm interested in whether it's possible to express the hardness of a result in the following form. 1.For example: Suppose $A(n)$ is the class of graphs for which the minimum degree $\delta(G)\geq n/...
-3
votes
2answers
34 views

Simple ranking/rating algorithm [closed]

Is there a Simple ranking/rating algorithm that calculates a score between 0 and 1 given a number of alerts along with its priority. For example: each system can produce "Low", "Medium" and "High" ...
2
votes
1answer
48 views

Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$. ...
0
votes
0answers
25 views

Pollard's $\rho$ algorithm and quadratic sieve

I am wondering why is quadratic sieve better than Pollard's $\rho$ for integer of $10^4-10^{10}$ digits? The running time of quadratic sieve is $e^{(1+o(1))\sqrt{\ln n\ln \ln n}}$, but the Pollard's $\...
0
votes
0answers
47 views

Is there a known fast algorithm to find the $k^\text{th}$ root modulo a prime?

I was trying to write an algorithm, but I got stuck at a point. Is there a known computationally fast algorithm to find kth root of an integer modulo a prime n, with k being odd and coprime to n. I ...
0
votes
0answers
20 views

Find a set of vertices $U\subseteq V$ included in some simple cycle

Let $G=(V,E)$, an un-directed graph. Find an efficient algorithm to return a $U\subseteq V$, where $u\in U$ is in some simple cycle of $G$. So basically we've learned in class about the $low$ ...
0
votes
2answers
56 views

Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
1
vote
1answer
20 views

For every $v\in V$, determine if it belongs to some negative cycle in $G$

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle. Obviously we need to utilize Bellman-Ford algorithm for ...
0
votes
0answers
10 views

Estimate the complexity for number times the function n/ lgn will be called recursively such that the result is a constant c = 2?

Cormen exercise $3.6$ which defines recursive function $f(i)$ such that $i$, $i \ge 0$ and the function is recursively called on itself $f(….f(i))$ such that it reaches a constant $c= 2$. Please help....
4
votes
0answers
74 views

I am looking for a mathematical equation to warp an image [closed]

Theoretically, I know that to warp an image, each pixel $(x,y)$ in the source image is transformed to $(x', y')$ using a function f (i.e. $x'=f(x,y)$ & $y'=f(x,y)$ ). But what mathematical ...
0
votes
0answers
14 views

2D Bin Packing with Ordering Along One Dimension

This is my second attempt at solving this particular problem (original is here: Topological sort into a limited number of bins, each with limited capacity). For clarity, I have reproduced the relevant ...
1
vote
2answers
29 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
1
vote
0answers
28 views

Monte Carlo Search Tree iterations

I have had this example in my exam last week and I can not figure out how to solve it. I have watched lots of tutorials on Monte Carlo Search Tree but I can't still understand this algorithm properly. ...
-1
votes
1answer
34 views

Construct a weighted graph under the following conditions:

I need to construct a weighted graph of which neither of the Greedy Algorithms produces a correct answer to the Traveling Salesman Problem. Greedy Algorithms 1) Nearest Neighbor Works as ...
4
votes
2answers
67 views

Can someone give me some ideas of algorithm for this card question?

Problem There is a $N$ by $1$ long card consisting of $N$ square cards, each having the number $1, 2, \cdots, N$ regardless of the sequence of cards. Find whether or not the long card could be in ...
1
vote
1answer
70 views

Coefficients of a Polynomial Approximation in Minimax Sense

I am working on a Uniform Random Number Generator using a IEEE paper, and I got stuck with the coefficients for a Piecewise Polynomial Approximation using Horner's Rule : $$ y = ((C_d x + C_{d-1})x +...
3
votes
0answers
19 views

Factory inspections on a budget

A factory inspector is testing the efficiency of $n$ machines. To pass the inspection, each machine is required to run at or above a certain standard efficiency. The inspector can measure the ...
0
votes
1answer
11 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
0answers
19 views

Basis Function Algorithm, In The NURBS book

On page 74, Peigl explained an algorithm about computing a single basis function. first lines of this algorithm are handling some special cases. ...
0
votes
1answer
28 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
44 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
28 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
24 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
17 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
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 \...