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)

1
vote
1answer
66 views

Minimizing computations for evaluating two polynomial simultaneously

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I ...
0
votes
0answers
24 views

What's the efficient algorithm to compare (a subset of) algebraic numbers to zero?

Let $\mathbb{X}$ be a set of numbers that are built out of integers using $+,-,*,/$ and $\sqrt[2]{\phantom{x}}$. Let $x \in \mathbb{X}$. What's the efficient algorithm to check if $x = 0$ or $x > ...
1
vote
1answer
33 views

If I have a vector inside a rectangle, how do I tell which side of the rectangle the vector will hit?

I'm trying to solve an issue where I basically have a vector inside of a rectangle. I want to figure out if the vector continues its trajectory, what side will it strike? The vector is given as an (x, ...
0
votes
1answer
74 views

Solving a Rubik's cube in 20 moves or less

Most "cubers" solve a Rubik's cube in about 60 moves, using special algorithms and quick fingers. But any Rubik's cube can be solved in 20 moves or less (cube20.org). Is it possible that there is a ...
1
vote
0answers
28 views

Algorithm to find a number to divide by

I have a following problem. I have a variable $x$, I have a target value $y = 20$ and I have a ...
4
votes
2answers
76 views

Integer Square Root Algorithm

I'm currently working my way through David M. Bressoud's "Factorization and Primality Testing", and I'm struggling with an exercise (exercise 5.7) that asks the reader to prove that the following ...
1
vote
0answers
53 views

Application of algorithm to sequence

I got this puzzle from a professor. Suppose that we have a sequence $a_1$, $a_2$, .., $a_{200}$ $= 1, -1, 0, ..., 0$ where we have $198$ zeros. Now, we perform this algorithm: we replace $a_i$ with ...
0
votes
1answer
19 views

Sorting Algorithm for weakly ordered list

I am aware of some sorting algorithms and there pros and cons but my question is specifically: What is a good sorting algorithm for a list that is generally but not strictly increasing, i.e. 1 5 4 8 5 ...
1
vote
1answer
46 views

Number of Paths in a Graph

I have an undirected, unweighted graph. Let us fix a vertex and find all distinct paths from that vertex which covers all vertices of the graph. The task is to find the number of possible such paths ...
3
votes
1answer
84 views

How many pawns, bishops, rooks or kings can be put on a $n \times n$ chessboard such that they don't threaten each other?

A friend of mine asked me this question and I know this is not easy to solve. I found some informations similar to this question here: https://en.wikipedia.org/wiki/Eight_queens_puzzle; First of all, ...
0
votes
1answer
22 views

Need help in understanding appoximation for heavy hitters problem

I am reading a paper and do not understand the following "We allow the space used by a solution to grow as $1/ \epsilon $, so as $ \epsilon ↓ 0$ the space blows up..." I do not understand the ...
0
votes
0answers
21 views

Efficient curve fitting, and quantum computers

I have a two part question concerning curve fitting to N parameters using computers. First, is the time to find a curve fit to N data points proportional to N or is it worse? Second, is this class of ...
24
votes
4answers
1k views

Is there a branch of Mathematics which connects Calculus and Discrete Math / Number Theory?

I am asking this question out of both curiosity and frustration. There are many problems in computer science which require you to perform operations on a finite set of numbers. It always bothers me ...
0
votes
0answers
76 views

Find number of valid permutations [duplicate]

I have to find the number of permutations of first N natural numbers such that given C conditions should be satisfied. The C conditons can be like this 1 and 2 not occurs consecutively 4 and 5 not ...
0
votes
1answer
37 views

Is this the correct way to calculate probability?

I'm trying to create an AI for a game I develop but I run into the problem of trying to figure out how to calculate probability. The probability I'm trying to calculate is what is the probability ...
2
votes
2answers
84 views

Deriving a formula/algorithm to find all integers with n digits (abcd…) where a+b+c+d… = a × b × c × d…

a+b+c+d... = a × b × c × d... The sum of the digits equals the product of the digits. I'm currently creating a program in c++ where the user inserts a lower limit m, and a upper ...
1
vote
1answer
39 views

Why does the Master Theorem work for this example but not the other?

So apparently: $T(n) = 2T(n/2) + n / \log n$ doesn't work with the Master Theorem because of the log term. But then: $T(n) = 4T(n/2) + n / \log n$ is $\Theta(n^2)$ even though it's still the same ...
-4
votes
1answer
33 views

Compute bits per second [closed]

We know a computer can code 1024 bits/sec using a RSA modulus of 1536 bits and the running time of modular exponential with modulus $n$ is $O(\ln^3(n))$. Using a key of 2048 bits, how many bits per ...
2
votes
0answers
24 views

Is there a faster algorithm than $O(n^2)$ for calculating “cofactors” $C_k = \prod\limits_{j\neq k}(c_k - c_j)$?

Is there a faster algorithm than $O(n^2)$ for calculating "cofactors" $C_k = \prod\limits_{j\neq k}(c_k - c_j)$ ? (presumably $O(n \log_2 n)$ if one exists) In other words, if I have factors ...
0
votes
0answers
22 views

How to calculate x from these two numbers

Here's the scenario: I have a basket of apples. Any apple I put into the basket quadruples. If there are 20 apples in the basket it means I placed inside 5. But this only happens till it reaches 1000 ...
3
votes
2answers
26 views

How can a blind pixelated 2d mason chip away the entirety of a pixelated 2d rock

So the mason is a single pixel and next to him there is a continuous pixelated rock in this 2d pixel space. He can detect rock pixels, he can turn, move forward, and chip away rock he is next to. The ...
0
votes
1answer
74 views

How to solve these system of linear equations?

I am having a problem to solve the following set of n equations: $$a_1 - k_1*b_1 = a_2 - k_2*b_2 = a_3 - k_3*b_3 = \dots = a_n - k_n*b_n$$ Given all the values of $a_i \ and \ b_i$, the question is ...
4
votes
1answer
179 views

Monotonic Function Optimization on Convex Constraint Region

So I have the following function, which I want to maximize: $$f(x_1,...,x_n) = \sum_{i=1}^n\alpha_i\sqrt{x_i}$$ (where all $\alpha_i$ are positive), subjected to the following equality and inequality ...
1
vote
3answers
131 views

Isomorphism of Non-Symmetric Matrices

$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$. Example: An example of $6 \times 3$ non-symmetric matrix is $$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & ...
4
votes
1answer
72 views

Algorithm. Minimum area of a square enclosing given set of points .

I am learning about the science of algorithms and I'm studying some problems with their optimum algorithm. The problem I describe below is one of them. I need a lower and an upper bound of its ...
0
votes
1answer
29 views

Simplifying a -1 term out of a finite product

I've come up with an algorithm that relies upon the value of the following product: $$Q_{k} =\prod_{n=0}^k [f(n) - 1]$$ Where $f(n) \ge 2$ and strictly increasing integer function [see note]. ...
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
55 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
46 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
66 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
34 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
23 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
26 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
69 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
32 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 ...