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,344
questions
1
vote
1
answer
19
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 ...
- 133
0
votes
0
answers
17
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 ...
- 101
1
vote
1
answer
38
views
0
votes
0
answers
35
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
1
vote
1
answer
63
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 ...
- 23
1
vote
0
answers
9
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} = \...
- 23
1
vote
1
answer
433
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
2
answers
102
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 ...
-1
votes
1
answer
45
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......
- 1
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$ ...
0
votes
0
answers
26
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\...
- 1,564
0
votes
0
answers
10
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
3
votes
2
answers
371
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
10
votes
1
answer
615
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
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, <...
- 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 ...
- 1
0
votes
1
answer
32
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] ...
- 1
0
votes
0
answers
15
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
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 ...
- 12.5k
0
votes
0
answers
25
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,...
- 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 ...
- 11
-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 ...
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 ...
- 1
0
votes
1
answer
31
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)
...
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.
...
- 1
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 ...
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 $...
- 532
0
votes
2
answers
32
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:
...
- 167
1
vote
1
answer
47
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 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 ...
- 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?
- 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 ...
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: <...
- 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$ ...
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 ...
- 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 ...
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 ...
- 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 ...
0
votes
0
answers
13
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 ...
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:
...
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 ...
- 136
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 ...
- 55
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{...
0
votes
1
answer
88
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 ...
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$ ...
- 67
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 ...
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 ...
- 1
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. ...
- 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 ...
- 13
1
vote
1
answer
64
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 ...
- 11