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)

3
votes
1answer
54 views

Optimal algorithm for guessing random variable

Let's say you have some unknown quantity $$X\in [0,1]$$ We have N tries to guess the value of X - if you guess $$g_{i}\le X$$ then you capture value $$V_{i} = g_{i}$$ while if your guess is over the ...
0
votes
0answers
23 views

Algortihm to sort by increasing/decreasing

Suppose, you are given a list of $n$ tubs, $T[i]$, $i=1(1)n$. Initially, each tub contains $c[i]$ litre water. Each tub has two taps, from one (if kept open) water enters $x$ litre/minute, and from ...
0
votes
0answers
8 views

FPT algorithm equivalent definitions

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ ...
4
votes
2answers
49 views

Is there any way to compute these sums quickly?

I have a sum of the following form (all numbers are positive integers): $$F(p) = \sum_{x=1}^{N} a_x x^p $$ Where $N$ and all $a_x$ terms are known/fixed constants. However I need to be able to ...
0
votes
0answers
10 views

Identify arbitrer policy of a network component

I would like to identify the formula of the service rate of a network component ARB based on input and output rates of flows crossing it. For instance, I have several flows which cross several ...
-5
votes
1answer
24 views

compute the prefix function π for the pattern ababbabbabbababbabb [closed]

I have the following question as part of my Introduction to Algorithms class. Compute the prefix function π for the pattern ababbabbabbababbabb. In regards to the Knuth-Morris-Pratt Algorithm.
2
votes
0answers
30 views

Minimizing a floor expression

Consider the expression $$ax - b\left\lfloor\frac{cx}{m}\right\rfloor$$ Variables $a, b, c, m$ are positive integers (all of which are known), and $x$ is an unknown integer. The bounds on $x$ are ...
2
votes
0answers
19 views

Stable Marriage algorithms other than Gale-Shapely?

