# 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,347 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
30 views

...
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 ...
1 vote
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 ...
1 vote
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} = \...
1 vote
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 ...
1 vote
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 ...
44 views

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 ...
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 ...
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 ...
1 vote
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, <...
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 ...
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] ...
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 ...
1 vote
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 ...
24 views

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: ...
1 vote
46 views

### Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
1 vote
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 ...
1 vote
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?
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 ...
54 views

### artificial intelligence [closed]

how to solve this puzzle in A* algorithm with the Manhattan distance heuristic
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: <...
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$ ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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: ...
1 vote
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 ...
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 ...
129 views

1 vote