# Questions tagged [algorithms]

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).

10,670 questions
Filter by
Sorted by
Tagged with
8 views

### Convert a direction into an angle on our compass

I have a new position vector and old x and z coordinates and I need to determine the angle traveled. So far I am getting the slopes absolute value and then using that to generate an angle. Based on ...
7 views

### Approximating $\mathcal X \subset \mathbb R^n$ with the union of disjoint hyperrectangles

Let $\mathcal X$ be a bounded subset of $R^n$ that is generated by a set of linear inequalities. For example, let ${\bf x} = (x_1, x_2, x_3, x_4, x_5)^\intercal \in \mathcal X$ iff \begin{align*} 0 &...
1 vote
33 views

### Algorithm to find the angle of a direction

I need to translate the distance between two points into an angle from 0 to 359. To do this I use the new position coordinates which is defined by a vector and subtract the original position. This ...
16 views

### shifting polynomials in Fast Multipole Method

There is one thing I don't get about the FMM algorithm (of coulombic potential in 2D - https://cims.nyu.edu/~donev/Teaching/WrittenOral/Projects/JasonKaye-WrittenAndOral.pdf). Suppose we have ...
83 views

### Number of three-tuples such that $c_1a_1 + c_2a_2 + c_3a_3 = n$ and $c_1 \ge c_2 \ge c_3$

I'm trying to figure out how to find the number of three tuples that sum up to $n$ when each element has a weight of $c_i$. In other words, how many combinations are there of $(a_1, a_2, a_3)$ such ...
1 vote
19 views

### Integer algorithm to rotate a bitmap image(2d array) on small angle?

The task is - if you want to rotate a bitmap image on the small angle , so the most of the pixels will remain on its place or will be just shitted strict horizontally or vertically a little bit, is ...
32 views

### Why does spectral clustering work?

Relevant Background I've recently learnt about the spectral clustering algorithm and had a hard time understanding why we do what we do. Trying to undetstand, I stumbled upon this great post, that ...
19 views

### Find the closest stack total weight where number of n values should be the same in all stack

Lets say I have potatoes with weight 7,5,4,8,12,10,4,8,12,12,13,12 I want to stack them in the way that all the stacks weight should be closest possible condition each stack should have equal amount ...
1 vote
56 views

### Find the cheapest arrangement of non-overlapping colored rectangles necessary to achieve a sequence of colors behind holes

Input Let the input be a sequence of colors with any length at least 1. For example, (red, blue, red, green, blue). Each color is represented in the input as a string, not as any abstract notion of a ...
94 views

### Good Algorithm to Compute all Subgroups of a Finite Group.

Let's suppose we have a group $G$ of finite order $n$. We want to algorithmically compute all subgroups, and there are some ways to do that. First one: Compute all subsets. Verify for each of them if ...
44 views

### Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability.prove $p_i=p_j \implies |w_i|-|w_j|\leq1$.

Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability. I have to prove the fact that $p_i=p_j \implies |w_i|-|w_j|\leq1$. I read about binary Huffman codes and ...
1 vote
44 views

### Determinant of triangular matrix with extra diagonal

If we have a triangular matrix we can calculate the determinant in $O(n)$. If we have a triangular matrix with one extra diagonal above the main diagonal, so for example: \begin{Vmatrix} a_1 & a_2 ...
16 views

### Boolean algebra simplify with use of complex gates

How to simplify Boolean algebra, And most importantly, "simplify" means at the least use of logic gates | including (nand,nor,xor,exnor...) The Boolean algebra(including K-maps , Quine–...
35 views

### Can an articulation point have all edges as non-bridge?

The two endpoints of a bridge are articulation vertices unless they have a degree of 1. Will these articulation vertices form the complete set of articulation points of an undirected graph ? ...
45 views

### Determine the location of a logistics center which is optimally close to its providers

Excuse me if my question is not worded perfectly in mathematical terms. I don't have a strong math background. So, here's the problem which has been brought up by a real-life situation: For simplicity,...
24 views

### Is it possible to obtain rotation or transposition with following rules?

I have been trying to solve a problem in which I faced this question which I need to answer to solve my problem. Any help or suggestions or references would be helpful ? Given a sequence of length ...
51 views

### Fibonacci sequences within the Fibonacci sequence recurrence

I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm: ...
45 views

### How many rounds does an Elo Rating System require to stabilise?

the questioner is not a mathematician Using an Elo Rating System, or a 'modified' Elo Rating system ... If I start a competition not knowing participants' relative ability How many rounds are required ...
69 views

### How did Lanczos find his approximation for the Gamma function?

The Lanczos approximation gives a fixed-precision method for calculating the Gamma function. It is used in Desmos in their factorial function. According to this Wikipedia page, Lanczos derived his ...
117 views

### No Dijkstra and no BFS? What else is there?

So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a ...
117 views

### I think I have discovered a new sorting algorithm using binary search tree. [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
8 views

### Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ , Find an optimal code.

Let $X,Y,Z,W$ be words with vector frequency $(x,y,z,w)$ such that $x\leq y\leq z\leq w$. Find certain requirements about $x,y,z,w$ such that $W=00,Z=01,Y=10,X=11$ is an optimal code. My solution : ...
31 views

### Brooks' Theorem Time complexity

I am looking to derive an algorithm that finds, for every connected graph $G$ that is neither complete nor an odd cycle, a $\Delta(G)$-colouring in time $O(m+n)$. When we proved Brooks' theorem we ...
4 views

### Clarify answer for asymtotic of median smoothing

Calculating algorithmic complexity for median smoothing in Time Series I came up with the question same as this. Quote it here: A time series with T observations is given. Median smoothing with width ...
18 views

### In TSP where a modified triangle inequality holds, what is the approximation ratio of Christofides' algorithm?

In the metric TSP, we can use Christofides' algorithm to get a $\frac{3}{2}$-approximate solution. This is a consequence of the triangle inequality where $d_{ij} + d_{jl} \geq d_{il}$, that enables us ...
18 views

### Prove that factoradic method gives $k$-th lexicographical permutation.

Factoradic method can be used to get $k$-th lexicographic permutation of $n$-elements. The factoradic method is described here: https://en.wikipedia.org/wiki/Factorial_number_system#Permutations. ...
39 views

### Bellman-Ford algorithm find path between source and destination

Suppose we have this graph and we want to go from A to E with the least cost: Here are my steps: I think I am correct and I dont need any more iterations to find something new , I have found the ...
1 vote
43 views

### The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

I saw this pseudocode from the book Introduction to algorithm (Chapter 31 page 957) on how to implement Modular Exponentiation. ...
21 views

### Bellman-Ford algorithm undirected graph with destination node

Suppose we have a undirected graph with n vertices.If we wanted to find the shortest path from the starting vertex to any vertex we would have to apply the Bellman-Ford algorithm for n-1 iterations. ...
86 views

### Can we find the sum of a sorted array in O(logn) time?

I have the following code: arr = [2,3,4,5,6] sum = 0; for i in range(0, len(array)): sum = sum + arr[i]; print("Array has the sum of:"+str(sum)); ...
251 views

### Why do greedy coloring algorithms mess up?

It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...