# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

10,493 questions
Filter by
Sorted by
Tagged with
57 views

1 vote
34 views

### Hints for efficient computation of the maximum length of a binary sequence

Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
141 views

### Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem: Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
72 views

### Does this greedy algorithm minimize the sum of the diameters of two clusters?

Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the ...
1 vote
46 views

### Space-efficient way to prove that a data has been processed before

Suppose that I have a stream of data packets in the form of unsigned 64 bit integers. And I want to make sure that I am not processing the same packet content more than once. A way of doing this would ...
1 vote
29 views

### Is there an algorithm for generating non comparable boolean vectors?

First some context: A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself. The dynamical behavior of a ...
16 views

### Big O notation References and Resources

I am new to time complexity, and Big O notation. I have this question pertaining to this code in Python 3.X: ...
641 views

### Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$, Describe an algorithm that determines if the MST ...
118 views

### Maximum sum of values in a square grid (one in each row/ column)

this is my first post here so bare with me :). What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from ...
21 views

### How to create tensors at runtime?

I have a small personal CAS project around linear algebra which involves, among other things, manipulating tensors. When I talk about tensors, I mean them according to the physical / mathematical ...
1 vote
49 views

### Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
1 vote
77 views

### How to tell if I know algorithms & I learned it right?

Notes I apologize if the question is not formed well, I tried my best. "Only" means anything else is discarded. A stupid man’s report of what a clever man says can never be accurate, ...
1 vote
26 views

### Hashing for dot products

I've come across this problem that uses hashing to compute dot products (for non-negative vectors). Suppose we are in $d$-dimensional space and $M$ will be our target for our hash. That is we have a ...
1 vote
72 views

### Amortized analysis (accounting/banker's method) for tree operations

Suppose we have a tree data structure with root $r$ with two operations: Add($x, y$) - adds the node $y$ as a child to the node $x$ Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct ...
20 views

### Psuedo Code for A* with Adjency Matrix Graph

There are algorithms for A* but the algorithms use a pointer based representation of a graph instead of an adjacency matrix of a graph. I would like to know how to do the algorithm with an adjacency ...
14 views

### non-linear lower bounds for polynomial time decision problems [duplicate]

Are there any decision problems that have deterministic polynomial time algorithms and proven non-linear lower bounds?
1 vote
34 views

### Order List of Sets so Adjacent Sets are Disjoint

Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$. Now I'...
32 views

### How to compute efficiently the winner of a chess match where players are algorithms

This is my problem: The chess match starts with a board where chess pieces are randomly placed. Both players are controlled by the same deterministic algorithm so if two games start with the same ...
1 vote
21 views

### What is "energy" in computer vision

I keep seeing the term "energy" used in computer vision literature, specifically when speaking about Image Segmentation. For example on this page on Graph-Cut. I'm just wondering if someone ...
1 vote
33 views

### Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$

Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math For completeness, below is the problem ...
2k views

### What is the fastest algorithm to approximate an irrational number with specified precision?

Problem Background: Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
1 vote
35 views

### Prove an edge that minimizes the Euclidean distance crossing a cut is in the Delaunay triangulation

Let $P$ and $Q$ be two disjoint point sets in the plane. (Think of them as a red point set and a black point set.) Let $p \in P$ and $q \in Q$ be two points from these sets that minimize the Euclidean ...
86 views

### Is O(k*n) in this case linear?

Problem: find sum of k element in array and it is biggest? time complexity of my algorithm is O(k*n).Is it linear complexity?
1 vote
29 views

### Are there any algorithms that become much easier to design & implement in reversible computation settings?

If your program can move backwards (even if just for a preset amount like 10,000 atomic steps), then it's easier to do these things: Undo/Redo history (automatically for everything). This can be a ...
27 views

### How to find the second most closest pair of points modifying the Divide and Conquer?

I know the Divide and conquer approach for the finding the closest pair of points and the proof of correctness. Can we modify it in such a way so that , we can find the 2nd most closest pair. I am ...
87 views

### Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking

I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article. ...
35 views

### Fast Algorithm To Compute Gradient Of Gaussian Blur

what is the fastest algorithm to compute the gradient of the Gaussian blur of a (grayscale) image, with a blur radius of around 100 pixels, where smoothness of the result is important to me, i.e. no ...
26 views

### Bellman Ford may not update distance correctly by termination?

Consider the example shown in the above figure. Let's consider two orders (1) S, A, B and (2) S, B, A for traversing the graph and updating the distance d (numbers in circle are distance d): 1- start ...
85 views

### What is ridge in hill climbing algorithm?

I am studying hill climbing algorithm and this topic seems so confusing. What is ridge basically? Can you show an example while searching using hill climbing when ridge occurs? I have researched in ...