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)

2
votes
0answers
22 views

Completely autonomous traversal of a planar graph

I have to program an autonomous robot to traverse through a grid given in the following figure. But the main problem is that the nodes to visit is not known beforehand, it will be received by the bot ...
0
votes
2answers
22 views

Linear regression: zero indexed?

I have a set of data corresponding to profit per month: Dec -> 1726 Jan -> 1252 Feb -> 1472 Mar -> 1165 ... And a linear regression algorithm that ...
8
votes
0answers
53 views

Solving general (dis)entanglement puzzles

What is the state of the art in (modelling and) solving a general (dis)entanglement puzzle? The following picture shows a nice example: There is a project called "The Untangler", which seems to be ...
1
vote
1answer
446 views

Coloring problem on directed graph

Let $D=(V,E)$ a directed graph. How to color nodes of $D$ in white and black such that: No two white colors are adjacent, and For each black node there exists at least one white node which is ...
0
votes
0answers
23 views

Minimum number of equal moves to reach the end of destination if there are some bricks in the path?

I have given some numbers $A_1, A_2, A_3, ..., A_n$. I have asked that if I have to reach from 0 to $A_n+1$/$\ge$$A_n+1$ , what is the minimum number of equal jumps I have to make in order reach my ...
1
vote
2answers
45 views

$2^{O(\log \log n)} = O(\log n)$ prove or disprove

I need to prove or disprove this: $$2^{O(\log\log n)} = O(\log n)$$ I haven't found anything like that through search. I would like to have some help. Thanks.
6
votes
0answers
65 views

Different geometric figures from trapezoids

I have recently bought a very interesting a Brazilian kit to my kid to build mosaics: It is easy to see that I am able to generate equilateral triangles, hexagons, parallelograms, Rhombuses etc. ...
1
vote
1answer
39 views

Greedy Strategy for assigning skis to skiers

We have n skiers with increasing heights $p_1,...,p_n$ and n skis with increasing heights $s_1,...,s_n$. We want to minimize the average difference between the height of a skier and his assigned ski. ...
3
votes
2answers
91 views

Squeezing primes

Any positive odd number $n$ can be coded one binary digit smaller by the rule $\frac{n-1}{2}$ and that's obviously the best squeeze: a bijection from $\mathbb N$ such that $f(n)\geq n$. I'm looking ...
2
votes
1answer
32 views

Knowing which factorization algorithm to use

There are many ways of factorization available, e.g. trial division, Pollard rho, elliptic curve factorisation, the general number field sieve. But for what ranges of numbers are such algorithms ...
2
votes
0answers
27 views

Why does this algorithm converge?

Consider the following problem. Let $p_1, \dots, p_n \in (0,1)$ such that $\sum p_i = 1$. Let $m > 0$ such that $$ q_i := p_i + m \frac{p_i \log(p_i)}{\sum p_k \log(p_k)} < 1 $$ Suppose ...
5
votes
0answers
33 views

How to quantify the “uniformity” of a distribution of holes in a surface

I want to try to quantify if the distribution of holes over a surface is uniform or not. The holes can have any given shape and can be arranged in any way over the surface. Three examples are ...
1
vote
2answers
57 views

Leaping frog algorithm

