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
0answers
7 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
39 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 $10^9 ...
1
vote
1answer
18 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
4 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
1answer
52 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
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.
0
votes
0answers
32 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
59 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
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
0answers
50 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
12 views

Algorithm creates representative set of data [on hold]

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
0answers
18 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
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 ...
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 ...
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 ...
2
votes
0answers
25 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 ...
21
votes
3answers
700 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
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 ...
5
votes
2answers
54 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
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 ...
0
votes
1answer
34 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 ...
0
votes
0answers
10 views

Determine an algorithm for $LU$ factorization and determine the number of operations [duplicate]

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of ...
0
votes
0answers
7 views

Determine an efficient algorithm and describe the computational/storage complexity

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
4
votes
1answer
34 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
44 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
13 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
62 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
votes
0answers
14 views

Vertex-cover-like problem with reduction to maximum flow

I am trying to solve the following problem: Solve the following problem by reducing it to the computation of a maximum s-t-flow: Let G be an undirected graph, $c:V\rightarrow\mathbb{Z}$ and ...
-2
votes
0answers
25 views

Trouble with Strassen's algorithm [closed]

I just recently started learning about matrix multiplication. I' teaching myself through the internet mostly and I can't quite grasp the concept of Strassen's algorithm. I understand the 2x2 matrix ...
0
votes
0answers
10 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
20 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
70 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
votes
0answers
12 views

Apply gradient and divergence on 2D matrix to get drains

I need to find all drains in relief map. It is 2D matrix with heights for each point. Is it possible to compute vector field from scalar 2D matrix by applying gradient and to compute scalar field of ...
1
vote
4answers
72 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
18 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
55 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
37 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 ...
-5
votes
0answers
13 views

Decision Tree for heapsort [closed]

Construct the $4=n$ decision tree for mergesort using the code discussed in class. The initial entries of the array are $a,b,c,d$. You can omit the right subtree. That is, start with the root ...
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
32 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
24 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
23 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) . $$ $$ ...
3
votes
5answers
65 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
19 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 ...