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
1answer
16 views

To fast invert a real symmetric positive definite matrix that is almost similar to Toeplitz

It is well known how to solve a Toeplitz system Ax = b, of a matrix A, n x n elements, ...
0
votes
0answers
26 views

Relation between farthest pair of points and closest pair of points in plane

I am writing program for obtaining distance between shortest and farthest pair of points among the given points in plane .I am able to calculate them both the shortest one using divide and conquer ...
-3
votes
0answers
15 views

What are the properties of an algorithm? Or what are different Types of algorithms? [on hold]

Please explain what are the different types of algorithms.
-1
votes
1answer
32 views

Finding the intersections from most intervals [on hold]

I am looking for a data structure that can perform following operations: Insert and delete intervals. At any time, return the intersections [x;y] of most current intervals. For example, if ...
0
votes
0answers
24 views

Piecewise Logistic Function [Satellite Data]

I am working with $16$-day MODIS EVI (satellite) data and I want to fit a Piece-wise Logistic Function through my $23$ EVI data values. The following formula is for the Piece-wise Logistic Function: ...
-1
votes
0answers
18 views

Average operations on a hashtable

Suppose we are given an empty hash table of size $n$, where collisions are resolved by re-hashing (open addressing). Next, $n/2$ items are randomly inserted into the table using a hash function that ...
0
votes
1answer
24 views

Show that running time of Quick Sort is $\mathcal O(n^2)$ when array contains distinct elements and is sorted in descending order

I'm trying to study running time for various algorithms. Now I have QuickSort. How exactly is the running time of an algorithm calculated, I know how quick sort works and the Asymptontic notations. I ...
0
votes
1answer
16 views

Target coordinates given estimate distance from multiple points

I have a device that emits a probe signal, let it be called X. The location of the device is unknown. I have multiple readings of the probe signal in different GPS coordinates spread over an area , ...
0
votes
0answers
13 views

How to compute whether an almost homomorphism is positive or negative when it isn't 0?

A function $f:\mathbb Z \to \mathbb Z$ is almost a homomorphism if there is a $C \in \mathbb N$ (called the additive constant) such that for all $x, y \in \mathbb Z$ $$f(x+y)-(f(x)+f(y)) \le C$$ For ...
0
votes
0answers
58 views

Is there a general solution to the water-bucket logic problem?

Having an infinite supply of water and two containers, one for 3 liters and one for 5 liters, how would you measure 4 liters? Each step in the solution can be one of three things: Fill up a container ...
-2
votes
0answers
18 views

What formula/algorithm would be used to find the significant points of a 2.5D point cloud?

Example of the results of a tool that does something similar. (Link to the tool). Edit 1: Clarification 2.5 dimensional point cloud: A uniform grid of points on the X and Y axes, where the points ...
0
votes
0answers
13 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
0
votes
0answers
11 views

Determine Similarity Algorithm Used

For a known set the comparison values, and result scores, is it possible to determine the similarity comparison algorithm that is being used? When using a Similarity function for SQL Servers ...
2
votes
0answers
19 views

Fast Way to Compute DFT with index summation subject to a constraint

I really appreciate if anyone can help me with this problem. Problem: Let $W_n=e^{\frac{2\pi i}{N}}$ which is the $N$th root of unity. The backward Discrete Fourier Transform of a complex vector ...
3
votes
0answers
24 views

Need to calculate number of valid domain names between two other domain names

A domain name can be 2 to 32 characters in length. The first character can be the characters 'a' through 'z' The last character can be the characters 'a' through 'z' or '0' through '9' The ...
2
votes
1answer
33 views

Puzzle: Determining the structure of a bipartite graph

Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway. Each switch on one end of the hallway has ...
0
votes
1answer
57 views

Is there an O(1) operation to find the Nth digit of Pi?

