Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

2
votes
0answers
49 views

What kind of numerical methods are best applicable to this?

I'm wondering: what would be the best numerical method for solving a nonlinear integral equation of the form $$f(x) = a(x) + \int_{-A}^{A} K(x, t, f(t)) dt$$ where $f$ is the unknown function, a ...
2
votes
0answers
210 views

Proof of the optimality of A* algorithm

In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105. However, I cannot ...
2
votes
0answers
179 views

all eigenvalues of a large sparse symmetric matrix

my question is similar to how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors however i wish to be more concrete and ask if one can, on a standard PC (e.g. a ...
2
votes
0answers
95 views

The Edge Set Grown in Kruskal's Algorithm

Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let ...
2
votes
0answers
51 views

What is the pagerank of the given nodes?

Given nodes $A,B$ and $C$. with $A \rightarrow A$, $A\rightarrow B$, $B \rightarrow B$, $C \rightarrow A$, $C \rightarrow C$ where the arrows represent outgoing links from left and incoming links to ...
2
votes
0answers
27 views

Broken disk head

Broken disk head: We would like to read 1 byte = sequence of 8 bits from a disk, starting from bit 0. Our disk head reads 1 bit at a time. Disk head can only move forward, but after reaching bit 7 ...
2
votes
0answers
123 views

Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it, which contains all edges leading into it on all paths from a ...
2
votes
0answers
140 views

Effective model for calculating momentum or growth rate for a time series

I have a series of numbers tracking the performance of an entity on any given day. It's nothing but a simple integer for each date. For example, here's a series for Entity "X" ...
2
votes
0answers
47 views

Finding number of smaller elements for each element in an array

I am stuck in this problem. Can anyone help me. Thanks. Consider an array 'A' of 1st n natural numbers randomly permuted. Consider an array B formed from array A as given below B(k) = number of ...
2
votes
0answers
163 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
2
votes
0answers
81 views

Iterative method for solving linear equations that generate narrower and narrower bound on the solution

I know that there are many methods that solve linear equations $Ax = b$ iteratively. But I'm curious if there's one that in each iteration tells us a bound on the solution. Specifically, assume $Ax^* ...
2
votes
0answers
315 views

Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $$||f-G_m(f,D)||>Cm^{-1/2}|f|_{H}$$ ...
2
votes
0answers
374 views

Logistic regression algorithm in Casio and Texas Instruments calculators

When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form $$f(x) = \frac{c}{1+ae^{-bx}} $$ The problem I have (when teaching in a class where both types of ...
2
votes
0answers
163 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
2
votes
0answers
320 views

Incremental algorithm for variance of geometric mean

For our application, I'm trying to find a memory-efficient, incremental algorithm to maintain variance of geometric mean. This "online algorithm" on Wikipedia seems excellent, ...
2
votes
0answers
96 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
2
votes
0answers
75 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
2
votes
0answers
55 views

Algorithms for the Antikythera Mechanism

I am working on a little computer program, and i was wondering if any one knew of any collections of all the calculations done and their associated mathematical algorithms? The algorithms dont have ...
2
votes
0answers
38 views

How to pick correct sign on matrices such that their sum is a nonnegative matrix?

Given a set of matrix $M_i$, by picking a sign coefficient $S_i\in\{-1,1\}$ How can I effectively find a combination that the sum $M^*= \sum_{i=1}^N S_iM_i$ is a nonnegative matrix. i.e. ...
2
votes
0answers
164 views

google page rank algorithm with range of values

According to the wikipedia article, the iterative google page rank algorithm is defined as follows: Can this be modified to include a range of values, not just binary, and would it look something ...
2
votes
0answers
329 views

Mathematics in the “ The Art of Computer Programming”

I don't know of this the right place to ask this type of question and hence I apologize (in advance) for any inconvenience. Here is my question: I have studied Concrete Mathematics by Knuth, Graham ...
2
votes
0answers
98 views

Why is there no alpha-approximation algorithms for k-center problem where $\alpha<2$?

On page 39 of Design of Approximation Algorithms, the author argues this case with the dominating set problem. I can't understand it. A dominating set problem is a special case of the $k$-center ...
2
votes
0answers
457 views

Counting couples having least common multiple less than a number

Let f(n) be the number of couples (x,y) with x and y positive integers, $x\leq y$ and the least common multiple of x and y equal to n. Let g be the summatory function of f, i.e.: $g(n) = ...
2
votes
0answers
75 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
691 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
73 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
103 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
565 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
142 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
83 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
270 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
71 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
275 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
200 views

Finding position in a tree based on node number

Let us assume my tree starts with $1$ node, then each node has $2$ nodes beneath it. Let us also assume the top node of the tree is numbered $1$, and node $2$ and $3$ are directly beneath it. An ...
2
votes
0answers
95 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
169 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
399 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
799 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
95 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
446 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
537 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 ...
1
vote
0answers
11 views

Heuristic & Approximation algorithms

I just came to know the definition of r-approximation algorithm. I just want to know whether infinite-approximation algorithm is a heuristic algorithm? Is heuristic algorithm is an ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
1
vote
0answers
29 views

Complexity of combination method

I have a question about complexity of combination two methods. Assume that I have method A with its complexity is $O(n)$ and second method that has complexity is $O(n^2)$. In which, n is number of ...
1
vote
0answers
26 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
0answers
44 views

longest integer vector partition

I'm trying to solve the following question: Given an nonegetive integer vector $\overset{\rightarrow}{m}=(m_1,m_2,\ldots,m_k)$, how to find the longest distinct integer vector sequence ...
1
vote
0answers
163 views

Count arrays with GCD as D

Given N ,I need to count the number of array of integers which satisfy the following conditions : ...