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
1
vote
0answers
25 views

Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
1
vote
1answer
22 views

Is the sieve an improvement for prime finding over an optimized algorithm?

I don't think it is, as you have to loop through each set multiple times at least. implementation of sieve in JS - in the answer at the bottom. The link shows a 10X improvement using sieve. In this ...
3
votes
1answer
39 views

Matching two sets when you cannot do within-set comparisons

Suppose you have two lists, A and B, each with length n. The elements of A cannot be compared with other elements of ...
1
vote
0answers
11 views

Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
0
votes
1answer
39 views

Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
0
votes
1answer
31 views

If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?

Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST? MST means ...
0
votes
1answer
22 views

Does input space size contribute at all to the runtime of an algorithm?

I just started learning about NP-Complete problems and one of the first examples they give is Set Cover: Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a ...
-1
votes
0answers
24 views

Is it possible to keep weights of left and right subtree at each node of BST that has duplicate values?

Is it possible to keep weights of left and right subtree at each node of BST that has duplicate values? I must be able to delete a node completely(irrespective of how many times it is present) ...
2
votes
1answer
117 views

Similar news detection

How do top news portals detect similar news? For example https://www.bbc.com/news/world-asia-china-51431087, if you go to this webpage, you can see the "More on this story" section at the bottom of ...
4
votes
0answers
55 views
+50

Are weakly polynomial time algorithms truly polynomial?

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if ...
0
votes
0answers
14 views

Is it possible to implement iterative pre/in/post-order traversal with only one stack?

All iterative algorithms I've seen for pre-order, in-order, and post-order traversals of trees have used two stacks. Is it possible to do it with one? I've been thinking about it for ever, I haven't ...
1
vote
1answer
77 views

Selection over combinatorics that satisfies a distribution

I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not. Here is the problem : Consider a list of M ...
1
vote
3answers
61 views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
3
votes
0answers
78 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
2
votes
2answers
58 views

Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
2
votes
1answer
57 views

DQQD algorithm for Frobenius numbers

As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga ...
1
vote
1answer
14 views

Algorithm to compute decomposition of a union of sets to a disjoint union of intersections

A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets. This clearly generalizes. If ...
0
votes
1answer
25 views

Clustering algorithm with specific cluster grouping areas

I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its ...
0
votes
1answer
65 views

Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in ...
0
votes
2answers
33 views

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can ...
1
vote
1answer
109 views

Independence of order of insertion hashtable with open addressing

I'm taking a data-structure class, and the lecturer made the following assertion: the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order. ...
-1
votes
1answer
31 views

From a randomized algorithm with expected time $O(n)$ to a reliable with determined running time

Let $A$ be a randomised algorithm and $F$ be a function such that $A$ returns $F(x)$ on any input $x$. Furthermore suppose that, for input $x$ of size $n$, the $\textbf{expected}$ running time of $A$ ...
1
vote
1answer
34 views

Determining if match is possible

I have a list of patterns with each pattern containing one or more wildcards. For example: abc* a* ...
-1
votes
0answers
19 views

Minimum perimeter of rectangle

Help me, please, to find the algorithm for this task: Given a set of points in plane, determine a rectangle with the smallest possible perimeter which contains all the points. The rectangle is not ...
4
votes
1answer
100 views

Minimizing total distance traveled by points in points cloud transformation

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting ...
0
votes
0answers
17 views

How do I know which node to do rotation on?

I'm wondering which node do I perform a rotation for on an AVL tree? I think in a single rotation it is always the grandparent of the node causing the imbalance (which could either be the root node ...
0
votes
2answers
44 views

Algorithm to find the correct word

Imagine you are given a word samw and it is an invalid word (for the word same), and you need to find the correct word from the ...
3
votes
1answer
53 views

Efficiently prime factorising an integer with an oracle

Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns ...
1
vote
2answers
60 views

Computational complexity vs other complexities

Complexities, such as time complexity, space complexity, communication complexity and sample complexity, are often used to analyze the performance of algorithms. As far as I know, time complexity and ...
2
votes
0answers
33 views

Bipartite Planar Graph Isomorphism

I want a hueristic algorithm for the following problem. Here, $V(G)$, $E(G)$ respectively refer to the vertex set and edge set of a graph $G$. Input: two planar bipartite graphs, $G,H$ and a map $\...
-1
votes
0answers
26 views

Back edge in a DFS Algorithm

I run DFS algorithm on the graph and If the I have 2 options so the order is lexicographic. As I saw in Wikipedia: back edges, which point from a node to one of its ancestors Who are my two ...
0
votes
2answers
69 views

Is this program O(n^2logn) or O(nlog^2(n))?

I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely. ...
0
votes
0answers
36 views

Binary Search Complexity

I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...
1
vote
1answer
43 views

An algorithm to find the closest match between 2 arrays of RGB pixel tuples

So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best. Suppose we have 2 arrays of ...
1
vote
1answer
50 views

Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

For this I came up with a DFS recursion. Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing. The element with ...
2
votes
2answers
80 views

Algorithm to compute $n^{\log k}$ in $O(\log\log k)$

I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\...
0
votes
0answers
64 views

Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
0
votes
0answers
20 views

Cover marked squares with rectangles with optimal tradeoff

I'm trying to solve this problem where I have to cover all the squares in a N x N grid with rectangles with a tradeoff between cost and computation. These are the constraints: Fields are rectangular, ...
2
votes
3answers
66 views

Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

This is the problem statement I came across today. Given a binary tree, find the lowest common ancestor of all deepest leaves. I came up with a correct algorithm, but I would like to confirm the ...
0
votes
0answers
25 views

How can I efficiently find out if X is in any of N ranges of L-R numbers?

This is part of a bigger problem, which is to find out if point XYZ exists in any of n ...
1
vote
1answer
40 views

Two peaks finding algorithm

We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than O(N), maybe ...
0
votes
1answer
24 views

$O(n \log n)$ algorithm to find next interval that is also disjoint

Say there are some intervals $\{1, \ldots ,n\}$ with starting times and ending times, and they're sorted in order of starting time from first to last in an array intervals$[]$. Now I want create an ...
1
vote
1answer
22 views

Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

Gradient descent sometimes works better than simulated annealing and vice versa. Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one ...
3
votes
0answers
36 views

Why is the Black-White Bakery Algorithm considered bounded?

As stated in Lamport's papers for the bakery algorithm he states that the ticket numbers are unbounded specifically The range of values of number is unbounded. and Fortunately, practical ...
1
vote
1answer
31 views

Maximum Subsequence Sum : Mark Weiss:

In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"? By ...
1
vote
1answer
27 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
2
votes
1answer
84 views

Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles,...
3
votes
2answers
45 views

Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up ...
1
vote
0answers
13 views

Why are bottom-up selector matching algorithms more efficient?

Most implementations of CSS-like selectors (that is, patterns that may match paths in a tree) seem to use a bottom-up approach. That is, for each node in the tree, they check for a match against the ...
1
vote
1answer
21 views

Algorithm for token replacement game

I'm having problems finding an algorithm to the following problem: A and B take turns replacing a number $n$ of tokens with either $floor((n+1)/2)$ or $n-1$. The player who makes one token remain ...