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)

2
votes
0answers
64 views

Tweaking Reddit's Ranking Algorithm

This image explains how Reddit's Ranking algorithm works. As you know, Reddit is a very high traffic site. Therefore, the post rank decreases quite fast. This algorithm puts emphasis on bringing ...
2
votes
0answers
29 views

Fast multiplication times a fixed constant $A$?

Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$? We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) ...
2
votes
0answers
63 views

Dishwasher Unloading: Optimal Algorithm

Suppose you are unloading cutlery from a dishwasher containing $4$ types of cutlery: teaspoons, tablespoons, knives and forks. Each type has 8 pieces. You hang the cutlery on a rack with two sides. ...
2
votes
0answers
38 views

Accelerated Gradient Descent V.S Nonlinear Conjugate Gradient Descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has ...
2
votes
0answers
159 views

multi-game round robin tournament algorithm

Each year I am part of a group that hosts a "Lawn Game Olympics." 6 different lawn games (bocce, ladder golf, washer toss etc...) and every year a different amount of teams shows up. The first year ...
2
votes
0answers
78 views

Efficient elevator strategy

Suppose an institution building has 12 floors and there are a total of 8 lifts. Now lets say a situation arises at peak times where almost all the lifts are crowded and people randomly enter any lift, ...
2
votes
0answers
29 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
2
votes
0answers
41 views

${n \choose m}$ on periodic lattice (Bravais)

How can I generate all symmetry-inequivalent selections of m sites on a periodic 2d (Bravais) lattice with n sites? Are there some general results or theorems which may be useful in this type of ...
2
votes
0answers
68 views

How do I solve the Frenet-Serret equations for the curve, instead the curvature/torsion?

So I happen to be working in a hobby side project which happens to be increasingly convoluted so now, naturally, I have come to the aid of the gurus. It turns out that I am trying to solve the ...
2
votes
0answers
84 views

Efficient computation of matrix determinant in finite ring

I am trying to implement generalization of Hill cipher. My idea is very simple: the size of key matrix should be arbitrary number not only three. All steps of this cipher is trivial except computation ...
2
votes
0answers
38 views

Assignment problem, minization of the Standard Deviation

I have an assignment problem. So typically I need to find the optimal combination between two sets of parameters P, M. I know that the Hungarian Algorithm is often privileged for this kind of problem ...
2
votes
0answers
75 views

Fast algorithm to invert a large sparse matrix

I am interesting in sparse matrix that defined at here. I am looking for a fast algorithm to invert the matrix (better than Gaussian Elimimation). Could you suggest to me some methods that reduce ...
2
votes
0answers
25 views

Binary search where the computer may lie upto $k$ times

We are performing a binary search on $n$ elements where the answer to a comparison may be wrong upto $k$ times. What is the time complexity of finding the right element in terms of $n$ and $k$? The ...
2
votes
0answers
86 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
0answers
44 views

Explanation of the algorithmic form

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.The core of the algorithm is the replacement of a string of $1's$ ...
2
votes
0answers
94 views

The amazing lift.

I would like to ask for a program to efficiently calculate how a lift should fetch the people who need it. Most of us use lifts (or elevators) but maybe it could be programmed to be faster! Or can it? ...
2
votes
0answers
327 views

How to solve instant insanity puzzle with graphs.

