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
2answers
95 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
88 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
45 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
24 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
74 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 ...
3
votes
0answers
34 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
54 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
29 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
34 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$. ...
2
votes
2answers
24 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
31 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
767 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
54 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
116 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
39 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
56 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
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
29 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
11 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
96 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
80 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
46 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
23 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
40 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
31 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
28 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
70 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
28 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
21 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
31 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
27 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 ...
0
votes
2answers
64 views

Division n items into k boxes prove that it is NP-Complete

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem. We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
1
vote
0answers
31 views

Karatsuba multiplication for $x = 123 , y = 100$

Given the numbers $x = 123$ and $y = 100$ how to apply the Karatsuba algorithm to multiply these numbers ? The formula is xy=10^n(ac)+10^n/2(ad+bc)+bd As I ...
1
vote
1answer
17 views

Simultaneous equations change expression variables

I have a deceptively simple-looking problem. $$A + B = A'\\ C + D = B'\\ A + C = C'\\ B + D = D'$$ On LHS $4$ variables $A, B, C, D$ On RHS $4$ variables $A', B', C', D'$ Is it possible to ...
0
votes
0answers
35 views

How to determine a matrix when the sums of rows and columns are given

I was given a $5\times30$ matrix with each element of the matrix can only take 0 or 1. It is given that the sum of each row is 8 and the sum of the first 20 columns equals to 1 while the sum of each ...
0
votes
1answer
19 views

Binary Heap Question interpretation

In the question in the link below, how do I tell weather to draw out a binary min heap or a binary max heap? Am I misunderstanding the question? Binary Heap Question
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...