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
1answer
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 ...
2
votes
1answer
110 views

Find N best subset of quotations

I am faced with the following problem; We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q_1 ... Q_k$. Each Quotation is a $M \...
1
vote
1answer
53 views

packing with time-variant weights

This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions. (If this is the wrong SE to ask this question, rather than downvoting it, could ...
2
votes
2answers
36 views

What does the following algorithm approximate? (Assume m>1,ϵ>0)

x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x); The answer is m½, its the Babylonian algorithm for square roots. I understand the ...
1
vote
1answer
82 views

Possible ways to have cross and full edges in a mincut maxflow

I am trying to solve the following problem about maxflow mincut it seems like my conclusion is incorrect and I am wonder where. There is no graph just following question. An edge e can be (x) ...
-1
votes
0answers
36 views

Finding the right algorithm

I am reading the book by Petkovsek et all "A = B". I am wondering which of the algorithms would better work in order to compute (or at least estimate) the following sum: $$ \sum_{m=0}^q\binom{q-m+\...
1
vote
0answers
40 views

What is the most straight forward, easy to verify algorithm to construct a valid password from a character stream?

Let's say we are given an infinite character stream like the following: nqDoo8NkPsDn0gVf(pAI)dwa^Vq7OfAgt@KDUkjN5ZXY1yK6w7ygW6S&@L0EsUEq9... What is the most ...
4
votes
1answer
407 views

2 approximation algorithm for the single machine scheduling problem

We are given one machine and $n$ jobs that we want to process. For the $n$ jobs we have the following data: $r_{1}, ... , r_{n}$ are the release times $p_{1}, ... , p_{n}$ are the processing times ...
8
votes
2answers
691 views

Is “ternary search” an appropriate term for the algorithm that optimizes a unimodal function on a real interval?

Suppose that I want to optimize a unimodal function defined on some real interval. I can use the well-known algorithm as described in Wikipedia under the name of ternary search. In case of the ...
0
votes
1answer
270 views

Find an element in sorted 2D-array (matrix)

Given an $N\times N$ array, where elements are decreasing in every row and every column. What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it ...
1
vote
0answers
8 views

Image quantization for grayscale images with alpha channel

I am looking for algorithm that quantize grayscale image that contains alpha to 4-bits (16 colors). I quite like the effect that is used in IrfanView to decrease color depth, however, I dont know the ...
3
votes
2answers
35 views

On the hardness of satisfying K number of linear constraints

Background: Normally in linear programing we have some objective function $$\text{maximize}\sum_{i = 1}^n a_i x_i $$ $$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...
1
vote
2answers
111 views

Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
6
votes
2answers
3k views

Why do we need to run the bellman-ford algorithm for n-1 times?

I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I ...
0
votes
1answer
27 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
3
votes
1answer
137 views

How to find the optimum solution of Weighted set cover in O(2^n)

A weighted set cover problem is: Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a ...
2
votes
1answer
25 views

Select certain number of column elements of a stochastic matrix, maximum one element per row

Consider a $m \times n$ Matrix. Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose ...
0
votes
0answers
21 views

Calculating the maxima of a function subject to a constraint

The first figure below shows the plots of a function $f(x)$ plotted for different values of a parameter $\lambda$, i.e., $f(x)=f(x,\lambda=\lambda_i);i=1,2,3,..;\lambda$ is maximum for the topmost ...
0
votes
1answer
30 views

Please provide me a solution of Max-Heapify using Recursion Tree

I tried my best to solve the recurrence relation. $T(n) \le T(2n/3) + \Theta(1)$ Using the recursion tree. I could reach out the boundary condition when at depth ...
2
votes
0answers
66 views

Set of maximum overlaps

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap. I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
0
votes
0answers
21 views

Using induction vs invariants to prove correctness of algorithms

In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $A(n)$ that computes $x$, I show that the algorithm works for some base case, say $A(...
2
votes
1answer
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'...
0
votes
1answer
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} $$
2
votes
1answer
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. ...
1
vote
1answer
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)...
3
votes
1answer
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 ...
0
votes
0answers
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, ...
1
vote
1answer
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 ...
0
votes
3answers
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 ...
2
votes
0answers
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 [...
1
vote
1answer
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 ...
3
votes
1answer
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 \...
26
votes
2answers
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 ...
11
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
5
votes
1answer
2k views

Why number of possible cuts in a graph differ from maximum number of minimum cuts?

According to this wikipedia link, under the title "Success probability of the contraction algorithm": Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\...
2
votes
0answers
95 views

Determine the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle

I need to create an algorithm that will output the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle. The sample input is as ...
2
votes
0answers
77 views

Algorithm to solve a physical ring removal puzzle

Assume we want to solve the so-called "Super-G" problem from Jean-Claude Constantin. The goal of the puzzle is to get the ring off the other components. Here is a picture of the problem: Source: ...
0
votes
1answer
32 views

Algorithm for solving system of congruences

I'm trying to understand an algorithm shown in my textbook for solving a system of congruences. The problem states: Let $r$ and $m$ be arrays of size $n$, such that every two numbers (modulos) from $...
6
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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) ...
2
votes
1answer
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)...
0
votes
2answers
42 views

How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
4
votes
1answer
9k views

Finding the path of a negative weight cycle using Bellman-Ford

I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, ...