# 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, ...
• 3,023
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 ...
• 133
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. ...
• 227
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 ...
• 429
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 ...
• 775
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 ...
• 233
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 ...
• 227
1 vote
3k views

1k views

• 619
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 ...
• 131
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 ...
• 3,139
11k views

• 3,139
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 ...
• 123
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 ...
• 621
686 views

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 ...
• 261
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)}$ ...
• 1,525
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....
• 43
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
54 views

### How to use greedy algorithm to solve this? [duplicate]

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$ ...
• 1,121