So I have a 10 cube insanity puzzle, I constructed the graph (I'll post pc later) based on the colors the problem is that there is just way to many lines and nodes to see the solution. Is there any ...
2
votes
0answers
89 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
0answers
34 views

Good method for finding roots that *usually* fall within an interval?

I've been using Brent's method to find the roots of a monotonic, nonlinear, non-differentiable function. The roots often fall within a known interval, but Brent's method fails if they occasionally ...
2
votes
0answers
31 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...
2
votes
0answers
44 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
2
votes
0answers
27 views

Sorting for maximum mean squared successive difference

I have a set of numbers and I have to order them for maximum MSSD (mean squared successive difference). For example, if I have the ordered set {1,2,3,4,5,6} this would give me an MSSD of ...
2
votes
0answers
125 views

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in ...
2
votes
0answers
287 views

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in ...
2
votes
0answers
110 views

Show that matrices multiplication and LUP decompositions have the same difficulty

Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to compute the LUP decomposition of an $n\times n$ matrix. How to show that multiplying matrices and ...
2
votes
0answers
31 views

What is the most “unbalanced” vector between two given vectors?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ be the product order on $\mathbb{R}_+^m$. Lastly, given a vector $V = (v_1, \dots, v_m) \in ...
2
votes
0answers
87 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
2
votes
0answers
98 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
2
votes
0answers
98 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
2
votes
0answers
72 views

longest integer vector partition

I'm trying to solve the following question: Given an nonegetive integer vector $\overset{\rightarrow}{m}=(m_1,m_2,\ldots,m_k)$, how to find the longest distinct integer vector sequence ...
2
votes
0answers
52 views

A list of numbers and

I have a real life problem that math may be able to solve. I am no mathematician so if you have any insight please use the simplified version. This problem is way beyond me. My gut tells me there is ...
2
votes
0answers
88 views

Algorithm to find smallest difference in array

We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array. One such algorithm is to sort the array and check adjacent pairs of ...
2
votes
0answers
46 views

Defining nth element of combinatorics

Let's say I have a set = {$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$} and I'm interested in the $C^{10}_3 = \frac{10!}{3!(10-3)!} = \frac{10*9*8*7!}{3!7!} = 10*3*4 = 120$ Now, say $1^{st} element = 1, 2, 3$ ...
2
votes
0answers
87 views

area estimation with tiling

For any given shape drawn on a graph paper, a kid can calculate the area of any shape by counting the tiles with a simple formula: any edge covering 50% or more, mark the tile; total area = sum all ...
2
votes
0answers
43 views

Polynomial decomposition

I've just recently learned about the neat algorithm that, given a polynomial $f$ finds (non linear) polynomials $h,g$ such that $$f = g \circ h \quad (1),$$ or decides that there are no such ...
2
votes
0answers
123 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
2
votes
0answers
105 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
2
votes
0answers
33 views

Rotating Seating Algorithm

I am planning a speed dating networking session with round tables. My challenge is to rotate all participants to each of the tables while minimizing the times in which they sit with the same person. ...
2
votes
0answers
62 views

Indexing ranked permutations into other ranked permutations

Consider all permutations of 0, ..., n-1 under some ranking R. Given two ranks, i and j, what is the rank of the permutation that results from applying the i'th permutation to the j'th permutation? ...
2
votes
0answers
114 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
2
votes
0answers
108 views

Computing generators of the positive component of a graded ring

Let $R$ be a sub-algebra of $\mathbb{Q}[X_1^{\pm 1}, \dots, X_n^{\pm 1}]$ given by finitely many generators, and let $\lambda$ be a linear form $\lambda : \mathbb{Z}^n \to \mathbb{Z}$. This defines a ...
2
votes
0answers
128 views

Quaternion conversion

We have a normalized orthogonal co-ordinate frame travelling through the curve as in figure 1 below, from one end to other. Let us call starting end as A and ending end as B. What we know is initial ...
2
votes
0answers
30 views

Does the method of steepest decent always move in an orthogonal direction between iterations?

I understand everything, I think, about the method but the result (or requirement) that successive steps are orthogonal to each other. SO, with the formula for this algorithm as: ...
2
votes
0answers
340 views

How to load warehouse pallets efficiently?

Assume that we would want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of $5$ vertical box stacks and the maximum height ...
2
votes
0answers
53 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers $\{a_1,\dots,a_n\}$ and another number $k$. I need to find whether sum of any combination of numbers in the set produces $k$. It can be $a_1 + a_2$ or $a_1 + a_2 + a_3 + a_7$. ...
2
votes
0answers
50 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
2
votes
0answers
79 views

Tau Summatory Function

It is well known that the divisor summatory function can be calculated in $O(x^{1/2})$ via $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^{\lfloor \sqrt{x}\rfloor} \lfloor\frac{x}{k}\rfloor - \lfloor ...
2
votes
0answers
104 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
2
votes
0answers
379 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
2
votes
0answers
330 views

How to distribute 5-digit numbers in 5x5 matrices

I have 98000 5-digit numbers, from 00001 to 98000. I need to distribute these 98000 numbers in 14000 5x5 matrices. A matrix cell must contain only a digit from 0 to 9. Each matrix must receive 7 ...