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
0answers
16 views

Minimum sample size [on hold]

I have a survey of $n$ distinct opinions and their outcomes rounded to percentages. How can I compute the minimum number of sample size? For example IF resuls are 0.33, 0.33, 0.33 then the minimum ...
0
votes
0answers
15 views

Second-price auction task

I've got a rather interesting task... Just imagine that we have exchange where trades only one product - apples. We also have N customers, which would like to buy some units of product: each of ...
0
votes
0answers
17 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 ...
0
votes
0answers
19 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
40 views

Trying to understand a part of the RSA algorithm…

The original paper published mentions this... ...
3
votes
0answers
33 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
10 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
44 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
12 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 ...
-2
votes
0answers
30 views

How many ways can you draw 17 cards from a deck of cards? [on hold]

Kaggle verification, the answer doesn't seem to be right, no matter what i enter.
0
votes
1answer
32 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
39 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
8 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
24 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
34 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
6 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
20 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
16 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
42 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
29 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
19 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
30 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
22 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 ...
10
votes
1answer
134 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
12 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
41 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
35 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
votes
0answers
36 views

unable to implement linear programming for min cut max flow problems [closed]

iam trying to solve codechef problem using linear programming(simplex). https://www.codechef.com/problems/CHEFBOOK i understood the concept of linear programming , but i was unable to implement. I ...
1
vote
0answers
25 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
21 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
27 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
21 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
32 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
15 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
27 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
13 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
28 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
30 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
33 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
67 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 ...
4
votes
2answers
206 views

Finding a recurrence for a sum

I am trying to implement the following sum using a programming language: $$\sum_{i=1}^N a^i i^r$$ where $N$, $a$ and $r$ are integers. The problem is, I cannot find a suitable way to do this. ...
1
vote
0answers
19 views

Show that splitting an edge in a flow network yields an equivalent network.

Need help with this question from my Intro to Algorithms book: Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge ...
0
votes
0answers
19 views

Minimum spanning tree of this graph

I'm trying to find a minimum spanning tree for this graph below using Krusal's and Prim's algorithm. This is what I got for each algorithm: Krusal: visited= ...
3
votes
0answers
61 views

Find a real number with even digits in a given base

A real number x ∈ (0,1) is called b-good if x converted to any base b >= 2 has all digits ...
2
votes
0answers
37 views

Dishwasher Unloading: Optimal Algorithm

Suppose you are unloading cutlery from a dishwasher containing $4$ types of cutlery: teaspoons, tablespoons, knives and forks. Each type has 8 pieces. You hang the cutlery on a rack with two sides. ...
5
votes
0answers
132 views

Apartness of reals and algorithm exctraction

I am trying to wrap my head around the notion of apartness in constructive mathematics and it turns out I lack understanding miserably. I would like to use as elementary notions as possible, in the ...