# 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,632 questions
Filter by
Sorted by
Tagged with
69 views

### Problem in downvote system

Problem For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
68 views

### Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
1k views

### Non-recursive (iterative) DFS with $O(n)$ size stack

I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case. ...
54 views

### What is the Time complexity of this sorting algo?

So i was trying to write an efficient sorting algorithm and i came up with this method, Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order ...
60 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 ...
1k views

### Find a node with maximum distance from query 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 $k$ queries of the form: find node $u$ ...
23 views

### Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
11 views

### String filtering - process hundreds to millions of filters

What would be the most efficient way (whether with algorithims, cpu(s), DBs & SQL, distributed computing, etc) to process many strings, say ~1000/minute, and filter each string over 100s to ...
111 views

### Minimum Path cover in a Directed Acyclic Graph

Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
25 views

30 views

### Point of Interest Problem

You are in a xy plane with a set of points F. You also have a collection P of N sets { P1,...., Pn} where each of the set consist of points of the form (Px,Py). Each set has a different number of ...
173 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 ...
101 views

### Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
25 views

### Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
39 views

### Number of bits needed to represent an integer with a specifed base

How many bits are required to represent an integer $x$ with base $b$?
43 views

### How to solve following tree problem?

Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
47 views

### Compute highest-scoring segmentation

I have the following problem: There is a "clean" sequence of sequences, say: clean = [ [1, 2], [3], [4, 5] ] And a "noisy" sequence which is not ...
82 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. ...
134 views

### Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
13 views

### Maximizing total value given bound on total cost

I have a list of pairs with values and costs: | value | cost | 11, 1000 7, 700 7, 700 6, 700 2, 400 2, 500 1, 600 The ...
34 views

### Absolute minimum difference

We are given a array of positive numbers. We can perform two types of operations on these sequence of numbers. If number E is even, then we can replace it by E/2 If number E is odd, then we can ...
52 views

### Longest path in a directed acyclic graph with constraints

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'. What is the complexity of this ...
456 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
19 views

43 views

### Which algorithm to detect errors in 32bit data with 8bit parity

I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking. Overall, a group is likely transmitted without error, but when there is an error ...
9k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
4k views

### Sorting a list of strings in lexicographic order of sorted strings

Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols. Your task is to sort each of the strings internally, and then sort the resulting strings ...
53 views

### How to count all integers less than a given integer and having two contigous digits as $y$?

Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...