Skip to main content

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
2 votes
0 answers
27 views

What are the fastest (in terms of Big O complexity) algorithms for estimating the spectral norm of a symmetric matrix?

I know that the norm can apparently be computed with Lanczos iteration which is $O(dnm)$ but are there any methods that have equally low or lower complexity for finding the (possibly inexact) spectral ...
ufghd34's user avatar
  • 81
1 vote
0 answers
25 views

How to change an iterative linear interpolation into a formula?

I'm programming a game which needs to perform a simple linear interpolation in an iterative manner on every frame the game draws the screen. See the below example: ...
user19179144's user avatar
1 vote
0 answers
63 views

How to make it more optimal?

Recently I encountered a problem like this : You are given an array $a$ consisting of includes $n$ elements integer values . Define $S$ and $T$ as follows for a subarray in the range $[i;j]$ where $(1≤...
provip's user avatar
  • 11
3 votes
2 answers
65 views

Given $k \in \mathbb{N}$, find the min sum of k different pairs $\sum_{i=1}^{k}(a_{i}+b_{i})$ where $(a_{i},b_{i})\in\mathbb{N}\times\mathbb{N}$

Problem set Given $k\in\mathbb{N}$ (positive integer) I want to find the minimum sum over $k$ different pairs, where the pairs are of the form $\left(a_{i},b_{i}\right)\in\mathbb{N}\times\mathbb{N}$, ...
linuxbeginner's user avatar
0 votes
1 answer
32 views

Achieving parallel wires with 180-degree rod rotations in an interconnected node system

We have 5 nodes on the left and 5 nodes on the right. You can imagine it this way: the nodes are on parallel rods and are connected with wires so that initially the wires are all parallel. We'll call ...
H-a-y-K's user avatar
  • 717
1 vote
1 answer
52 views

Prove that a fuction $T(n)$ is $O(n)$ [closed]

I'm studying algorithms and i have to prove that $T(n) = O(n)$ where $T(n) = \frac{1}{2}n^2 + 3n$ I'd like to submit an observation of mine and ask if it's correct. If $T(n) = O(n)$ than there exist ...
Talete's user avatar
  • 33
10 votes
1 answer
311 views

Algorithm for finding intersection of two groups from generators

Say I have two subgroups of $S_n$ defined from their generators. E.g. $G_1 = \langle (0 3 4 1), (0 3 2 1 4)\rangle$ and $G_2 = \langle (4)(0 2 3 1), (0 4 3 2 1)\rangle$. Their intersection can be ...
Thomas Ahle's user avatar
  • 4,814
0 votes
0 answers
48 views

Does the circle packing theorem result in the smallest radius? [closed]

I have a problem where I am given n circles, not necessarily of the same radius. I need to pack them in the smallest circle possible. The radius of a circle may repeat and the number of circles is not ...
user23314623's user avatar
2 votes
0 answers
46 views

Converting "improper" partial order to total order

I suspect that if I knew what to search for, this would be easy to find an answer to, but I don't know what the proper name is for the input portion of the problem statement. I have a set and a ...
BCS's user avatar
  • 663
0 votes
0 answers
28 views

finding a property testing algorithem for diameter approximation

given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem ...
adonis abboud's user avatar
0 votes
0 answers
38 views

Can distinct elements in a random sub-sample be an indicator of distinct elements in the population?

We have a sequence of elements $D = <a_1,a_2,...a_m>$. Let $a_i$ come from $[n]$. Our goal is to estimate the number of distinct elements in $D$. We use a simple idea. We have a set $B=${} and ...
SagarM's user avatar
  • 1,799
1 vote
1 answer
61 views

Seeking Algorithm to Solve a Convolution Integral or Directly Convolve Two CDFs

Convolution of CDFs in Polynomial Form Hi everyone, I'm working on a project where I need to find a way to directly convolve two cumulative distribution functions (CDFs) given in polynomial ...
guttf's user avatar
  • 21
-3 votes
0 answers
18 views

A Modification of the LLL Reduction Algorithm [closed]

Am looking at an implementation of the A Modification of the LLL Reduction Algorithm by M Pohst. Anyone know ? https://www.researchgate.net/publication/...
adam doo's user avatar
0 votes
0 answers
67 views
+400

Why does learning theory study generalization bounds?

Disclaimer: I know that mathematics needs no external motivation to be developed, and that such view is (in the long term) helpful even for applications. Nonetheless, I believe it is crucial for ...
Alek Fröhlich's user avatar
0 votes
1 answer
34 views

Create a regular n-gon from sides and bounds width [closed]

I am trying to create a regular polygon with an arbitrarily number of sides with the starting parameters: number of sides, width of bounding box. And the polygon should have an edge at the base. For ...
Barreto's user avatar
  • 131
3 votes
1 answer
70 views

An efficient algorithm for determining whether a quartic with integer coefficients is irreducible over $\mathbb{Z}$

I'm interested in what efficient algorithm could be used for determining if a quartic polynomial with integer coefficients is irreducible over $\mathbb{Z}$. For quadratics and cubics it's not too bad, ...
Robin's user avatar
  • 3,930
1 vote
0 answers
35 views

Derive Lanczos algorithm by imitating the derivation of Arnoldi iteration algorithm.

If A is Hermitian, then everything above simplifies (e.g., Hessenberg matrices turn into tridiagonal), and we get what is know in the literature separately as Lanczos iteration. My attempt:- ...
Unknown x's user avatar
  • 839
1 vote
1 answer
30 views

Partition algorithm for minimal summation

Assume 2 sets of integer $A=\{a_1,...,a_n\},B=\{b_1,...,b_m\}$ I need to find a target $n$ partition of $B$, denote $B_1,...,B_n$ such that the maximum of $a_i+\sum_{b\in B_i}b$ is minimal. I came up ...
Shore's user avatar
  • 343
-1 votes
0 answers
37 views

Resampling of unknown function to produce uniform distribution iteratively without rejection sampling

Say there is an function $f(x) = y$ where $x$ is a vector in $\mathbb{R}^n$ and outputs value $y$. $f$ outputs an unknown distribution given an input that follows a continuous uniform distribution. Is ...
Zappy's user avatar
  • 15
-1 votes
1 answer
31 views

Flajolet-Martin algorithm error estimate [closed]

I'm studying the Flajolet-Martin algorithm for counting distinct elements in a wider set of elements, but I got stuck trying to understand the error estimate of the algorithm. Here ...
JayK23's user avatar
  • 101
5 votes
1 answer
101 views

Transfering colored balls from random bags into identical ones

Let's consider the following scenario: There are $n$ colors, and there are $n^2$ colored balls, where we have $n$ balls of each of the $n$ colors. There are also $n$ bags $[b_1,b_2,\dots,b_n]$ where ...
EnEm's user avatar
  • 938
0 votes
0 answers
44 views

What does "ab!" mean in Markov algorithm?

I can't find information neither understand what does ab! mean, to be accurate - what does the "!" mean in the Markov algorithm? Is it just a sign more ...
stephan's user avatar
1 vote
0 answers
39 views

about the mathematics of sorting networks from computer science

Well, I had some searching about https://en.wikipedia.org/wiki/Sorting_network but it looks to me that all my findings focus on programming issues (in which I'm interested, too) but lack a clear ...
Gyro Gearloose's user avatar
0 votes
0 answers
12 views

An algorithm of Max-Cut

Suppose we have an $\alpha$-approximation algorithm $A$ for the Max-Cut problem. On a graph with $n$ vertices and $m$ uniformly weighted edges, the runtime of $A$ is $f(n,m/n)$, where $f$ is a ...
Lagranngekmno4's user avatar
1 vote
0 answers
27 views

Knapsack with fixed number of bins?

Constant: d, a fixed number of bins/sacks Input: $v_1,v_2,...,v_n$ item profits, $0<w_1,w_2,...,w_n\leq1$ item weights. Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
alon's user avatar
  • 11
0 votes
0 answers
25 views

How an algorithm is implemented in FOL?

According to Gödel's theorem on expressibility, every recursive relation is expressible, every recursive function is representable. I looked at the proof of this theorem, and the proof seems to make ...
spacemonkey's user avatar
0 votes
0 answers
31 views

Formalities on loop invariant - algorithms

When proving an algorithm using a loop invariant, we need to check these three things. The loop invariant holds before the loop is entered (initialization) If the loop invariant holds before the loop ...
Agustin G.'s user avatar
0 votes
0 answers
31 views

Value range of dual variables in Jonker-Volgenant algorithm for solving linear assignment problem

In A shortest augmenting path algorithm for dense and sparse linear assignment problems an algorithm for the Linear Assignment Problem is given, with a $O(N^3)$ time complexity (where $N$ is the "...
Oersted's user avatar
  • 161
0 votes
2 answers
171 views

Lumbroso "dice roller", correctness of the algorithm for 32 bit integers

In this paper Optimal Discrete Uniform Generation from Coin Flips, and Applications Lumbroso develop a nice algorithm: The FAST DICE ROLLER algorithm; it returns an integer which is uniformly drawn ...
Massimo's user avatar
  • 139
0 votes
0 answers
11 views

For $n,m \geq 1$, when do exist $p_1,\dots,p_n \in S_m$ so that they coordinate-wise map $X$ to $X'$, where $X,X' \subset \{1,\dots,m\}^n, |X|=|X'|$?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. Suppose $p_i \in S_m, i = 1,\dots,n$. Define $P_{p_1,\dots,p_n}: Y \rightarrow Y$ as follows: $\forall y=(y_1,\dots,y_n) \in Y, P(y) = (p_1(y_1)...
H-a-y-K's user avatar
  • 717
0 votes
1 answer
68 views

Tried finding an efficient algorithm for a 4-digit number guessing game, knowing only the number of digits on correct positions..

I've been playing a game similar to Bulls and Cows, but it goes like this: one player has to pick a random $4$ digit number. Digits can repeat, any digit between $0$ to $9$ and, you only get the ...
nex's user avatar
  • 3
2 votes
1 answer
60 views

Is this looser case of the maximal clique(connected subgraph) problem also hard?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. We'll call vectors $(x_1,\dots,x_n), (y_1,\dots,y_n) \in Y$ independent iff $\forall 1 \leq i \leq n, x_i \neq y_i$. There can be at most $m$ ...
H-a-y-K's user avatar
  • 717
1 vote
1 answer
33 views

Is there any algorithm to calculate this ranking method quickly?

I want to rank the 20 teams in the English Premier League. Say that each team are assigned to the number 1 through 20, defining their ranking, no ties. There would be $20!$ number of permutations for ...
Germaniac's user avatar
0 votes
0 answers
20 views

Finding any spanning tree that covers a subgraph of a directed graph

My work (programmer) has a business use case that basically boils down to the following graph theory problem: Given a directed graph $F$ and a subset of vertices / subgraph $G = v_1, v_2, ... , v_k$ ...
Pranav Rudra's user avatar
0 votes
0 answers
15 views

The elements of a list of length n that take the greatest number of function calls to be found using binary search

I was wondering if there was any information on determining the indices of the elements that take the greatest number of function calls to be found, if binary search is used to find the element, in a ...
nazorated's user avatar
0 votes
0 answers
46 views

Is this algorithm considered greedy?

The problem: Given a list of n cities, each one at distance D[i] from the beginning of a positive half-axis, find the least possible number of antennas, each one having a radius r, so that every city ...
Dimitris Gavriil's user avatar
0 votes
0 answers
36 views

Question about proof, using contrapositive, of Lamé’s theorem

Given the following lemma: If $a > b \geq 1$ and the call EUCLID(a, b) performs $k \geq 1$ recursive calls, then $a \geq F_{k+2}$ and $b \geq F_{k+1}$, which can be proved by induction, how is the ...
Hugh Mann's user avatar
1 vote
1 answer
32 views

Testing for strong homomorphism in polynomial time

Let $G$ and $H$ be graphs. We say that a map $f:V(G)\rightarrow V(H)$ is a strong homomorphism if for all $u,v\in V(G)$ it holds that $(u,v)\in E(G)$ if, and only if, $(f(u),f(g))\in E(H)$. Fix $H$ ...
Emil Sinclair's user avatar
1 vote
0 answers
25 views

Infinitesimal rank 1 update to eigendecomposition

Consider a Hermitian matrix $H$ for which we know the decomposition $Q \Lambda Q^\ast$. Let $H'= H + \epsilon~x x^\ast$ for a small $\epsilon$. What is a good way of computing the decomposition of $H'$...
Arthur B.'s user avatar
  • 962
0 votes
0 answers
34 views

Minimum number of measurements required to find heaviest and lightest from a group of idetntical looking balls having distinct weights.

You are given 68 identical looking balls, each with a distinct weight. You are given a common balance using which you can compare weights of any two pair of balls with a single measurement. Describe ...
Arvind H's user avatar
0 votes
2 answers
70 views

Interpreting an algorithm as an integral

$\text{Consider the following algorithm:}$ ...
Hussain-Alqatari's user avatar
2 votes
0 answers
42 views

Does every collection of edges between two sets of vertices in a plane have a "perimeter" edge suitable for induction inwards?

Joel Hamkins posted this nice problem: https://x.com/JDHamkins/status/1790582025977577591 I quote: Suppose you have 1000 white points and 1000 black points in the plane, no three collinear. Can you ...
it's a hire car baby's user avatar
1 vote
0 answers
21 views

What are the bounds on the convergence rate of Gradient Descent for non-convex quadratic polynomials defined over a hypercube?

I know of several function-independent complexity bounds on convergence rates of (projected) Gradient Descent (to a KKT point of course) e.g: https://doi.org/10.1007/s10107-019-01406-y http://...
ufghd34's user avatar
  • 81
0 votes
0 answers
24 views

Closest edge to a rectangle in a plane of rectangles

I have a 2D plane (with discrete points) that contains arbitrary-sized rectangles and all rectangles are axis aligned. I have their coordinates (upper-left) and sizes (length and breadth). Suppose I ...
Harsh's user avatar
  • 1
3 votes
1 answer
161 views

How to solve a given combinatorial problem?

Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
LaVuna47's user avatar
1 vote
1 answer
27 views

Algorithm to find if intersection of convex sets is empty [closed]

Is there an algorithm to find if the intersection of two convex sets is empty or not. The projection onto convex method (POCS) and similar methods finds a point in the intersection, but will they ...
user221985's user avatar
3 votes
1 answer
92 views

Least number of circles required to cover a continuous function on a closed interval.

Now asked on MO here. This question is a generalisation of a prior question. Given a continuous function $f :[a,b]\to\mathbb{R}$, what is the least number of circles with radius $r$ required to ...
pie's user avatar
  • 5,987
0 votes
1 answer
24 views

Relabelling Sets

Given a list of $n$ Sets $S_1,S_2,S_3,...,S_n$ such that each Set $S_i$ contains some integers between $1$ and $n$, for example $S_1 = \{2,3\} ,S_2 = \{1,2\} , S_3 = \{1,3\}$ which we can relabel to $...
Ahmad's user avatar
  • 712
1 vote
1 answer
29 views

Time complexity for evaluating prime factors using trial division

I am trying to find the prime factors and I am doing so by going through each number from $d=2$ upto $d=\lfloor{\sqrt{n}\rfloor}$, and dividing the remaining number by $d$ until it cannot be divided ...
Paras Khosla's user avatar
  • 6,411
1 vote
0 answers
85 views

Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?

Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
Amir's user avatar
  • 7,919

1
2 3 4 5
231