I've looked around lot and I haven't been able to find any algorithms for to the traditional stable marriage problem (I'm not talking about any of its variants like the roommate problem) besides the ...
0
votes
1answer
13 views

size of input of algorithm according to Moore's law

I am reading about algorithms in a book tilted Algorithms by Sanjay DasGupta. Here author mentione as below In 1965, computer chip pioneer Gordon E. Moore noticed that transistor density in ...
0
votes
0answers
16 views

Can the transposition of an arbitrarily-sized matrix be broken up to smaller transpositions?

I'm working with binary matrices. Let's assume that I have an algorithm that is very efficient in transposing 8×8 or 8×16 matrices, but I would like to transpose matrices with an arbitrary size. ...
0
votes
0answers
19 views

When can we say an algorithm is parameter free?

I was reading the paper by Dr. Francesco at http://arxiv.org/abs/1406.3816. The author presented a kernel version of parameter-free algorithm. But, any kernel, AFAIK, takes some parameter(RBF ...
1
vote
0answers
28 views

Will this method always find the maximum of a positive-definite function?

Definitions: A real-valued, continuously differentiable function $f$ is positive definite on a neighborhood of the origin, $D$, if $f(0) = 0$ and $f(x) > 0$ for every non-zero $x \in D$. ...
1
vote
2answers
47 views

Trying to understand a part of the RSA algorithm…

The original paper published mentions this... ...
3
votes
0answers
38 views

What is the area covered by a Random walk in a 2D grid?

I am a biologist and applying for a job, for which I need to solve this question. It is an open book test, where the internet and any other resources are fair game. Here's the question - I'm stuck on ...
0
votes
0answers
13 views

Schedule of maximum number of non-overlapping lectures

Suppose, we have a set $S=\{l_1,l_2,\ldots,l_n\}$ of $n$ lectures for a day. Lecture $l_k$ starts at time $s_k$ and ends at time $e_k$. Two lectures $l_i$ and $l_j$ where $i<j$ are said to ...
2
votes
0answers
49 views

Newton's method on a surface

I am trying to use Newton's method to find the stationary solutions of the integro-differential equation of the form $$\frac{\partial u(r,t)}{\partial t} = -u(r,t) + \int_{\mathbb{R}^{2}}w(r - ...
1
vote
0answers
21 views

Winograd and Coppersmith Algorithm for fast matrix multiplication

I have been trying to understand the algorithm given by Winograd and Coppersmith using Arithmetic Progressions (http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf). I have been successful in ...
0
votes
2answers
45 views

Fast multipole method: help on tutorial

I have some hard time with the FMM (Fast multipole method). I try to understand the basics with: "http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/FMM_tutorial.pdf". So here are my ...
0
votes
1answer
46 views

Prime Number Algorithm

function isPrime(n) { // If n is less than 2 or not an integer then by definition cannot be prime. if (n < 2) {return false} if (n != Math.round(n)) {return false} // Now assume that n is ...
0
votes
0answers
13 views

How to simulate Permanental Point Process

I have simulated a determinantal point process in a square grid using Gaussian Kernel. The Gaussain matrix is decomposed into its eigenvectors and eigenvalues. In core implementation, the elementary ...
0
votes
1answer
28 views

A question about a proof in nonlinear programming book

I have a question about the proof of Proposition 1.2.1 (Stationarity of limit points for gradient methods) in the nonlinear programming book (2nd edition) by Bertsekas. At the beginning of the proof ...
1
vote
1answer
38 views

Curve fit minimizing the sum of the deviation

I'm fitting a curve taking the smaller sum of deviations for each parameter tested, the smaller sum returns me the parameter that gives the best fit. Here is the algorithm for a test $f(x, ...
0
votes
0answers
7 views

Number of iterations of Network Simplex Method

The Network Simplex Method/Algorithm, as used for finding the shortest path in a tree, has complexity $O(m^3)$. How do I prove the algorithm has exactly $\frac12(n-1)(n-2)+1$ iterations?
0
votes
1answer
23 views

Substitution method for solving recurrences

I see this in CLRS: We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence ...
0
votes
0answers
18 views

Can these steps be converted to a mathematical expression using equations/graph theory/Calculus/Set theory/functions/?

Want to convert below algorithm into a mathematical model:- General points 1. Let there be a Connected Directed Graph. G = (V, E) V vertices or nodes E edges. This graph can be seen as a network ...
4
votes
1answer
51 views

Polynomial GCD in the presence of floating-point errors

The crucial requirement for using root isolation methods based on Vincent's theorem is that the input polynomial does not have multiple zeros. One way to remove the multiple zeros is to use polynomial ...
0
votes
0answers
33 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
0answers
20 views

Closest Triplets (Advanced form of Closest pair algorithm)?

So I was trying to solve for the closest triplets from the given number of points(closest in terms of sums of their Euclidean Distances i.e. D(P1,P2)+D(P2,P3)+D(P3,P1) ) ! I thought of proceeding in ...
1
vote
1answer
30 views

Possible to turn any in-fix expression into post-fix with all values on one side?

I remember hearing (correctly or not) that any thing in in-fix notation can be made into post-fix notation with all of the values put on the stack before any operation. $a + b + c \implies a\,b\,c + ...
0
votes
1answer
28 views

A small but quite general question about the optimization

If I have a minimization problem in which both the objective function and constraint are nonconvex. I use gradient projection method to solve the problem iteratively. If we relax the constraint and ...
2
votes
0answers
35 views

Tweaking Reddit's Ranking Algorithm

This image explains how Reddit's Ranking algorithm works. As you know, Reddit is a very high traffic site. Therefore, the post rank decreases quite fast. This algorithm puts emphasis on bringing ...
2
votes
0answers
23 views

Fast multiplication times a fixed constant $A$?

Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$? We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) ...
1
vote
0answers
24 views

Is the alias method “stable”?

The alias method is an algorithm for sampling from a discrete distribution. Let me describe it briefly. First there is a setup phase. You have $N$ values and associated probabilities. You introduce ...
11
votes
1answer
142 views

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
0
votes
0answers
21 views

Bairstow method improvements

I was reading about Bairstow method for polynomial root finding and I find very compelling that it uses just real numbers, as I'm interested in real roots of real polynomials only. However, couple of ...
0
votes
1answer
50 views

Parabola equation in Fortune algorithm for building Voronoi diagram

in DeBerg's "Algorithms and Applications", the part about Voronoi diagram, i have encountered the following formula for parabola arising in the beach line for a site point: $$\beta := y = ...
1
vote
1answer
36 views

Chaikin's Algorithm: Proof of Convergence

Chaikin's algorithm is, in some sense, similar to de Casteljau algorithm in that (in the limit) it produces a curve from a set of control points. There are claims all over the internet that Chaikin's ...
1
vote
0answers
34 views

Shear transformation and relation above/below in TrapezoidalMap

I'm currently reading about point location trapezoidal structure. And i stumbled upon this shearing part. I believe that if we have segment $s$ with endpoints $p_1 = (x_1+\epsilon y_1,y_1), p_2 = ...
0
votes
0answers
23 views

Multivariable gradient descent with approximation of gradinet

This is not a statistics problem I have a vector $$X=[x_1,...,x_{10}]$$ and a cost function $$y=F(X)$$ and my aim in to find the best $X$ to minimize the cost function. It is impossible to ...
0
votes
3answers
18 views

Help with little-oh given $f(n) = n^\epsilon$ and $g(n) = (\lg n)^4$

Problem Given $f(n) = n^\epsilon, \epsilon > 0$ and $g(n) = (\lg n)^4$ find a little-oh relation between $f(n)$ and $g(n)$. Are $f(n)$ and $g(n)$ asymptotically different? Are they polynomially ...
1
vote
0answers
28 views

Is the proposed a different version of the stable marriage problem and a valid Gale-Shapley solution?

my problem is the following. I've two sets A and B with the same numbe of elements. The elements in A can match only with some elements of B. The elements of B have no preferences. Elements have no ...
0
votes
1answer
23 views

Is Levenshtein distance transitive?

If I define some arbitrary similarity metric for Levenshtein distance $$ \mathrm{Sim}(A,B) = \text{true} \mathrel{{>}\mkern-13mu{<}} \mathrm{Lev}(A,B)\le 3 $$ e.g. If $L(A,B) \le 3$ is ...
2
votes
1answer
33 views

Given $n$ cards placed on a round table in upside down fashion, find the minimum operations to make them face upside up?

I have $n$ cards which are placed on a round table such that $1$ is placed between $n$ and $2$ in upside down manner. I need to find minimum number of operations to make them face upside up given ...
0
votes
0answers
17 views

How do you compute the weighted sum of data points for learning the centers of a hyper basis function network (HBF)?

I was reading the following paper on hyper basis function (HBF) (similar to radial basis function RBF network) and was trying to figure out how one learns the movable centers of the hyper basis ...
0
votes
1answer
30 views

Find the minimum number of tanks to hold the maximum quantity of wines, at each tank maximum possible capacity

My business is in the wine reselling business, and we have this problem I've been trying to solve. We have 50 - 70 types of wine to be stored at any time, and around 500 tanks of various capacity. ...
0
votes
1answer
15 views

Longest Contiguous Repeated Substring

I am wondering if a linear time algorithm exists to find the longest contiguous repeated substring in a given string? We could refer to this as the longest "contiguous-double", using the terminology ...
1
vote
0answers
32 views

how to test if Linear Discriminant Analysis (LDA) I implemented works?

I have implemented Linear Discriminant Analysis (LDA) in C by referring various sources. Now, I would like to test the system with a simple configuration. How can I do that? I work on a speech ...
2
votes
2answers
32 views

Strong Induction to prove $T(n)$ is $O(n)$ for $T(n) = T(\lfloor n/3 \rfloor) + T(\lfloor n/5 \rfloor) + T(\lfloor n/7 \rfloor) + n$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions ...
1
vote
0answers
37 views

Special Non-linear recurrence

Problem I have a non-linear recurrence relation given by $$ a_n = a_{n-1}+a_{n-2}+a_{n-3} - \sqrt{a_{n-1}.a_{n-2}+a_{n-2}.a_{n-3}+a_{n-3}.a_{n-1}} $$ Given $ a_1, a_2 $ and $ a_3 $,I have to find ...
0
votes
1answer
73 views

Minimum moves to make all coins have Heads facing up

Given a circular list of coins with Tails facing up. In each move, if we flip coin at position $i$, coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: $H H H T T$ : if I flip ...