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)

1
vote
0answers
23 views

When is $\frac{2 n f(n)}{n !}$ in the order of some fixed power of $n$?

I would like to know when $\frac{2 n f(n)}{n !}$ is $O (n^b)$ where $b$ is a constant. Here, $n$ is a positive integer. My attempt: $$ \frac{2 n f(n)}{n !} = \frac{2 n f(n)}{\sqrt{2 \pi n} (\frac{n}{...
0
votes
1answer
48 views

Analysis of bisection search

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/ In the following video i'm ...
2
votes
2answers
53 views

Why does $\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}$?

From CLRS Problem 4.3, part 5 . Why does the following holds? $$\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}. $$
1
vote
0answers
49 views

Intersection of two sets of rationals

I'm looking to see if anyone has any solutions or references for this problem. I'm not even sure of a proper category. It seems like it should be trivial, perhaps I'm missing something obvious. ...
1
vote
0answers
36 views

Sifting algorithm for group generated by a set. [closed]

On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2). I have some confusions. The algorithm needs to go to all column element indexed by ...
0
votes
0answers
14 views

Is there a simple way to describe all $O(n)$ algorithms given simple assumptions about the machine?

For example, can all $O(n)$ algorithms (where $n$ is strictly an integer) be described as: for k in 0..f(n): O(1)(k) where $f$ is a linear polynomial in $\Bbb{...
1
vote
1answer
29 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
0
votes
0answers
7 views

Knuth X exact cover

The famous algorithm for exact cover is given by Donald Knuth called Knuth X algorithm. https://en.wikipedia.org/wiki/Exact_cover) ...
0
votes
1answer
37 views

Finding the overlap between direction of distance in position space and direction of distance in velocity space

There are two objects A and B that can be described in position space and velocity space. The position space describes the instantaneous positions of the objects while the velocity space describes ...
1
vote
1answer
32 views

how to find closely related values from a set?

I have a set of values, for eg. {20, 1, 1, 21, 8, 22, 11, 40, 5, 21} and will need to find n closely related values. If n is 4 in the given example, the result should be {20, 21, 21, 22} because these ...
1
vote
1answer
21 views

translating algorithm to preserve validity?

Let two languages $\Sigma_1 = \{R^2, P^1, =^2\}$ and $\Sigma_2 = \{c, f^1, =^2\}$. Prove or disprove: There's an algorithm (procedure that halts) which gets as an input a formula $A$ above $\Sigma_2$ ...
0
votes
0answers
17 views

Graph theory decision tree

I have a graph G in $\R^4. |V(G)| = 15, vertices are 15 points in R^4. I am trying to build the largest graph possible without significantly changing it's independence number. I have a set of ...
0
votes
0answers
15 views

adjacency in a 4 tree

I have a mesh that is designed to partition a physical space with varying resolution. Basically the size of individual mesh cells varies depending on the location within the mesh (Visual Diagram) I ...
0
votes
0answers
13 views

How to convert an incidence matrix to adjecency list and what would be its time complexity?

Conversion from an incidence matrix to adjacency lists where there are $n$ number of vertices and $m$ number of edges. If it is undirected then every column will have two $1's$ in incidence matrix as ...
0
votes
0answers
31 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
60 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
49 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
24 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
44 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
45 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
22 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
49 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
21 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
76 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
15 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
72 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
20 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
22 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
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.