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.

7,634 questions
Filter by
Sorted by
Tagged with
28 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
110 views

93 views

Minimum-cut with minimum number of edges

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph. Firstly, let'...
30 views

Solving recurrences (tree method) with square roots

I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root: $$T(n) = 4T(n/2) + n^2\sqrt{n}$$
772 views

Find shortest path that visits all nodes in a given set of nodes

Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice. ...
29 views

Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
67 views

Solve recurrence relation that depends on depth of recursion

The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is: A frog is sitting on the edge of a pond facing ...
24 views

Counting step in Gale-Shapley Algorithm(Deferred Acceptance Algorithm)

Imagine there is a modified version of many-to-one school choice matching with Deferred Acceptance Algorithm(DAA): other things will be the same as original DAA, except that for an unassigned student, ...
65 views

...
17 views

What is the conversion engine problem related to?

I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given ...
1k views

How to find min or max in constant time using infinite # processors?

Given $n$ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ...
17 views

Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
13 views

Searching a hierarchy for progressive node criteria

In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc. I am ...
314 views

Minimize Manhattan distance travel algorithm

I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has. Say I have a matrix like:  \begin{array}{|r|r|r|} \hline \...
14k views

Show how to do FFT by hand

Say you have two polynomials: $3 + x$ and $2x^2 + 2$. I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how ...
315 views

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching? It is a long shot but it is often an ...
59 views

Running time of algorithm (effect of j*j in for loops) - Theta Runtime

In Theta notation what are the running times of these algorithms? Algorithm 1 for i=1..n j=1 while j*j <= i: j = j + 1 Since the outer loop ...
47 views

Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail? If we divide into ...
44 views

generating all pairs

suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t each number should be in one pair and also every number ...
2k views

3k views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n =$ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
39 views

Intuition behind this specific algorithm for time series

Going through the EPI book and I need some help understanding this part. There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The ...
111 views

Concatenate multiple integer arrays such that number of inversions in resulting array is minimal

Given N arrays of variable length. Find a way to concatenate the arrays in such a way that the number of inversions is minimum An inversion for an array Arr can ...
87 views

Elegant algorithm to semi-decide if two lambda calculus terms are equivalent

Given two lambda terms $t_1$ and $t_2$, it is semi-decidable if they are equivalent (i.e. can be rewritten as each other using alpha, beta, and eta conversions). An algorithm to do this is to try ...
35 views

Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

I am looking for some sort of communication or consensus algorithm with the following properties: Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties) ...
35 views

Minimum time to assemble multipart object

I've been asked to do this task in an online assessment. I've passed, so my solution is supposedly correct, but I am unable to prove it. The task is: Given a set of parts (array of integer part sizes)...