I need your help with a riddle, I need to find the best algorithm to catch a frog, The frog is on the Natural numbers, it begins at point L, each time it goes K Leaps right (means if it was at point ...
0
votes
0answers
9 views

How to find error bound of dual Space Saving algorithm?

Space Saving algorithm is an approximation algorithm for approximating frequencies of items in data stream. Suppose a continues stream of elements [$e_1,e_1,e_2,e_1,e_5,e_3....$], Space Saving ...
0
votes
0answers
43 views

How to find the basic elements of a set?

I have a set of some proposition for example($a_1,a_2,\cdots,a_n$). Some proposition depend on others(for example, $a_1,a_2=>a_3$). I want to find a subset of the proposition to be defined as ...
2
votes
0answers
22 views

An implement of Constructing elliptic curves of prescribed order

In the Reinier Bröker's Phd thesis——Constructing elliptic curves of prescribed order(2006), he present a effective way to generate a elliptic curve with a given order N. And the heuristic run time of ...
0
votes
0answers
110 views

Converting a 1st order non-linear recurrence to a 2nd order

I came across this problem while reading Blelloch's Prefix Sums and Their Applications: Show how the recurrence $x_i = a_i + b_i/x_{i-1}$ where + is numeric addition and / is division, can be ...
0
votes
0answers
25 views

Calculate stack size in iterative depth first algorithm (DFS)

I am trying to detetermine stack size in iterative depth first algorithm (DFS). My algorithm goes as follows: Push starting vertex into stack. Pop element from stack. If element was not visited yet, ...
2
votes
2answers
28 views

Simultaneous diagonalization

Given two symmetric matrices $A,B\in\Bbb R^n$ how can we find if they are simultaneously diagonalizable? If they have such property how can we find $U$ such that $UAU'$ and $UBU'$ are simultaneously ...
0
votes
1answer
68 views

How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?

How can we draw $14$ squares to obtain an $8\times8$ table divided into $64$ unit squares? Notes: -The squares to be drawn can be of any size. -There will be no drawings outside the table.
1
vote
1answer
30 views

Pth Root of Polynomial Over Finite Fields for Yun's Algorithm

While I was implementing Yun's algorithm in java, I could not figure out an algorithm to find the $p$th root of a polynomial in $\mathbf{F}_p$ where the polynomial is a perfect power of $p$. How would ...
0
votes
0answers
76 views
1
vote
1answer
13 views

Find if two multi-dimensional parallelograms intersect

Let $P$ be the $n$-dimensional cube $$P=\{(x_1,...,x_n):x_i\in [-1,1]\forall i\}$$ Let $Q$ be an $m$-dimensional cube defined by end points $[a_i,b_i]$ ...
4
votes
1answer
97 views

What is the minimum number of squares to be drawn on a paper in order to obtain an 8x8 table divided into 64 unit squares? [closed]

What is the minimum number of squares to be drawn on a paper in order to obtain an $8\times8$ table divided into $64$ unit squares. Notes: -The squares to be drawn can be of any size. -There ...
2
votes
0answers
60 views

Compute shooting targets for the gunmen

This is an extension of the well known "3 gunmen puzzle": N gunmen with hitting probabilities in (0,1] take turns to shoot at each other. Firing order is fixed (gunman 1 shoots first, then gunman ...
2
votes
2answers
64 views

Binary number with base $-2$ (minus two) arithmetic algorithm

I have a number X represented as a sequence of $a_i \in {0,1}$ so $$X = \sum_{i=0}^{N-1} a_i(-2)^i$$ where $N \in \{ 1, \ldots, 100000 \}$. I need to find an algorithm to produce a number $Y = -X$ ...
0
votes
0answers
18 views

Can 'tabu search' be considered a nature inspired algorithm?

Tabu search has been used widely alone or in hybrid strategies with other nature inspired algorithms such as simulated annealing, hill climbing... My question is, the strategy of tabu search that do ...
6
votes
0answers
52 views

Find a region with maximum sum of top-K points

My problem is: we have $N$ points in a 2D space, each point has a positive weight. Given a query consisting of two real numbers $a,b$ and one integer $k$, find the position of a rectangle of size $a ...
1
vote
0answers
27 views

Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm

This paper by a Russian gentleman gives an optimal (?) algorithm for $3$ $\times$ $3$ matrix multiplication. It beats a previously known method by reducing the total number of discrete operations from ...
5
votes
1answer
86 views

Does this algorithm for Graph Realization work?

A sequence of integers $d_1, \dots, d_n$ is called graphical if there exists a simple graph $G$ with it as its degree sequence. Deciding if a sequence is graphical is called the Graph Realization ...
0
votes
1answer
24 views

Prove verification given method of a shortest path tree with by giving node's predecessor and shortest distance is correct.

This is question from CLRS Chapter 24. Actually how to verify is already answered as below. How to verify a shortest path tree with O(V+E) running time by giving node's predecessor and shortest ...
0
votes
1answer
21 views

Algorithm to recompute the shortest path after edge weight decreases

Let duv be the length of the shortest path from u to v in a directed graph. Suppose that the length of a single edge (x, y) decreases from cxy to c'xy. Design an algorithm to recompute all the duv's ...
0
votes
0answers
15 views

Design a greedy algorithm to find the set of vectors that are linearly independent and have maximum total weight

You have a collection of n real k-dimensional vectors. Each vector has a weight attached to it. The vector weights are an input of your algorithm and are not necessarily related to the vector length ...
1
vote
0answers
26 views

When the integers got upset.

I have been stuck with this problem for quite large time. https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/when-the-integers-got-upset/. In short what is says is: There are two arrays ...
3
votes
1answer
33 views

Algorithms for a “Travelling Salesman with radius / time limit”?

I can't talk about my real-world situation I need this for, but imagine you walk around a warehouse that has things with RFID tags scattered around in it, and you have ten minutes to get within 2m of ...
0
votes
0answers
43 views

How to solve division one digit at a time?

I’m developing a computer program and I’m trying to work out some arithmetic algorithms for working with very large numbers. So far I have worked out a plan for addition, subtraction, and ...
2
votes
2answers
65 views

Given $2n$ points in the plane, prove we can connect them with nonintersecting segments

Given $2n$ points on the plane such that no three points lie on one line. Prove that it is possible to draw n segments such that each segment connects a pair of these points and no two segments ...
0
votes
1answer
28 views

Two-sigma notation k-means clustering

I have referred to this question: Two sigma notation, to get an understanding of how two-sigma notation works. But this is insufficient for my purposes. I am looking at a k-means clustering ...
1
vote
2answers
24 views

Find algorithm for converting number to Balanced ternary

I have this math question, I have to find an algorithm that is able to convert any number to balanced ternary. Balanced ternary is like ordinary base $3$ in the sense that the positions are ...
0
votes
0answers
9 views

GMRES method In matrix, how to set $x_0$

I am not sure if my question is reasonable or not, but because I'm not good at matrices I had to ask this question in here. This is the algorithm of The Generalized Minimum Residual Method (GMRES). ...
1
vote
1answer
16 views

Levenshtein distance calculations

What is the correct Levenshtein distance between the following strings? hahaha ahahah These sites report different values: ...
1
vote
1answer
24 views

Scheduling problem on bipartite graph

Consider a bipartite graph $(G, U, V)$. Each $v$ in $V$ represents a soccer team, and each $u$ in $U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
3
votes
1answer
45 views

Bicolour Towers of Hanoi

I am trying to solve Bicolour Towers of Hanoi problem. It is a variation of classical Towers of Hanoi problem. There are $3$ pegs (let's call them $A$, $B$, $C$) and $N$ disks on peg $A$. Disks have ...
0
votes
0answers
38 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of ...
1
vote
0answers
23 views

Is Richardson iteration algorithm backward stable?

How do we analyze the numerical stability of Richardson iteration algorithm? Can we say it is backward stable?
0
votes
0answers
12 views

Is there a way to find the limit of a function algorithmically?

Is there a certain sequence of instructions that one may use to find the limit of a function? I know that, $\lim_{x \rightarrow c}f(x)=L$ iff $f(x)$ gets arbitrarily close to $L$ as $x \rightarrow c$, ...
0
votes
0answers
92 views

More intuitive/easier explanation for Knuth's division algorithm needed

Knuth's division algorithm, here refers to the D algorithm mentioned in TAOCP written by Donald Knuth in Volume 2 (Semi-numerical algorithms) Section 4.3.1 I have been trying to understand the ...
2
votes
0answers
28 views

Probabilistic methods and equations over $m$-dimensional space

Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand ...
1
vote
0answers
36 views

question about isolation lemma.

Given the set $\mathcal{F}\in\mathcal{P}(\{1,...,m\})$, I need to provide it with probability $\frac{1}{2}$ a weight function $w:\{1,...,m\}\rightarrow\{1,...,n\}$ such that there will be a single ...
1
vote
2answers
32 views

Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...