# 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.

11,099 questions
Filter by
Sorted by
Tagged with
2k views

### Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
409 views

671 views

### How to random-generate a graph with Pareto-Lognormal degree nodes?

I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution. Where can I ...
541 views

### Balanced weighting of edges in cactus graph

Given a cactus, we want to weight its edges in such a way that For each vertex, the sum of the weights of edges incident to the vertex is no more than 1. The sum of all edge weights is maximized. ...
3k views

### Finding the Largest "Ordered" Difference in Elements of an Array

Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$. I would like to design an ...
721 views

### How to detect stack order?

We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current ...
4k views

### Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ... 4k views

### Most efficient algorithm to print 1-100 using a given random number generator

We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50. We may use only this random number generator to ...
2k views

### Finding the $k$th largest element in an evolving query data structure

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element ...
1 vote
3k views

1k views

189 views

### Improve Markov Chain results

Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different ...
3k views

### If any 3 points are collinear

Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear. The problem is I started with general definition but I cannot ...
11k views

11k views

### Fastest algorithm for finding the longest palindrome subsequence

First of all we must read a word, and a desired size. Then we need to find the longest palindrome created by characters in this word used in order. For example for size = 7 and word = "abcababac" the ... 3k views

### Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm ...
135 views

### Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...
6k views

### How to describe algorithms, prove and analyse them?

Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
686 views

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \... 22 votes 4 answers 4k views ### Sorting algorithms which accept a random comparator Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ... 0 votes 1 answer 2k views ### Solve a problem through reduction I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ... 3 votes 2 answers 2k views ### "Flow layouts" inside a GUI -- how do I come up with a good algorithm? I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode): ... 3 votes 1 answer 609 views ### Restricted version of vertex cover I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph$G =(L, R, E)$and an integer$K$. Question: Is there$S \subset L$,$|S| \... 1k views

### Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
4k views

### Finding interesting anagrams

Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ ...
464 views

### Generating number of possibilites of popping two stacks to two other stacks

Context: I'm working on this problem: There are two stacks here: A: 1,2,3,4 <- Stack Top B: 5,6,7,8 A and B will pop out to other two stacks: C and D....
179 views

### Numbers of ways of expressing the sum of a number between [a,b]

I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval [a, b] 1 vote
Possible Duplicate: How to use greedy algorithm to solve this? You are given $n$ integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ ...