Skip to main content
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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
JoeTheShmoe's user avatar
1 vote
1 answer
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 ...
vhd's user avatar
  • 45
3 votes
1 answer
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 ...
Simd's user avatar
  • 996
0 votes
0 answers
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. ...
Nissaba's user avatar
  • 101
1 vote
1 answer
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 ...
Nathaniel's user avatar
  • 15.7k
1 vote
0 answers
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 ...
tutizeri's user avatar
  • 139
1 vote
1 answer
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 ...
Yuumita's user avatar
  • 153
1 vote
1 answer
129 views

Median of two sorted arrays

Two sorted arrays A and B are given having size l and m ...
Shashikant's user avatar
0 votes
0 answers
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 ...
Lorenzo Tinfena's user avatar
5 votes
1 answer
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 ...
Albert Hendriks's user avatar
9 votes
1 answer
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 ...
Mees de Vries's user avatar
0 votes
0 answers
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$ ...
rus9384's user avatar
  • 1,664
0 votes
1 answer
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 ...
user166089's user avatar
3 votes
5 answers
219 views

How to do better than brute-force for this problem?

I am trying to solve a competitive-programming-style problem which I've boiled down to the following: given two arrays $a, b$ of length $n$, where $a_i, b_i > 0$ for all $i=1\ldots n$, compute $$\...
Archie Gertsman's user avatar
4 votes
3 answers
103 views

Element that occurs more than one third of the time in a sorted array - constant time?

Given a sorted array of positive integers that is guaranteed to have some unique entry that occupies more than $1/3$ of the entries, is there an algorithm to determine this entry in $O(1)$ time? Some ...
user165069's user avatar
4 votes
1 answer
398 views

Read-once complexity of a matrix problem

Given a binary $n \times n$ matrix, we would like to decide whether there is a row or a column which consists entirely of $1$s. The caveat is that after we read an entry of the matrix, it is erased. ...
Yuval Filmus's user avatar
-2 votes
1 answer
69 views

$N \times N$ Image Processing Time Complexity: Grayscale to Binary using Median Step Function

In an image processing system, an algorithm processes an $N \times N$ image with each pixel being a number between $0$ and $255$. It finds the median value $M$ in the $N \times N$ image and applies ...
Qammy's user avatar
  • 9
5 votes
3 answers
1k views

Small doubt concerning cardinality of set of problems and algorithms?

I write this question because my professor in Algorithm Analysis briefly mentioned some property related to the countability/uncountability of the set of strings/problems/algorithms and the consequent ...
Sho's user avatar
  • 159
2 votes
1 answer
23 views

Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval

PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-...
Shred's user avatar
  • 121
-3 votes
3 answers
139 views

Write an Algorithm that Outputs Whether a Number is a Perfect Square [closed]

Write an algorithm that takes an arbitrary natural number and returns a boolean of whether the number is a perfect square. Sketch a flowchart of the algorithm. My approach is that a natural number $n$ ...
math lover's user avatar
1 vote
2 answers
116 views

I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
Hardik Dhuri's user avatar
1 vote
1 answer
134 views

Hoare Logic: Identifying Hoare Triple given a simple function

The program is designed to start with values for $x$ and $y$. The variables $u1$​ and $u2$​ are intended to represent $x$ and $y$ in ascending order. Provide suitable preconditions and postconditions ...
User's user avatar
  • 9
2 votes
1 answer
69 views

Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)

I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\{\mathbf{0}\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\...
multiplywithadot's user avatar
2 votes
1 answer
33 views

Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
caitlin's user avatar
  • 21
1 vote
1 answer
118 views

Dynamic Programming problem about intervals

This is algorithms and data structures assignment and I have been thinking 3 days about it. You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in ...
guitarMan's user avatar
2 votes
1 answer
30 views

Hash function that returns the same result when the input is reversed

Do any hash functions exist that provide the same result if the input is reversed? If this is impossible, why is it impossible? I am interested in sending packets of constant size around a circuit in ...
Zaz's user avatar
  • 145
2 votes
0 answers
28 views

How does this partitioning problem map to studied problems?

I have a real-world (see background below) problem wherein a set $S = \{A,B,C,D...\}$ needs to be partitioned into set $P = \{ \{A,B\},\{D\},\{E,F\},\{C,G,H\},...\}$ where $P$ is required to have the ...
cms's user avatar
  • 121
2 votes
1 answer
46 views

Find the value of return variable based on the value of n?

...
Team B.I's user avatar
  • 263
0 votes
1 answer
64 views

Find multiple order-statistics of an array

Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i < m$ find $p_i$-th order statistics of array $a$ in $O(m log(n) + n)$? We can find order statistics separately, but it ...
  mozhayka's user avatar
1 vote
1 answer
524 views

How do I find time complexity of while loops?

I am designing a simple algorithm to be used at hardware level. And I want to find its time complexity. i=1 while(i<=n) { i=i*2; } How I'd go about finding ...
Team B.I's user avatar
  • 263
1 vote
0 answers
11 views

Confusion on the use of the chain-rule for the total derivative of the NLL Loss function

So my question is about when we want to find the total derivative of the NLL Loss function $L$ w.r.t. $w_i$. So the "pipeline" is often expressed as: $$\frac{\partial L}{\partial w_i} = \...
ZenPyro's user avatar
  • 23
1 vote
1 answer
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 ...
zebda's user avatar
  • 109
1 vote
2 answers
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 ...
Gary Drocella's user avatar
-1 votes
1 answer
51 views

Mergesort time complexity

Using the regular mergesort algorithm for a list, say $a[1...n]$, we call the merge function to merge, mergesort($a[1...\lfloor \frac{n}{2} \rfloor]$) and mergesort($a[\lfloor{\frac{n}{2}}\rfloor+1......
GaloisTH's user avatar
2 votes
1 answer
61 views

Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
30 views

Which one of the problems belong to P? [duplicate]

Suppose $P\neq NP$. The following problem can be solved in polynomial time? Given natural number $n$ and positive real numbers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$. The goal is to find $I\...
ErroR's user avatar
  • 1,942
0 votes
0 answers
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 ...
Nader's user avatar
  • 101
3 votes
2 answers
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 ...
xdaimon's user avatar
  • 53
10 votes
1 answer
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 ...
Benjohn's user avatar
  • 263
2 votes
0 answers
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, <...
popcorn's user avatar
  • 183
1 vote
0 answers
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 ...
Daniel's user avatar
  • 71
1 vote
1 answer
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] ...
patayala's user avatar
0 votes
0 answers
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 ...
Izzy Handkammer's user avatar
2 votes
0 answers
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 ...
Nathaniel's user avatar
  • 15.7k
0 votes
0 answers
35 views

Greedy algorithm for trading cryptocurrencies with perfect price information

Assume the following hypothetic scenario: You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
lafinur's user avatar
  • 195
1 vote
0 answers
40 views

How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
HelpmePlease's user avatar
-2 votes
2 answers
209 views

Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
Shawxing Kwok's user avatar
1 vote
0 answers
61 views

Necklace Alignment Problem

We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
Fireond's user avatar
  • 11
0 votes
1 answer
52 views

What's the Time Complexity and total no of iterations?

for a=1 to m means for(a=1;a<=m;a++) for i=1 to n for j=i to n c= c+1; The total no of iterations is O(n^2) ...
Vedant Khandelwal's user avatar
0 votes
0 answers
24 views

better ways to integer interpolation?

I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation. ...
박성재's user avatar

1
3 4
5
6 7
231