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
0 answers
9 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
  • 101
1 vote
1 answer
30 views

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

...
barnyard9's user avatar
0 votes
0 answers
29 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
59 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 ...
barnyard9's user avatar
1 vote
0 answers
7 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
425 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
95 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
44 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
0 votes
1 answer
32 views

Non-dominated maximal paths (DAG)

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $\quad\quad P$ is maximal and $\exists_{P^{'} \in D}(P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
23 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\...
MR_'s user avatar
  • 1,564
0 votes
0 answers
9 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
368 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
612 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
1 vote
0 answers
36 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
  • 31
0 votes
0 answers
42 views

The second shortest path on a directed graph

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 get ...
Daniel's user avatar
  • 1
0 votes
1 answer
30 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
12 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
1 vote
0 answers
53 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
  • 12.5k
0 votes
0 answers
24 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
  • 181
1 vote
0 answers
37 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
193 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
0 votes
0 answers
56 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
0 votes
1 answer
29 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
15 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
0 votes
2 answers
41 views

Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
Root Groves's user avatar
2 votes
0 answers
18 views

Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?

LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
chausies's user avatar
  • 532
0 votes
2 answers
30 views

Time complexity of algorithm involving function calls

Me again. This time I have a more general question. Suppose I have the following code snippet: ...
john doe's user avatar
  • 167
1 vote
1 answer
46 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 167
1 vote
0 answers
85 views

Can we compute most significant digit of a binary number in O(1) on RAM model?

Consider we use a RAM model with word length w (or if you really want a more exact model, you can use Knuth's MMIX instructions with w-bit numbers). Given a number n, we want to compute the most ...
Kaveh's user avatar
  • 22.2k
1 vote
1 answer
29 views

Independent sets generation in a graph

Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
maliya's user avatar
  • 11
0 votes
1 answer
16 views

Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
Maceo Cardinale Kwik's user avatar
-3 votes
1 answer
54 views

artificial intelligence [closed]

how to solve this puzzle in A* algorithm with the Manhattan distance heuristic
shar's user avatar
  • 1
0 votes
0 answers
18 views

How to check for correct order in a fill-in-the-blanks exercise

Suppose the following fill-in-the-blanks exercise: ___ ___ and ___ ___ went to the ___. Suppose the correct solution here is "John Smith and Mike Jones went to the pub". In other words: <...
Jakub's user avatar
  • 1
-4 votes
0 answers
36 views

Maximum possible coincidences? Python code please [closed]

Given $M = [0,4,8,15]$ as points on a real line place 2 points $C_1$, $C_2$ on the line according to the following conditions Both $C_1$ and $C_2$ cannot be placed at 0 or 15. Distance between $C_1$ ...
Vamsi Krishna Kunapareddy's user avatar
0 votes
0 answers
17 views

Runtime of randomization algorithm to find majority element in an array?

This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such ...
Shisui's user avatar
  • 111
0 votes
1 answer
24 views

Can Dijkstra's algorithm be used this way?

Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
Johnny Upman's user avatar
1 vote
0 answers
16 views

epsilon-optimality in cycle-cancelling for min cost flow

I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
AWhite's user avatar
  • 21
0 votes
1 answer
49 views

How to modify Dijkstra's algorithm to model the path of an electric car?

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks. Somebody online asked (but nobody ...
Johnny Upman's user avatar
0 votes
0 answers
12 views

Algorithm to find the number of N length sticks needed to cut into an array of various sized lengths (all <= N)

Given a length N (e.g. 20) and an array of lengths which are all <= N (e.g. [15, 1, 6]) I'd like an algorithm that finds the minimum number of N lengths necessary to be cut into the array of ...
ajHurliman's user avatar
0 votes
2 answers
22 views

How to calculate the time complexity if the upper bound is decreasing as well?

For example if the condition is i<=n, and the n is decreasing in the loops, how can i calculate the time complexity? Lets say we have nested loops like below: ...
Emad Kheyroddin's user avatar
1 vote
0 answers
21 views

What should be the personalisation vector for the personalised page rank algorithm?

I am trying to understand the personalised page rank algorithm. I have a graph with multiple types of nodes and I want to calculate how important other nodes are w.r.t these nodes. I am using ...
Deepak Patankar's user avatar
3 votes
1 answer
88 views

How many random bits does this algorithm use on average?

Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved ...
Ilkay Burak's user avatar
3 votes
0 answers
129 views

Recover unknown vector through shifted argmax queries

I am interested in finding an efficient algorithm for the following problem: Let $x \in [0,1]^n$ be some vector, with $x_n = 1$. We want to recover $x$, solely by asking queries of the form $\texttt{...
Florian Tramèr's user avatar
0 votes
1 answer
87 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
2 votes
2 answers
112 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
Hugh Mann's user avatar
2 votes
0 answers
37 views

Related papers about finding longest vector(maximum in magnitude) as subset sum from given set of 2d vectors [duplicate]

Given a set of 2D vectors. Find maximum magnitude of sum of a subset of the set. I want to do my undergrad thesis on this topic. Can anyone suggest me some existing papers related to this topic or its ...
Iridescent 53's user avatar
0 votes
1 answer
30 views

Optimal randomized algorithm for set cover

This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem ...
meeeeee's user avatar
0 votes
1 answer
30 views

Can an unreocognizable language be Turing-reducible to a recognizable language?

Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
Arthur's user avatar
  • 3
1 vote
1 answer
47 views

Maximum reachable checkers on a checkerboard

This is a problem inspired by a video game that I've been thinking about for a long while, and I haven't convinced myself that I can do any better than brute force + pruning techniques, which would ...
crs's user avatar
  • 13
1 vote
1 answer
63 views

Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University. I have recently got through three questions I found in an old exam: Is it possible to sort in asymptotically linear time ...
Lorenzo's user avatar
  • 11

1
2 3 4 5
227