Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

2
votes
0answers
71 views

Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...
2
votes
0answers
626 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
2
votes
0answers
71 views

Petri net analysis (attainability)

how to analyse safe petri net for attainability? (i need algorithm) I have an oriented multigraph $\mathbb{G}$. $A$ - adjacency matrix. $m$ - the count of input elements. $n$ - the count of ...
2
votes
0answers
98 views

Maximum Flow in Dynamic graphs

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in $G$ now new node added/deleted with related ...
2
votes
0answers
426 views

Computing the Minimum Number of Squares Needed to Sum to $n$

I am aware of Lagrange's Four-Square Theorem, which states that every positive integer can be written as the sum of at most four squares. Clearly some integers require fewer squares. Does there ...
2
votes
0answers
137 views

Find most densely located $K$ points among $N$ ($N \gt K$) points in two dimension

Suppose I have $N$ points in two dimensional space. I want to know which $K$ of them ($K \lt N$) are located most densely (so that area of Convex Hull of points or sum of squares within cluster is ...
2
votes
0answers
80 views

Is there a use for this technique?

I remember reading once about the following algorithm: Consider a lattice grid and $N$ houses situated at grid points, in which live the town elders. They want to choose a lattice point location ...
2
votes
0answers
256 views

Bell-like recurrence

Let $$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$$ $$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$$ I'm interested in computing $S(n)=A(n)+B(n)$ ...
2
votes
0answers
69 views

Algorithm to predict next 3D points

For example, having this data: year x/y/z 2007 10/20/70 2008 20/10/70 2009 30/10/60 2010 40/10/50 2011 40/15/45 We want to predict what will be the x/y/z in ...
2
votes
0answers
261 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
2
votes
0answers
94 views

Probabilistic analysis of two algorithms

Let $f$ be a binary function programmed at random; i.e. for any $x$ in its domain, $f(x)$ equals some $n$-bit value initially chosen at random. Such a function has the nice property that for any two ...
2
votes
0answers
107 views

What does it mean if a sequence is indexed beyond its bounds?

I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences. Part of the algorithm involves ...
2
votes
0answers
161 views

calculate the rate of change

I am trying to calculate the change frequency for a set of data. Each bit of data has the date-time it was created. I would like to say for a specific set of data the change frequency is hourly, ...
2
votes
0answers
384 views

algorithm for the intersections of a line and an ellipse in 2D

I am looking for an algorithm for finding the intersection of a line and an ellipse. I have the line in the form $ax+by+c=0 \qquad(1)$ and the ellipse in the form $Ax^2+Bxy+Cy^2+Dx+Ey+F=0 ...
2
votes
0answers
682 views

QR with column pivoting

Golub and van Loan's algorithm 5.4.1 for QR factorization is suitable as a rank revealing algorithm. The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
2
votes
0answers
64 views

Iterative Compounded Growth Calculation

Hello I would like to develop a quick algorithm for computing compounded change over an arbitrary period $T$. I'll illustrate with an example. Suppose I have $N$ data points as follows: $$(x_0, t_0, ...
2
votes
0answers
94 views

What's the fastest way to solve these equations with powers in a field?

This is for an algorithm I'm working on. Perhaps we can work together! We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find ...
2
votes
0answers
35 views

What is this method called of calculating corrections for calculated values from measured values?

I am dealing with a piece of software which calculates temperatures, and corrects these based on measurements (which may be in error) as follows:- The difference between the corresponding calculated ...
2
votes
0answers
417 views

Set of segments a vertical ray intersects

The problem is 10.6a from Computational Geometry: Algorithms and Applications. We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, ...
2
votes
0answers
529 views

Algorithm for the transitive reduction of a DAG

I'm looking for an algorithm for the transitive reduction of a digraph (a DAG in fact). The wikipedia article displays a formula R- = R - (R × R+) — where R- is the transitive reduction of ...
2
votes
0answers
132 views

The $n$-shortest lattice vectors problem in $\mathcal{R}^2$

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows: Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a ...
1
vote
0answers
13 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
1
vote
0answers
47 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
1
vote
0answers
18 views

Fast way to find the sum of LCM of the given range of numbers?

I want to find the sum of LCM of a given range of integers.For example: Input: 5 Output: LCM(1,5)+LCM(2,5)+LCM(3,5)+......LCM(5,5)// ie. 55 The method I use ...
1
vote
0answers
29 views

Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
1
vote
0answers
26 views

Lowest sum of 2 sets of number pairs

I am given a set of unique integers $n$. I need to compute the smallest sum $s$ such that there are two different pairs of integers $(x1, x2)$ and $(y1, y2)$ where $x1 < x2$ and $y1 < y2$ and ...
1
vote
0answers
38 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
1
vote
0answers
27 views

directed simple graph, all paths from node $ v_0 $ to an other node $ v $, MATLAB

consider a directed simple graph $ G=(V,E) $ with $ V=\lbrace v_0,v_1,\ldots,v_k \rbrace $ and adjacency matrix $ A=(a_{ij}) $, where $ a_{ij}=1 $ means, that there is an arc from node $ v_i $ to node ...
1
vote
0answers
24 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
1
vote
0answers
58 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
1
vote
0answers
57 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
0answers
29 views

Iterative Mean, Covariance Algorithm Convergence

The problem is to show that the following iterations converge to the vector $\mu$ and the matrix $\Sigma$. We have data in the form of nx1 vectors $\mathbf{Q}_k$, $1 \leq k \leq N$ where ...
1
vote
0answers
46 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
1
vote
0answers
20 views

Enumerating certain size 15 square matrices

This is an attempt to tackle A zero sum subset of a sum-full set by complete enumeration. I am looking for an algorithm which will efficiently (i.e. within reasonable time, several hours at the most) ...
1
vote
0answers
27 views

Assign most people their first choice based on a list of preferred choices

Given a list of choices (say 100), each person in a list (say 30) has to choose 5 choices in the order they would like them to be assigned. How would I assign each person a choice making sure as many ...
1
vote
0answers
23 views

A good book with algorithmic puzzles with solutions (not of kind “how to pass and IT interview”)

can you please advise me a book with algorithmic and mathematical (IT-oriented) puzzles. But I want not one more book of kind "How to pass an interview in Microsoft / Google / any other big company" ...
1
vote
0answers
28 views

Proper subsets with closest sum

Suppose you have sets $A$ and $B$ of positive reals, with $sum(A) = sum(B)$. Is there an efficient algorithm to find proper subsets $A_1$ of $A$ and $B_1$ of $B$ such that $abs(sum(A_1) - sum(B_1))$ ...
1
vote
0answers
24 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
1
vote
0answers
31 views

Searching a common substring presence

Some time ago during an interview for software developer position I was asked the following task: Supposing we have two immense texts (like till million of characters each) and we are asked whether ...
1
vote
0answers
34 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
1
vote
0answers
23 views

number set with non-adjacent digits

I'm not sure such thing exists, or even if I'm asking for a valid thing, but I'll do my best describing it. At least the thing I want is similar to Gray code, so should be valid. So, I want to know ...
1
vote
0answers
34 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
1
vote
0answers
20 views

Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$ \leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I ...
1
vote
0answers
37 views

Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be: $ x*y = (x \uparrow y) \bmod n $ where $ \uparrow $ is the symbol for tetration. ...
1
vote
0answers
20 views

Ideal shrinking of discrete randomness source

I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to ...
1
vote
0answers
31 views

Mathematical formulation of Algorithms

Is there a way to formulate the definition of algorithms mathematically, so that the effectiveness and completeness of algorithms is justified.
1
vote
0answers
59 views

3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
1
vote
0answers
36 views

How do I use the digit-by-digit square root algorithm in a base-n context, e.g. $2^{16}$?

I have to take the square root of a number so large that there is no way to compute it directly. I thought if I divided it up into smaller pieces, I might be able to get this done in as few steps as ...
1
vote
0answers
20 views

Factorisation algorithm for polynomials in several variables over $\mathbb{Z}$.

What algorithm is used by a CAS to decide how to factor a polynomial in several variables over $\mathbb Z$?
1
vote
0answers
35 views

How to find the lengths of the shortest paths in a directed graph in $O(m)$ steps?

Let $G = (V,A)$ be a directed graph for which it is true that if $(v_i , v_j) \in A$, it is implied that $i < j$. Question: How does one construct an $\mathcal{O}(m)$ algorithm to find the ...