Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
2answers
52 views

Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
0
votes
2answers
41 views

How to analyze the worst case of weighted quick-union method on union-find

Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne. Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial ...
3
votes
2answers
75 views

Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

I came across this problem in Tim Roughgarden's course on Coursera: In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A ...
-1
votes
0answers
54 views

Destroy the graph in minimum number of steps [on hold]

$G$ is a directed acyclic graph with $N$ vertices and $M$ edges. The aim is to destroy the graph - by deleting all of its vertices in minimum number of steps. For each step following rules must be ...
0
votes
0answers
27 views

Dijkstra’s shortest path algorithm

I'm learning about single source shortest path algorithms and need to clarify few doubts- Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers. Does ...
2
votes
1answer
351 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
5
votes
2answers
1k views

Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort

I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get ...
0
votes
1answer
40 views

Minimum number of scenarios to run to fully test a page

I run a testing application that, using Selenium, runs testing "scenarios" each of which visits a bunch of pages on a website. Each page is modeled by a Java file that contains locators, each of which ...
0
votes
1answer
407 views

Find a node with maximum distance from given node in a tree

I solved this problem from codechef: problem link and now I want to change it a bit. Instead of find out the distance between node u and v I want to answer the following query: find node u to which ...
2
votes
2answers
23 views

When are you supposed to eta-reduce?

Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$: If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ ...
-1
votes
0answers
22 views

Graph transformation

Problem: Given two undirected graphs (A and B) determine if graph B can be obtained from graph A by adding new nodes (possibly 0) and new edges between this new nodes or new edges between new nodes ...
-1
votes
0answers
11 views

Regarding Metaheuristic algorithm

I have a confusion regarding meta heuristic algorithms. I am currently looking at Sine Cosine Algorithm(SCA). I am trying to combine it with K means algorithm. Does metaheuristic algorithms calculate ...
1
vote
0answers
21 views

directed edges in an undirected graph [duplicate]

Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even. For example, consider a graph ...
0
votes
1answer
49 views

Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?

I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says : In computational complexity theory, nondeterministic algorithms are ones that, ...
2
votes
1answer
73 views

Time interval correction for step detection algorithm

I am currently going over this paper, and in fact have already tried to implement it: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4634483/ [1] Paper looks at the amplitude of the step and the time ...
2
votes
2answers
158 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
1
vote
1answer
104 views

Merge Leaf labeled trees

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...
2
votes
1answer
51 views

Largest rectangle problem

Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (...
1
vote
1answer
104 views

How to restore a broken minimal spanning tree?

We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be ...
2
votes
1answer
172 views

Finding the minimum subset within a cycle

Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $[c,d]$. Assume no two values are identical. For $(a,b)$, if $a > b$, the range is $[a,d] \...
8
votes
1answer
369 views

Transitive reduction of rectangle containment hierarchy DAG

I am looking for a $O(|V| + |E|)$ algorithm for finding transitive reduction of a rectangle containment hierarchy DAG, i.e. a directed edge exists from one rectangle to another if the first rectangle ...
1
vote
1answer
39 views

Distinct Minimum Weight Spanning Trees

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider ...
0
votes
0answers
13 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
-1
votes
0answers
19 views

Banerjee's Test

I have a few questions about Banerjee's test. what is Banerjee's Test, and is it related to the GCD algorithm if the answer is yes how? And what is the benefit of using it in dependency analysis, and ...
39
votes
7answers
54k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
5
votes
1answer
1k views

Dynamic programming: speed of top down vs bottom up approaches

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...
-1
votes
0answers
18 views

Any code/algorithm/paper for video smoothing?

I've implemented on a third party software the NVidia Optix Denoiser but it has problems with animations yet since it introduces a small flickering so introducing a temporal smooth could be a nice ...
1
vote
1answer
24 views

Running time in FPT

For a certain parameter $k$, is the algorithm with the running time of $O(k.n^{\log{n}})$ in class $FPT$? I would appreciate if you can kindly guide me through.
0
votes
0answers
15 views

What's a good clustering algorithm to form a consensus definition of a word?

For example, if I had a list of different definitions for the same word, how can I use semantic clustering to form a consensus definition? What's the best algorithm?
0
votes
1answer
39 views

“Ways to make change for a dollar”: How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
0
votes
1answer
45 views

Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
2
votes
2answers
3k views

Sorting an array of boolean values

im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues. so if given this: a = {true, true, false, true, false} it ...
0
votes
1answer
137 views

Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms

I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if ...
0
votes
1answer
55 views

Store array of sequential intervals

I need to store a list of sequential intervals. So for example I would to say: {0-5} = a {6} = b ...
1
vote
1answer
83 views

Pairs distance to ordering?

Thanks to anon for contributing this wording: Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\...
2
votes
1answer
64 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
0
votes
0answers
21 views

“Spring” vs FFT spacial to frequency domain?

Before I found out about FFT https://m.youtube.com/watch?v=spUNpyF58BY but having seen and been impressed by spectrograms/sonograms, I developed my own algorithm for converting to the frequency domain ...
0
votes
0answers
12 views

Digitalize the endpoints (10, 18), (15,8) using Bresenham’s algorithm [on hold]

If there are any other example for Bresenham's regarding negative slopes ?
-1
votes
0answers
23 views

Writing a recurrence

I do not understand this problem. Please help me solve it, but also explain what is happening. I missed it completely on a HW assignment You are researching the size of the crowd at the US ...
0
votes
1answer
15 views

Parallel Algorithm for Data Averaging

I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
2
votes
1answer
23 views

Variant of interval scheduling (multiple machines with given availability)

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
2
votes
2answers
584 views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
1
vote
1answer
115 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
2
votes
2answers
51 views

Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?

Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. ...
2
votes
3answers
479 views

Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem: We are given a ...
0
votes
1answer
144 views

A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...
5
votes
1answer
302 views

Query all bounding boxes which contain a point

I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the ...
1
vote
1answer
67 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
0
votes
1answer
96 views

Algorithm to find best combination of datasources (Quality and price)

I have some sources of data, and each one of this sources have a cost per request. I know wich data attributes each one of these sources have, and what are the best sources for each attribute. Given ...