Unanswered Questions
753 questions with no upvoted or accepted answers
12
votes
1
answer
5k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 280k
10
votes
2
answers
2k
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 ...
CommunityBot
- 1
9
votes
0
answers
784
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,058
8
votes
0
answers
2k
views
Choosing potential function in amortized analysis
How should I think to choose the potential function in the amortized analysis?
More specifically are there techniques or tips for choosing optimal or good potential functions?
- 82.4k
8
votes
0
answers
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
CommunityBot
- 1
8
votes
0
answers
383
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 73.1k
7
votes
0
answers
3k
views
Stopping condition for goal-directed bidirectional search for shortest path
So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.
So let $l(u,v)$ ...
- 658
7
votes
0
answers
557
views
What is the average-case running time of Fun-sort?
I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
- 1,090
7
votes
0
answers
203
views
What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
- 22.6k
7
votes
1
answer
1k
views
Find maximum in array without comparisons between elements
Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.
The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:
$...
- 199
6
votes
0
answers
97
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
CommunityBot
- 1
6
votes
0
answers
292
views
Is greedy minimax permutation rejecting sorting optimal?
I sketch an impractical, theoretical comparison sort.
Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how many permutations would get rejected ...
- 73.1k
6
votes
0
answers
89
views
What are the properties of the unsided fold?
Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold:
fold f [a,b,c,d] = (f (f a b) (f c d))
That ...
- 441
6
votes
1
answer
124
views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
- 6,188
5
votes
0
answers
85
views
Completeness of red-black tree operations
Red-black trees are defined to have the following invariants:
The nodes are in sorted order (it is a binary search tree).
The root is black, and leaves are black.
Every red node has black children.
...
- 541