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
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$. ...
4
votes
1answer
568 views

Determining partial derivatives and cross products for bicubic interpolation using function values only?

I'm trying to implement a bicubic interpolation algorithm. In order to calculate the interpolated values, I need to calculate sixteen coefficients used in the calculation process - and that's where ...
0
votes
2answers
31 views
1
vote
1answer
27 views

Finding Automorphisms of Irregular graph through Regular Sub-Graphs.

Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph. Description and ...
3
votes
1answer
371 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
3
votes
0answers
31 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 ...
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 = ...
4
votes
1answer
165 views

Richardson's theorem for constants

It's known that there is no algorithm for deciding for any elementary function is it identically zero or not (http://en.wikipedia.org/wiki/Richardson%27s_theorem ). But if I consider only constants - ...
3
votes
1answer
623 views

Does the greedy method guarantee max flow in a directed tree?

Consider a directed tree $G$ with a root node $s$. Let $s$ be the source node of $G$ and its leaves the sink nodes (call these leaves $t$). (And of course edges have their respective capacities like ...
3
votes
1answer
289 views

Is there any efficient algorithm for finding subgroups of a given finite group?

I am implementing an algorithm which finds every subgroup of given group. Here's my algorithm. Let $G$ be a group of order $n$ with elements $g_1,\cdots,g_n$. Then I consider each $\langle ...
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
43 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
28 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 ...
1
vote
2answers
84 views

Asymptotic Notations in Limits

Can the asymptotic notations, like Big O, be defined using limits? example: $\lim_\limits{x\to\infty} (f(n)/g(n))=c$ for defining $f(n)=O(g(n))$ If not, why??
4
votes
1answer
342 views

How many non-isomorphic permutation selections are on an arbitrary N x N square matrix with rotations applied?

My question is an extension to a classic one: On a square $N \times N$ grid, select exact $N$ cells that satisfy condition: only one cell selected in same row and column. How many solutions will ...
0
votes
1answer
24 views

Converting $f_{2}$ to $O(f_{2})$ that isn't $f_{1}$

So the actual problem I'm trying to figure out is Find functions $f_{1}$ and $f_{2}$ such that both $f_{1}(n)$ and $f_{2}(n)$ are $O(g(n))$, but $f_{1}(n)$ is not $O(f_{2})$ I know that if I had ...
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 ...
0
votes
0answers
95 views

Two Counterfeit Coins Out of n Coins

I have an amount of $n$ coins and I know that $n-2$ of them are 'regular' and $2$ are fake, as one is lighter than the rest and the other is heavier than the rest, and the sum of both of them is as ...
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 ...
9
votes
2answers
7k views

Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then. The way I ...
6
votes
2answers
275 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
1
vote
1answer
33 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, ...
2
votes
2answers
60 views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length ...
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?
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 ...
-1
votes
0answers
161 views

need mathematical expression for the below [closed]

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 ...
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 ...
2
votes
2answers
3k views

Square three digit numbers, the efficient way

I would like to square a three digit number in my head. Now I know that the formula is $$ ( X + r ) ( X - r ) + r^2 = X^2 - rX + rX - r^2 + r^2 = X^2 $$ Where $\,r\,$ is a number such that $\,X + ...
2
votes
2answers
3k views

What is the best strategy for a guess-my-number game?

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure: Player B decides on a number between ...
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 ...
0
votes
0answers
28 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 ...
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
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
1answer
327 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
0
votes
2answers
554 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
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 + ...
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
20 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 ...
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 ...
2
votes
1answer
365 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
0
votes
2answers
497 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
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
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 ...