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
0answers
58 views

Conjecture about Rabin-Miller pseudo prime test

At oeis A014233 a method for exact testing of primes up to a level using Rabin-Miller is described. I have used this method together with squeezed prime tables to test the Rabin-Miller pseudo prime ...
5
votes
3answers
63 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
0
votes
2answers
23 views

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected graph?

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected, unweighted graph?
0
votes
0answers
32 views

Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with $$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ...
1
vote
1answer
9 views

Big Omega number theory representation

Source-https://en.wikipedia.org/wiki/Big_O_notation Is the highlighted portion in red right? $\forall$$n_0$ $\exists$$n>n_0$ It should be opposite(for all and for some should be ...
0
votes
0answers
2 views

Hurst exponent Algorithm not well defined? What to do in this case?

The R/S algorithm is well known for finding the Hurst component of a given data set. I have one query about whether it is well defined? Suppose in a given partition, all of the values were equal to ...
0
votes
1answer
62 views

Do formal power series algorithms different from normal power series algorithms?

As far as I understand formal power series is an infinite sequence unlike normal power series which try to approximate the function in a few terms. So will formalPowerSeries$(\sin(x))$ differ from ...
0
votes
0answers
7 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
1
vote
1answer
19 views

Relation between powers of inverse modulo n.

Recently, I was studying enchanced euclidean algorithm. I am wondering if there is some way to calculate inverse of $a^2$ (and higher powers) modulo $n$, knowing inverse of $a$ modulo $n$. For ...
2
votes
0answers
83 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ ...
1
vote
0answers
12 views

Calculate random distribution of triangles within a rectangle. [on hold]

I am a programmer trying to find a solution to a problem regarding images and JavaScript. I want to create a function that when given an image will calculate a random set of triangles of different ...
3
votes
0answers
126 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
0
votes
1answer
37 views

What is the order of

What is the order of the following: $$\frac{(33x^{7}+6)(x^{2}+3)}{\sqrt{x^3+7x^2-x+5}}$$ Would it be $$\Theta (x^{\frac{17}{2}})$$
3
votes
1answer
95 views

A variation of Buchberger algorithm

Let $I$ be an ideal of a polynomial ring $R$. Fix a monomial order. Denote the $S$-polynomial of $f, g\in R$ by $S(f, g)$ and denote the gcd of their leading terms by $T(f, g)$. Consider the ...
3
votes
1answer
20 views

Prove that it is sufficient to check $\lceil \log(k) \rceil$ pairs to tell if a set of integers is pairwise coprime

I am reading chapter 31 of Introduction to Algorithms (CRLS) and I encountered some difficulties while solving 31.2-9. I managed to prove the first part of a problem, but I can't prove the generalized ...
2
votes
2answers
496 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
3
votes
2answers
77 views

How can the policeman catch the gangster?

I try to solve the following problem (Moscow Mathematical Olympiad, 1978) There is a town with six streets: four sides of a square and two its middle lines. Policeman tries to catch a gangster. If ...
0
votes
0answers
29 views

Solving system of nonlinear equations via iteration

I will give an example to illustrate the question: Assume I have the system: $$ xy + x + y = 7\\ x^2 + y^3 = 9 $$ and I want to solve for $x$ and $y$. It is a fairly common approach to rearrange ...
1
vote
1answer
92 views

Game of chocolates

Two players $A$ and $B$ play a game alternatively and $A$ starts the game. Their are $2$ boxes of chocolates and we are Given the number of chocolates in both the boxes, let them be $c_1$ and $c_2$, ...
0
votes
0answers
64 views

Sequence of integers in given range that sums up to given value

I'm trying to find out, if there is a way to find the total number of possible combinations of integers $x_i \in [l,u] \cap \mathbb{Z}$ for all $i = 1,\ldots,n$ that sum up to $A$. Generally, ...
1
vote
0answers
11 views

Maximize the mutual permutation disparity

I am trying to work on a problem that needs me to find the top-k most disparate permutations for a n-tuple (hence n! possible choices). The disparity measure between two permutations I'm thinking of ...
6
votes
5answers
23k views

Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
1
vote
1answer
24 views

Algorithm to check if number x exists in matrix

I have the task to develop an algorithm which checks if a specific number x exists in an int-array[][]. Further the 2-dim array entries have following terms: $$array[i][j] \leq array[i][j+1] \space ...
0
votes
0answers
5 views

Dynamic Biased Randomized Selection Algorithm

