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
23
votes
2
answers
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
5
votes
1
answer
409
views
Is it possible to always construct a hamiltonian path on a tournament graph by sorting?
Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:
$\qquad \displaystyle a \leq b \iff (a,b)...
- 153
14
votes
1
answer
16k
views
Expected number of swaps in bubble sort
Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
TheRock
3
votes
1
answer
248
views
What is the significance of the semi clustering formula in the Google Pregel paper?
Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula
$\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c -...
- 131
3
votes
1
answer
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
7
votes
2
answers
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
6
votes
4
answers
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
8
votes
1
answer
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
2
votes
2
answers
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 ...
Julian J. Tejera
11
votes
4
answers
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
5
votes
3
answers
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
1
answer
3k
views
3-dimensional matching approximation algorithm (implementation details)
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?
$X, Y,...
- 13
41
votes
4
answers
10k
views
Worst case $O(n \ln n)$ in place stable sort?
I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources?
Just a reminder, in place means it uses the ...
- 829
3
votes
1
answer
1k
views
Can truth tables be used in non-boolean algebra to derive functions?
There are obvious analogs (pardon the pun) between Boolean algebra and algebra. They have similar laws, operators and properties. I can't figure out why Karnaugh Maps and sum of products, which are ...
- 147
8
votes
2
answers
1k
views
How can I find minimum number required to add to sequence such that their xor becomes zero
Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.
Consider the ...
- 181
7
votes
1
answer
706
views
Find string that minimizes the sum of the edit distances to all other strings in set
I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.
Is there an algorithm for finding the string $x$ which minimizes the sum of the ...
- 173
8
votes
2
answers
646
views
Minimizing the total variation of a sequence of discrete choices
My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a ...
- 2,372
3
votes
3
answers
4k
views
How does worst-fit memory allocation react when encountering contiguous empty memory blocks?
So I have a problem understanding how the worst-fit protocol for memory allocation reacts to contiguous blocks of empty memory. None of the examples I have found address this possibility.
For ...
- 1,115
8
votes
1
answer
335
views
Algorithm to test a graph for $t$-transitivity
I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.
I am also interested in knowing if this problem is in P, NP, NPC or some other ...
- 651
17
votes
1
answer
6k
views
Getting parallel items in dependency resolution
I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
- 273
5
votes
2
answers
5k
views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
- 829
2
votes
2
answers
1k
views
How to use dynamic programming to solve this?
Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
- 1,121
23
votes
4
answers
12k
views
Book for algorithms beyond Cormen
I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations?
NOTE: I asked ...
- 341
9
votes
2
answers
855
views
CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof
In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| ...
- 363
6
votes
3
answers
1k
views
What is the bitwise xor of an interval?
Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval.
What is a fast algorithm to find
$\{ k\oplus x\mid x\in [a..b]...
- 3,023
3
votes
1
answer
710
views
Efficient bandwidth algorithm
Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:
Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
9
votes
5
answers
22k
views
Using Dijkstra's algorithm with negative edges?
Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance ...
user1422
5
votes
1
answer
649
views
Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?
I've been given the following problem:
Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:
$\text{Insert}(x)$ – add $x$ to $S$
$\...
- 619
3
votes
1
answer
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
7
votes
1
answer
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
12
votes
1
answer
11k
views
How do I construct a doubly connected edge list given a set of line segments?
For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \...
- 3,139
0
votes
2
answers
310
views
Proving that the cover time for graph is exponential in the worst case
How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?
The cover time is the expected length of a random walk that visits all vertices.
- 489
1
vote
0
answers
38
views
constrained cover on biparite graphs [duplicate]
Possible Duplicate:
Restricted version of vertex cover
Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those ...
- 11
4
votes
2
answers
19k
views
Finding the number of distinct permutations of length N with n different symbols
I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.
For example if the string is of length ten as $w = aabbbaabba$, the total number ...
- 141
9
votes
5
answers
7k
views
Shortest distance between a point in A and a point in B
Given two sets $A$ and $B$ each containing $n$ disjoint points
in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \...
- 3,139
8
votes
4
answers
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 ...
Lin Yon Xong
17
votes
1
answer
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 ...
- 623
2
votes
1
answer
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
21
votes
2
answers
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
20
votes
3
answers
686
views
Problems in P with provably faster randomized algorithms
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 \...
- 1,787
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 ...
- 1,538
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 ...
- 17
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):
...
- 1,167
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| \...
hbm
9
votes
1
answer
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
32
votes
5
answers
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
3
votes
2
answers
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
3
votes
1
answer
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]
vikt0r
1
vote
0
answers
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
2
votes
1
answer
3k
views
Enumerating all the walks in a graph between a start vertex and a terminal vertex?
I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can ...
- 121