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
1
vote
2
answers
94
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 ...
5
votes
2
answers
2k
views
Time complexity for count-change procedure in SICP
In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
- 105
1
vote
1
answer
24
views
0
votes
0
answers
7
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
0
votes
1
answer
109
views
Suggest good books for Advanced Data Structure and Algorithms
I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded ...
CommunityBot
- 1
0
votes
0
answers
28
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
57
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 ...
0
votes
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} = \...
- 13
1
vote
1
answer
423
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 ...
- 28.4k
2
votes
1
answer
72
views
A version of Bareiss algorithm or similar for symmetric matrices
A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
CommunityBot
- 1
0
votes
1
answer
37
views
Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :
...
CommunityBot
- 1
-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......
- 28.4k
0
votes
1
answer
44
views
Trying to understand the time complexity of IDDFS
I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.
For BFS it is ...
CommunityBot
- 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
1
answer
69
views
Optimal scheduling order for two queues of jobs
I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed ...
CommunityBot
- 1
0
votes
1
answer
62
views
Given required total area and capacity, choose an amount for each of three given modules
Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
CommunityBot
- 1
0
votes
0
answers
19
views
Which one of the problems belong to P? [duplicate]
Suppose $P\neq NP$. Which one of the mentioned problems 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 ...
- 1,564
0
votes
2
answers
121
views
How to avoid costly square root operations in A* algorithm?
As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
- 28.4k
2
votes
1
answer
170
views
Design a data structure with constant insertion and sublinear range maximum query
Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
CommunityBot
- 1
0
votes
1
answer
35
views
Finding the mode of a continuous distribution
I need to find the empirical mode of a sample of numbers taken from a continuous distribution (i.e. floating-point data).
I can think of using an histogram, but choosing an appropriate bin size does ...
CommunityBot
- 1
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 ...
- 101
10
votes
1
answer
610
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
3
votes
2
answers
366
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 ...
D.W.♦
- 156k
0
votes
1
answer
51
views
Memory allocation algorithm over a growing storage
I am going to story data in a growable persistent storage. I need to implement allocation/deallocation (like malloc/free and possibly realloc but in Rust) of continuous regions of memory on this ...
CommunityBot
- 1
0
votes
2
answers
53
views
Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)
The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added):
2.3.2 Analyzing divide-and-conquer algorithms
[...]
A recurrence for the running time of a ...
CommunityBot
- 1
4
votes
1
answer
143
views
Survival algorithm for Network deterministic failures
Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
CommunityBot
- 1
3
votes
1
answer
448
views
Tree traversal with conditional summing values from nodes
Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
CommunityBot
- 1
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, <...
D.W.♦
- 156k
1
vote
1
answer
115
views
Comparing variable image to static image
What are Levenshtein distance algorithms, but for images?
I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created)
For example,
...
CommunityBot
- 1
20
votes
3
answers
24k
views
What is the difference between the fundamental matrix and the essential matrix?
Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision?
How are they different, and how can each be used in ...
- 578
3
votes
1
answer
183
views
Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)
I was studying Paxos from:
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
Recall that Paxos is a distributed system algorithm with the goal that the processes ...
CommunityBot
- 1
0
votes
2
answers
118
views
Why is there no polynomial time verifier for N Queens
The N-Queens in question is referring to the one where it is interested in finding all solutions for some natural number n. I just read about the idea of a verifier being an algorithm that verifies ...
CommunityBot
- 1
1
vote
1
answer
306
views
Appropriate graph clustering algorithm
I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I ...
CommunityBot
- 1
0
votes
1
answer
27
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] ...
- 28.4k
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
1
vote
1
answer
136
views
Sorting O(log n) elements in O(n) time
I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time.
What I am ...
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,...
1
vote
1
answer
46
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 607
-1
votes
1
answer
65
views
The three elevator problem
There are three elevators in a building that has twelve floors. Find an algorithm that needs to find the best possible way for the elevators to stop at any particular floor considering the traffic ...
- 771
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 ...
0
votes
1
answer
2k
views
Proof that median of an array is the number that minimizes the sum of manhattan distance to all points
Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come ...
- 103
0
votes
1
answer
37
views
Find combination of elements, one element from each list, whose average is the closest to a target number
Problem:
There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1.
The lists have equal length.
There is a target number T.
Find what is the combination of elements, one element from each ...
- 592
-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
1
answer
36
views
Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
CommunityBot
- 1
3
votes
1
answer
713
views
calculating the string similarity of an optimal alignment
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
CommunityBot
- 1
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 ...
1
vote
1
answer
465
views
Find all polygons from a set that overlap a given polygon (convex case)
Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
CommunityBot
- 1
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
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
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