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)

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 ...
0
votes
0answers
33 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
0answers
12 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 ...
2
votes
0answers
93 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
1answer
27 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 ...
3
votes
2answers
88 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 ...
-4
votes
2answers
53 views

computer algorithm VS mathematical algorithm [closed]

I really dont understand the difference between computer algorithm and mathematical algorithm. Do you know? I tried finding a solution but I failed.
0
votes
0answers
42 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

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
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
69 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 ...
4
votes
0answers
32 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
0answers
53 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 ...
0
votes
0answers
25 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 ...
1
vote
1answer
33 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 $8$. ...
1
vote
2answers
23 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 ...
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 ...
3
votes
0answers
28 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 ...
25
votes
3answers
760 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
53 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 don'...
8
votes
4answers
110 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
1answer
29 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 $...
0
votes
1answer
37 views

Euclid GCD intuition

I was reading someone explanation about Euclid's GCD. I understand some things that the person explain but I don't get some points. This is the explanation: If both the large numbers $a$ and $b$ have ...
4
votes
1answer
43 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 ...
1
vote
1answer
46 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
0
votes
0answers
14 views

Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
0
votes
0answers
68 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, \begin{...
0
votes
0answers
11 views

How to translate between two 3D coordinate systems

I am working with 3 coordinate systems: Blender, Bullet Physics engine and LibGDX. I use Blender as UI engine with it's built in Bullet Physics and exporting those to LibGDX. I am not sure, but I ...
0
votes
0answers
28 views

Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
1
vote
1answer
10 views

Is there a better way to get the value of X after recursively multiplying by list Z?

If I have a number X and a list of percentages Z, how would I find the value of X after repeatedly multiplying it (and its result) by each percentage value in the list Z? Naive Way: ...
3
votes
2answers
82 views

How do you pack circles into a circle?

I want to know how many small circles can be packed into a large circle. Looking at Erich's Packing Center it seems that packing is a non-trivial problem to solve. My interest is practical rather ...
1
vote
4answers
77 views

Is there any Algorithm to Write a Number $N$ as a Sum of $M$ Natural Numbers?

I have a number $N$ (for example $N=64$). Is there any algorithm to find all the feasible ways for writing the number $N$ as a sum of $M$ positive numbers? (For example $M=16$) --- Repetition is ...
0
votes
1answer
19 views

Inequality insde algorithm design (kleinberg), Disjoint Path

I am reading the "Algorithm Design" (Kleinberg et al). Inside this book, at the chapter 11.6 there is an inequality I have failed to resolve. Considering $\beta=m^{(1/3)}$ and $|I|>=1$ (it is a ...
0
votes
2answers
56 views

Comparison between $n\log n$ and $n^2$ sorting algorithms

Suppose we have two sorting algorithms which takes $O(n\log n)$ and $O(n^2)$ time. What can we say about it? Is it always better to choose $n\log n$ if the size $n$ is not given? Or can we say on an ...
-1
votes
1answer
39 views

How to represent a nested loop using mathematical formulae [closed]

Excluding the context of summation or product, how can one represent a nested loop within mathematical notation? For instance, if every element of an array X is being compared to one another as part ...
0
votes
1answer
22 views

Determine if the function is $O(x^2)$ . If so find the constants $C$ and $k$ to verify.

Determine if $ f(x) = 4x^2+x+1$ is $O(x^2)$. If so find the constants $C$ and $k$ to verify that the function is $O(x^2)$ My solution is: \begin{align} & |f(x)| \le C|x^2| \ \ \ \ \ \ \forall x ...
0
votes
1answer
13 views

Prove that search in matrix takes mor than n comparisons

Let us call matrix $A$ ascending if $A_{kl}\ge A_{ij}, i \le k, j \le l$ for every $k$ and $l$. Given a number $x$ prove that determining whether $x$ is in an ascending matrix or not takes more than $...
1
vote
0answers
36 views

Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem: There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix: $$\begin{pmatrix} ...
0
votes
0answers
18 views

number of times a sum can be made with three numbers

we are given 4 numbers A, B, C and K with the condition A,B,C >=K. We need to find the sum ...
1
vote
1answer
21 views

A more general case of assignment problem

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more general problem: for given $n \times m$ table select several numbers, maximizing ...
0
votes
0answers
28 views

Minimum sum of matrix coefficients

Let be $A$ a finite matrix with positives coefficients of order $m\times n$. Lets consider the sum of $k=min(m,n)$ coefficients of matrix $A$, such that at most one element by row and column are ...
0
votes
0answers
27 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ T(n)=T(\...
3
votes
5answers
66 views

How to prove that $\sum_{i=j}^nn-i = \sum_{i=1}^{n-j}i$?

Trying to solve question 2-3 from Skiena's Algorithm Design Manual which asks to find the runtime of the following loop: ...
1
vote
1answer
22 views

Is the set of numbers of computable functions f(x) = c recursively enumerable?

Consider the set of numbers of computable functions such that is $f(x)$ defined, $f(x) = c$ for any $x$. Is this set enumerable or co-enumerable? (Or neither). A bit of my thoughts on it. We can take ...
1
vote
0answers
25 views

Pollard Rho - DLP Algorithm Implementation

I am working with Pollard Rho Algorithm DLP. I have developed in Java and Python the way to calculate the table to find the collisions, and then using congruences and some others tricks I am getting ...
1
vote
0answers
20 views

Determine if fitted line is actually one line

I am trying to fit multiple lines through many data points in 3d space. My working method is sequential RANSAC, which now is fast enough and fits some lines, but produces some lines that don't fit one ...
1
vote
0answers
27 views

Interpolating discrete data with completely monotone analytic functions

Suppose we have a positive integer $n$ and a finite list of real numbers $\{a_1,\,a_2,\,\dots,\,a_n\}$. We want to find a real-analytic function $f:[1,n]\to\mathbb R$ such that $f(m)=a_m$ for all $m\...
1
vote
1answer
26 views

Showing equivalence of 2 Big O notations

I have the task to show that the following two big O definitions are equivalent. My first thought was that it has to be equivalent because the set of natural numbers excludes all broken rational ...