I'm looking to implement an algorithm that picks items from a list randomly, albeit in a biased way. Say I have a value priority for each element in that list. I would like an element with higher ...
1
vote
1answer
445 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
-4
votes
2answers
37 views

computer algorithm VS mathematical algorithm [on hold]

I really dont understand the difference between computer algorithm and mathematical algorithm. Do you know? I tried finding a solution but I failed.
7
votes
1answer
103 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
0
votes
0answers
36 views

Construction of Permutation Group (bounded order) from a Set of Permutation

Given a set of permutation $S$. It has $|S|$ (The cardinality of $S$) elements. Consider a subset $A\subset S$. We can construct a group using $A$. One possible algorithm could be- We start ...
0
votes
0answers
7 views
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
0
votes
0answers
23 views

What is the lowest order of linear ODE that cannot exist any general algorithm for solving all the aforementioned order differential equations?

What is the lowest order of linear ODE that cannot exist any general algorithm for solving all the aforementioned order differential equations? There are general algorithms that already can solve the ...
0
votes
0answers
66 views

Algorithm to calculate shortest time in which two people can collect K items from N cities.

There are N cities connected via M bidirectional roads. Each road connects exactly 2 different cities and has a travel time associated with it. There are K different items in these cities. Given the ...
1
vote
0answers
52 views

About a geometric algorithm to compute $\sin$ based on the unit circle

In an old post I have found a user which claims to have a geometric algorithm to compute trigonometric  functions for an angle between $0^\circ$ and $90^\circ$ based on the unit circle. Here's the ...
4
votes
0answers
26 views

Find most varied match assignments for a 4-player card game

I'm a programmer and confronted with a particularly hard (at least for me) problem I couldn't find an answer for. This is not a school task or anything. It is something I need personally. I've ...
1
vote
1answer
31 views

Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be ...
0
votes
0answers
13 views

Algorithm creates representative set of data [closed]

I have algorithm to analyze and make it easier to implement in programming language (Python). We have table with data and we want to select only representative part. It looks like: ID_PRODUCT | ...
0
votes
1answer
50 views

finding two most distant 3d points

I'm trying to write an algorithm. There are $9$ points $3$ of $x$, $3$ of $y$, $3$ of $z$. How can I find the two most distant? Mathematically, I need explanation. Thank you for all appreciated ...
0
votes
0answers
19 views

solving mathematical function using genetic algorithm

I want to solve a mathematical function(ex: f(x) = 2x*x+3x) which I want to implement using genetic algorithm. I was following through lecture in the given link . But couldn't understand few things ...
5
votes
3answers
435 views

Algorithm to find the exact roots of solvable high-order polynomials?

It is not generally possible to determine the roots of a polynomial whose grade is bigger than 4 in terms of roots and basic operations. But I heard that it is possible to give a criteria whether a ...
21
votes
3answers
714 views

Sudoku with special properties

Sudoku is a puzzle, with the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also "sudoku-blocks") contains all of ...
1
vote
1answer
14 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
0
votes
1answer
62 views

Strassen's Laser Method Technique AND Tensors in matrix multiplication algorithms

I understand the first algorithm presented by Strassen in 1968, for fast matrix multiplication. This was the first improvement to the naive approach of multiplying matrices. Thereafter, he went on to ...
3
votes
1answer
531 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
7
votes
1answer
1k views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
3
votes
0answers
27 views

Efficient algorithm for solving a bilinear Diophantine system

I wonder if there is an efficient algorithm for finding an integer solution $(x_1, \dots, x_n)$, $(y_1, \dots, y_n)$ for the following type of system of equations $$ a_{1,1} x_1 y_1 + a_{1,2} x_1 y_2 ...
1
vote
1answer
52 views

Union, intersection, set theoretic difference of recursively enumerable sets

Forgive me for asking though some of this has been asked/answered elsewhere and there are many examples on the internet; I ask again because I am doing a Maths course (not computer science) and we ...
18
votes
0answers
992 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
4
votes
1answer
35 views

Computing volume of concave polyhedron

I have a circular grid with points uniformly distributed throughout it. See this: Each point has some nonnegative height assigned to it (i.e. height can be 0 on up). I'm trying to accurately ...
0
votes
1answer
752 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 ...
0
votes
1answer
28 views

Why is $lg(\theta(\frac{1}{n}))$ = $\theta(\frac{1}{n})$?

I'm trying to follow a proof of an exercise from an algorithms textbook, and am confused about one the algebraic steps in the proof: $lg(\theta(\frac{1}{n}))$ = $\theta(\frac{1}{n})$ Where $lg$ is ...