Share Your Experience: Take the 2024 Developer Survey

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

11,531 questions
Filter by
Sorted by
Tagged with
39 views

### Buy two chocolates when want MAXIMUM nonegative spend

This is a self-study inspired by the trivial https://leetcode.com/problems/buy-two-chocolates/. Basically the question is as follows: if you have a value of money m ...
• 195
1 vote
99 views

### Restore the original array after merge Sort based on it's steps

i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
• 45
202 views

### is there an efficient algorithm to find the optimal partition of a matrix?

Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down ...
• 996
15 views

### Looking for an algorithm f(min, max, progress[from 0.0 to 1.0]) = value between min and max

I am writing a program where I need to have a circle animation that grows from a start value to a end value and back to the starting value. I was able to come up with a semi-solution. ...
• 101
1 vote
75 views

### Does $\mathsf{P} = \mathsf{NP}$ imply $\mathsf{PO} = \mathsf{NPO}$?

The class $\mathsf{NPO}$ is defined as optimization problems such that the corresponding decision problems defined with a threshold are in $\mathsf{NP}$. Let $A$ be an optimization problem and $B$ a ...
• 15.7k
1 vote
110 views

### What's the name of the genre of algorithms for efficiently collecting common factors?

I'm working with sparse vectors represented as index (array of unsigned integers) and coefficient (array of floats with the same ...
• 139
1 vote
129 views

### Examples of problems in P but with verifiers with many computations

Let me first specify my question. I am looking for decision problems with polynomial algorithms but such that the simpliest or fastests verifiers do many computations. Here by verifiers I mean both ...
• 153
1 vote
129 views

### Median of two sorted arrays

Two sorted arrays A and B are given having size l and m ...
143 views

### O(n) algorithm to find primes up to n

I don't know the name of this algorithm, but anyway it was interesting to share (btw Linear sieve, Sieve of Atkin and Sieve of Pritchard performs better) The main idea is to use the Fundamental ...
96 views

### "Unbounded" binary search in $\log_2(n) + O(?)$ comparisons

Binary search is the well-known algorithm that compares the input value to an entry in a sorted array, and based on the result then decides to check the same input value against another entry either ...
• 2,521
166 views

### Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem: Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$? (More ...
28 views

### Is it possible to perform clause-pair minimization on a CNF instance in $o(n^2)$ time?

Let $\varphi(X)$ be a boolean formula in CNF over a set $X$ of boolean variables $x_1,x_2,...,x_n$. Let $c_i$ denote $i^{th}$ clause in $\varphi(X)$. $x_j^0$ denotes $\overline{x_j}$ and $x_j^1$ ...
• 1,664
82 views

### Idea for Improving Heapsort

i have an idea of enhancing the heapsort by finding the max and min simultaneously and then swapping the max into the last node, and then the min will be swapped into the second to the last node, and ...
219 views

• 23
1 vote
461 views

### Find the smallest subarray with sum larger than a threshold

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
• 109
1 vote
216 views

### Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
51 views

• 1,942
13 views

### Identifying peaks at every cluster

I have a data set showing different clusters of data points and was attempting to find a way to get the peak of at every cluster. Comparing the moving average between a set of points does not work as ...
• 101
417 views

### Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
• 53
654 views

### Are there associative cryptographic / collision resistant hashes?

Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key. For content ...
• 263
61 views

### Find maximum sized rectangle on a plane

I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
• 183
1 vote
245 views

### The second shortest path on a directed graph [closed]

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between $s∈V$ and $t∈V$. The farthest I managed to ...
• 71
1 vote
92 views

### Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
• 11
100 views

### Dynamic programming problem for minimum cost tower placement

I have an algorithmic problem in which I have a highway that is a straight line of length $n$ and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
63 views

### Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
• 15.7k
35 views

• 11