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

11,540 questions
Filter by
Sorted by
Tagged with
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 ...
• 81
1 vote
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: ...
1 vote
63 views

• 717
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 ...
• 3
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$ ...
• 717
1 vote
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 ...
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$ ...
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 ...
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 ...
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 ...
1 vote
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$ ...
1 vote
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'$...
• 962
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 ...
70 views

### Interpreting an algorithm as an integral

$\text{Consider the following algorithm:}$ ...
• 5,439
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 ...
• 9,305
1 vote
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://...
• 81
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 ...
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 ...
• 33
1 vote
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 ...
• 111
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 ...
• 5,987