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
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
18 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
14 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
32 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
27 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
18 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
28 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 ...
9
votes
1answer
107 views
+150

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
10 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
40 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
33 views

unable to implement linear programming for min cut max flow problems

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

Shear transformation and relation above/below in TrapezoidalMap [closed]

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
19 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
29 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 ...
0
votes
0answers
15 views

Maximum Weighted Path in a graph with edge weights [closed]

I have to write an algorithm to find maximum weighted path in an undirected graph with positive edge weights. Can anyone tell me the algorithm?
1
vote
0answers
31 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
66 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 ...
5
votes
2answers
204 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
128 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 ...
2
votes
1answer
22 views

find least multiple formed only of 1's of given number

The problem states that given a number find the least multiple formed only of 1's. If no such number exists then 0 will be the answer. For example for: ...
2
votes
2answers
17 views

Distance in a periodic system

I have two random points in a 3D unit cell and I want to write a computer program that calculates their distance. The system is periodic in all directions in the sense that a point in the unit cell is ...
0
votes
1answer
29 views

Prove that the following program terminates

I have tried searching for the following proof but couldn't find any result. The question is to prove that the following program will terminate when its input x is a positive integer. ...
0
votes
0answers
17 views

Algorithmic question about algebraic varieties and affinely independence

Let $f \in \mathbb{R}[x_1,\ldots,x_d]$ be a polynomial in $d$ variables. Then we can write $f$ as $$ f = \sum_{i=0}^m f_i x_1^i $$ where $f_i \in \mathbb{R}[x_2, \ldots, x_d]$. We may assume $m \neq ...
0
votes
1answer
31 views

How to determine the optimal waiting time?

You are working at a theme park ride and your job is to clip the tickets of guests as they get on the ride. There are some restrictions: Only one ticket can be clipped at a time. The average clipped ...
0
votes
0answers
18 views

What is the best time complexity for this case?

I only want to know if the following system has any integer solution or not. Actually, I do not need to know the solution(s), and only need to know the answer of question "Does the system have any ...
0
votes
1answer
60 views

Appropriate Graph Theory Concepts

I am working in a different domain and I have very basic information about the graph theory concepts. Trying to map my problem into graph theory and looking for the concepts and algorithms applicable ...
2
votes
2answers
55 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
54 views

Are there exact methods to solve the Path cover in bipartite graphs?

We consider a simple graph $G =(V; E)$. The well known Path Cover problem is NP-complete on all graph classes on which the Hamiltonian path problem is NP-complete, including planar graphs, bipartite ...
0
votes
0answers
30 views

Simple curve fitting smoothing algorithm

Is there any conditionally simple algorithm to obtain a best fit (equation) for points set? I have a few points for which I want to have a "smooth" function is constructed that approximately fits the ...
1
vote
2answers
25 views

Robust matching of values to a uniform sequence

I have a sequence of $N$ real numbers $X_i$ that are deemed to be equally spaced. $N$ is small (say $10$ to $20$). Two problems can arise: the spacing isn't perfectly uniform, it can vary in a ...
1
vote
2answers
29 views

Optimal step for drawing Bezier curve

Bezier curves are parametric in the sense that for each dimension their polynomials share common parameter $t$ [1]. To draw a Bezier curve on screen one could increment $t$ by tiny step and calculate ...
0
votes
2answers
27 views

Need help figuring out substitution with recurrence equation. [duplicate]

I need help with an Algorithm text book problem. The problem is the following T(n) = 2T(n/2) + n We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an ...
1
vote
1answer
26 views

Shortest path in a hypercube graph

A* algorithm is one of the algorithm which produces a shortest path in a given graph. I am interested in knowing, is there any property of d-dimensional hypercube which allows the parallel computing ...