I'm afraid that 10 minutes of googling isn't finding references to a paper that I thought existed. I remember seeing some years ago a reference to a paper that claims to have proven an algorithm that ...
-1
votes
1answer
43 views

Calculating distance between two squares of a board

Given an $n\times n$ board, for example a chess board 8x8, with the squares ordered in a Little-Endian Rank-File Mapping. Is there a direct way to calculate the distance between two squares using ...
2
votes
0answers
12 views

Accelerated Gradient Descent V.S Nonlinear Conjugate Gradient Descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has ...
0
votes
1answer
17 views

How to find right child in a pyramid number?

A pyramid number: 0 1 2 3 4 5 6 7 8 9 So is there any equation like: ...
3
votes
0answers
58 views

How can I calculate the formula of this fractal-like structure?

I did the following fractal-like structure manually, and I was trying to convert it to a formula (or an algorithm including formulas) to compute some parts of the drawing, but I get lost due to the ...
0
votes
1answer
18 views

How to find maximal dimension abelian subalgebra in finite Lie Algebra?

Is there any well known algorithm how to find maximal dimension abelian subalgebra in finite dimension Lie Algebra? If there is a built-in routine in some computer algebra system, it is the most ...
0
votes
0answers
31 views

Exponentiation of Pascal's Triangle(in matrix form)

I want to find a pattern in subsequent exponentiations of the pascal triangle shown in the form below Matrix P[K+1][K+1]: $$ \begin{matrix} \binom{0}{0} & 0 & 0 & 0\cdots ...
1
vote
1answer
22 views

More efficient algorithm for matrix rearrangement (MatLab)

Say I have the following matrix: $$A = \begin{bmatrix}0.1 & 2 \\ 0.1 & 4 \\ 0.1 & 6 \\ 0.2 & 3 \\ 0.2 & 2 \\ 0.2 & 7 \\ 0.3 & 10 \\ 0.3 & 7 \\ 0.3 & 5 ...
0
votes
1answer
14 views

How to insert a knot in NURBS if it coincides with the first knot?

I want to insert a knot to the knot vector. Currently I use the algorithm from the NURBS book, but it has an assumption that U={0,...0,u_{k},u_{k+1}...,1,...1}, the first knot and the last knot repeat ...
1
vote
1answer
22 views

Solving for a Binary Matrix: A somewhat unusual method needs justification, and mabye interpretation.

Introduction: Define a "Bit Map" to be a matrix whose entries can only be $0$ or $1$. Then numbers above and beside each column and row indicates how many entries are "filled" with a one. For ...
1
vote
0answers
22 views

Coin distribution problem to optimize

There are $N$ users, with each user having a money request. There are $T$ coins, these coins are to be assigned to the user in such a way that its request is fulfilled. Assume each coin may have ...
0
votes
0answers
10 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
0
votes
1answer
11 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
0
votes
0answers
19 views

RSA number sequence encryption

Encrypt the following number sequence $3,9,27$ with key $m=33$ and $r=7$ It's about RSA encryption. How should I encrypt this? Should I find the key $s$ (inverse key) and what then? $r \cdot s + ...
0
votes
0answers
28 views

Degree-Constrained Shortest Path Problem

The following is my problem: Given an undirected graph G(V,E) with cost c(e) associated with every edge e∈E such that c(e)>0 and a vector d=(dv : v∈V) which denotes the maximum degree on each vertex ...
0
votes
0answers
38 views

Minimum spanning tree for a weighted square grid

I have a particular grid with weighted edges connecting each vertex: From this I'm looking for an easy method to obtain a Minimum Spanning Tree. I can easily check columns or rows and remove all ...
-1
votes
0answers
30 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [closed]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
0
votes
1answer
18 views

How do we prove a method is optimal?

This is a very simple question, infact it's so simple that I have no idea how to solve it. We have an ordered list of $n$ words. The length of the $i$'th word is $W_i$. Our goal is to write all the ...
1
vote
1answer
25 views

