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

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
user avatar
  • 91
0 votes
0 answers
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 &...
user avatar
  • 805
1 vote
1 answer
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 ...
user avatar
  • 91
0 votes
0 answers
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 ...
user avatar
  • 1
2 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1,551
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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–...
user avatar
  • 1
0 votes
2 answers
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 ? ...
user avatar
0 votes
1 answer
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,...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 62
6 votes
1 answer
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: ...
user avatar
  • 75
3 votes
0 answers
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 311
4 votes
2 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 : ...
user avatar
  • 1,551
0 votes
0 answers
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 ...
user avatar
  • 77
0 votes
0 answers
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 ...
user avatar
  • 111
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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. ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
2 answers
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. ...
user avatar
  • 315
0 votes
0 answers
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. ...
user avatar
0 votes
2 answers
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)); ...
user avatar
3 votes
2 answers
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 ...
user avatar
0 votes
2 answers
34 views

Finding containment between convex polytopes

Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{...
user avatar
0 votes
0 answers
9 views

Root sub-trees of 2-3 tree

Suppose there is a $2-3$ tree with $n$ nodes. Each node in the left sub-tree of the root has $3$ children. (except the leaves). Each node in the right sub-tree of the root has $2$ children. (except ...
user avatar
  • 1,551
1 vote
1 answer
73 views

Algorithm complexity: Proof that $\lfloor\sqrt{n}\rfloor \geq \frac{\sqrt{n}}{2}$ and $n-\lfloor\sqrt{n}\rfloor+1\geq \frac{n}{2}$, $\forall n\geq 2$

Background / Context: I'm currently calculating the complexity of the following algorithm: for j = 1 to n if j*j <= n for k = j to n f() ...
user avatar
1 vote
1 answer
48 views

Explanation for the Euclid Extended Algorithm

Please this is how the code for the extended-euclid algorithm was implemented in the book Introduction to Algorithm (Chapter 31 page 937 EXTENDED-EUCLID(a,b) if b == 0 return (a,1,0) else (d_1,x_1,y_1)...
user avatar
  • 13
1 vote
1 answer
36 views

Verifying the answer of T(n) = T(n/2) + n(2 - cos n) using Master Theorem

$T(n) = T(n/2) + n(2 - \cos n)$ I want to verify my answer for this recurrence. Using the extended master theorem, $\log_ba = \log_2 1 = 0$ Comparing $f(n)$ with $\Theta(n^k \log ^p n)$ we get $k= 1$ ...
user avatar
1 vote
1 answer
37 views

How can I calculate $d$ in this sum with a min-term that depends on $d$?

Given $n \in \mathbb{N}$, $e_i \in \mathbb{N_{0}}$, $l_i \in \mathbb{N}$, $b_i \in \{0,1,2\}$ where $1 \le i \le n, i \in \mathbb{N}$. $$ \sum_{i=1}^n{\min\left(e_i + \frac{b_i \cdot d}{4}, l_i\right)}...
user avatar
0 votes
0 answers
25 views

Finding a invariant subspaces for a specific matrix, but this time: over C

The matrix I found a good algorithm here, ( Finding a invariant subspaces for a specific matrix ) but this time I want to find the invariant subspaces for a specific matrix OVER C (complex). does it ...
user avatar
-1 votes
1 answer
17 views

Prove that if the array A contains a sequence of n numbers, then there is an element $a_i$ in A, that is a peak [closed]

Let $A = (a_1, a_2,..., an_i)$ a sequence of $n > 0$ numbers. An element $a_i$ is a peak of the vector A so that: $ai \geq a_{i-1}$ and $a_i \geq a_{i+1}$ for $1 < i < n$, or $ai \geq a_{i+1}...
user avatar
  • 1
-1 votes
2 answers
89 views

Can every number be written as $2^{a_1}+\cdots+2^{a_n} + 1$?

I am reading an algorithm that calculates $x^y$. Basically it is about an implementation of a function $power(x, y)$ where $x$ is the base and $y$ is the exponent i.e. the power. The algorithm uses ...
user avatar
  • 1,507
1 vote
0 answers
30 views

Dijkstra's algorithm confusion

I have this graph: and I am trying to apply Djiktra's algorithm to find the shortest path from A to E. Here is my progress: However I havent understood what I have found.Okay I have some values for ...
user avatar
0 votes
0 answers
5 views

Simplex : minimum of objective function is zero when ..

I run simplex (hopefully right) with break ties rules and everything for a minimisation problem. If I end up with the same base made of variables that are not in the cost function and there's no ...
user avatar
4 votes
1 answer
97 views

Fast algorithm to embed a triangulation into plane

Let $G = (V, E)$ be a planar graph such that $|E| = 3|V| - 6$ (so $G$ must be a triangulation without Kuratowski subgraphs). Given the adjacent matrix $A$ of $G$, please design an algorithm to embed $...
user avatar
1 vote
0 answers
29 views

Finding the smallest box that would fit different sets or stacks of other boxes

I am trying to find an efficient way of solving this. I have 3 sets of boxes. Each set of boxes goes together. I want to find a one size bigger Box that can hold each of these sets. By this I mean one ...
user avatar
0 votes
0 answers
16 views

How do you calculate the best/worst case complexity of an algorithm?

I have been given the example: ALGORITHM 1: Require: $n \ge 0 $ $x \leftarrow 1$ $\;\;\;\;\;\;$for $i = 1$ to $n$ do: $\;\;\;\;\;\;\;\;$$x \leftarrow x \cdot i$ $\;\;\;\;\;\;\;\;$ $i \leftarrow i + ...
user avatar
0 votes
1 answer
74 views

Find a simple path in given tree with minimum number of edges

Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
user avatar
  • 1
1 vote
0 answers
52 views

A weirdly difficult question on probability of flipping a coin.

The Question: Assume the coin is perfectly fair, and that it cannot land on its side. Now let's imagine I throw the coin T times, it lands on the same side, X times in a row in T throws, what is the ...
user avatar
0 votes
0 answers
7 views

Select intermediate vertex with the shortest total route with Dijkstra's algorithm

I need an algorithm to select the intermediate vertex that has the shortest route between the source node s and the destination node h. There are midpoints (intermediate vertices) b in the set of ...
user avatar
1 vote
0 answers
35 views

Make n numbers equal

Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...
user avatar
  • 11
0 votes
0 answers
11 views

Given $n$ items each with value $X_i$ and $m$ parties, distribute the items such that each gets at least $Y_i$

So I wanted to make an algorithm for the above problem and it felt like a famous problem (felt like I heard it before) but couldn't find it. Anyone knows? I actually wanted to solve a little bit ...
user avatar
  • 169

1
2 3 4 5
214