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
5 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
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 ...
-1
votes
0answers
154 views

need mathematical expression for the below [on hold]

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
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
13 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
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 ...
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 ...
9
votes
1answer
104 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
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
543 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
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 ...
3
votes
0answers
126 views
+50

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 - ...
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
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 ...
2
votes
1answer
360 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 ...
1
vote
0answers
23 views

Shear transformation and relation above/below in TrapezoidalMap [on hold]

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
2answers
485 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
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
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
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 ...
2
votes
1answer
395 views

In context of graph search,what is mini-max principle

after doing some Google search i am not able to find an effective and understandable explanation of mini-max principle,anyone please explain it to me.
5
votes
2answers
203 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. ...
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 ...
8
votes
2answers
295 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
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. ...
5
votes
0answers
127 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 ...
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 ...
0
votes
3answers
38 views

A lower bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal in the sense that is it a lower bound for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ ...
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?
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 ...
2
votes
2answers
28 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
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
0answers
21 views

Graphs and MST proof [closed]

Given a graph $G$ with the set $S$ which the distance between each vertices is $w_i$. Now we add $k$ vertices to $G$. Is it possible that $W\{MST(s+k)\} < W\{MST(s)\}$? $W$ is the sum of edges ...
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. ...
2
votes
2answers
189 views

Number of Basic Operations - Grade School Multiplication Algorithm

I am currently taking an online course and am confused by this question regarding the Number of Basic Operations. Problem: Count the number of these basic operations performed as a function of the ...
2
votes
1answer
52 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 ...