List all sets of points in a plane that are enclosed by circles with given radius

My problem is: Given N points in a plane and a number R, list/enumerate all subsets of points, where points in each subset are enclosed by a circle with radius of R. Two subsets $S_i$ and $S_j$ should ...
0
votes
0answers
13 views

Anomalous diffusion dynamic exponent calculation

I'm trying to calculate this $\alpha$ (dynamic exponent, I think) from an equation from this wikipedia article. The equation (anomalous diffusion power law): $r^2 \propto t^\alpha$ The problem is ...
-1
votes
3answers
46 views

Algorithm for solving quadratic equation $ax^2 + bx + c = 0$ [closed]

describe the algorithm diagram for a given square equation $ax^2 + bx + c = 0$ $a$, $b$ and $c$ are coefficient which are members of $\mathbb R$. while the equation's definition area for variable $x$ ...
1
vote
0answers
8 views

anomaly detection algorithm problem

I've been trying to determine how to detect point-anomalies given window-anomalies. In more detail, I know for each 30-day window whether it contains an anomaly. For example, window 1 starts at ...
2
votes
1answer
35 views

Proving optimality of simple greedy algorithm

Professor Xavier (yeah, the one from X-Men) wants to drive from Reno to Newark. His gas tank, when full, holds enough gas to drive $n$ kilometers. The professor has a map showing the gas stations ...
2
votes
1answer
18 views

Problem with my simple algorithm to count repetitions

We have two arrays $A,B$ with sizes $n,m$ respectively. We know that $m \geq n$. We also know that no array contains the same number twice. Propose an algorithm that prints how many numbers appear in ...
0
votes
0answers
24 views

FFT Hyperbolic Distribution R

This is my first posting so forgive me if it is not 100% in line with this forum's best practices. I am completing an analysis using ICA as the decomposition technique. I am keeping 4 of the 10 ...
0
votes
1answer
19 views

Calculate the asymptotic growth of a sum that contains log or binom

I'm looking for a basic explanation how to calculate the asymptotic growth of sums. Take for example this one: $\sum_{i=1}^{lg(n!)} 2^{n^2}$ or this one: $\sum_{i=0}^{n} {n\choose{i}}$ The ...
0
votes
1answer
39 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
1
vote
0answers
20 views

How to properly detect rows to be swapped in a Gaussian elimination?

I'm trying to describe an algorithm for solving solvable linear systems. The Gaussian elimination is pretty straightforward in terms of adding multiples of rows. However, consider the following ...
1
vote
0answers
14 views

Planar nearest neighbor search for many points.

I have two sets of points on the plane, A and B. For every point in A, I would like the k nearest points in B. The naive approach is for each point in A having a linear selection to choose the kth ...
2
votes
3answers
34 views

Prove correctness of simple greedy algorithm to find max

We have $2n$ values $x_1,x_2,x_3,\ldots,x_n$ and $y_1,y_2,y_3,\ldots,y_n$ such that the pair $(x_i,y_i)$ represents the location of a city $i$. Assume there is no straight line that goes through all ...
1
vote
0answers
19 views

Algorithm for high contrast

Using this algorithm I can increase contrast but applications like Paint.Net can increase contrast significantly. For example it can convert to (by setting contrast to 100 and brightness to 100, ...
1
vote
1answer
127 views

Graham scan with collinear points

I'm having some trouble understanding the Graham scan algorithm as described in Wikipedia. Particularly, I don't understand how to handle collinear points. Consider these points as a simple example: ...
0
votes
1answer
41 views

Biggest n that can be solved in one second

I have been given the following problem: What is the largest n for which one can solve in one second a problem that requires $(\log_2(n))^2$ elementary operations, where each elementary operation is ...
0
votes
2answers
37 views

Worst case binary search

Suppose you play a game with a computer program where you guess a number between 0 and 1 and the computer uses binary search to search for your number. My question is what is the best number to ...