Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

Filter by
Sorted by
Tagged with
16
votes
1answer
253 views

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...
16
votes
1answer
576 views

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?

While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post: If, for every $n$, there exists a relation of the form $$ (2^n)! = \sum_{k=0}^{m-1} ...
16
votes
1answer
677 views

Making a minimum-width tree decomposition lean in polynomial time

As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions: Every ...
16
votes
1answer
778 views

Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
16
votes
1answer
728 views

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
16
votes
2answers
1k views

Permutation phrases with LR parsing

A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$...
15
votes
6answers
3k views

Complexity of the Fisher-Yates Shuffle Algorithm

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n). In ...
15
votes
5answers
868 views

References for Modular Decomposition

What are good papers/books to better understand the power of Modular Decomposition and its properties? I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
15
votes
5answers
1k views

Examples of pedantry in TCS

Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it): The ...
15
votes
4answers
2k views

Definition of matrix-multiplication exponent $\omega$

Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a ...
15
votes
2answers
3k views

Minimum number of transpositions to sort a list

In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it. For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way ...
15
votes
3answers
1k views

Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier. For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine ...
15
votes
2answers
1k views

What is known about this TSP variant?

This question was previously posted to Computer Science Stack Exchange here. Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
15
votes
3answers
1k views

Subgraph isomorphism with a tree

If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism ...
15
votes
1answer
1k views

Examples of algorithms and proofs that seem correct, but aren't

In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an ...
15
votes
3answers
3k views

Linear time in-place riffle shuffle algorithm

Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then ...
15
votes
2answers
1k views

Notable examples of the square root idea in complexity analysis

There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include baby-step giant-step ...
15
votes
4answers
399 views

Worst number of questions needed to learn a monotonic predicate over a poset

Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
15
votes
1answer
2k views

Algorithms Design and Complexity - How to think in that 'way'?

My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it ...
15
votes
3answers
882 views

Super Mario Flows in NP?

One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
15
votes
3answers
527 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
15
votes
2answers
4k views

What is the fastest algorithm to compute rank of a rectangular matrix?

Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns? I am aware it can be solved through linear matroid intersection, which ...
15
votes
1answer
1k views

Equivalence of feasibility checking and optimization for linear systems

One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the ...
15
votes
1answer
1k views

Speedup from algorithmic advances vs. hardware

I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does ...
15
votes
1answer
233 views

2FA state complexity of k-Clique?

In simple form: Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states? Details Of interest here are $v$-vertex graphs encoded using a sequence of ...
15
votes
1answer
474 views

Imperfect subgraph isomorphism

Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
15
votes
1answer
442 views

Graph decompositions for combining “local” functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
15
votes
1answer
733 views

Sparse Walsh-Hadamard Transform

The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is ...
15
votes
0answers
158 views

Is it possible to boost the error probability of a Consensus protocol over dynamic network?

Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
15
votes
0answers
434 views

Semiprime factorization, Groebner bases and a Nullstellensatz certificate

Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}...
15
votes
2answers
593 views

Exponential Speedup in External Memory

Background The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
14
votes
5answers
2k views

Best book on Simplex Method implementation?

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
14
votes
4answers
2k views

Theoretical study of coordinate descent methods

I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ ...
14
votes
2answers
2k views

Justification for the Hungarian method (Kuhn-Munkres)

I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even ...
14
votes
2answers
4k views

Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
14
votes
1answer
1k views

Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
14
votes
2answers
352 views

Smallest set not included in a collection of sets

Given as input an integer $n$ and a set $S$ of sets of elements of $\{1, ..., n\}$, what is the complexity of finding a set $T$ of elements of $\{1, ..., n\}$ such that $T$ has minimal cardinality and ...
14
votes
1answer
645 views

Complexity class associated with exhaustive search

What is the complexity class associated with exhaustive search algorithms? (if there is one) Is it NP or PSPACE? Are there restricted models of computation capturing the class of exhaustive search ...
14
votes
2answers
1k views

NP-hard problems with very fast exponential-time algorithms

NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare. Is any fact like "For any constant $\epsilon>0$ there is an NP-hard 'natural' ...
14
votes
3answers
389 views

Separation of a preprocessed polyhedron and a plane

I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: http://www.cs.princeton.edu/~dpd/Papers/...
14
votes
3answers
687 views

Nontrivial problems solvable in constant time?

Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can ...
14
votes
2answers
2k views

Number of mincuts of a graph without using Karger's algorithm

We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$. I was wondering if we could ...
14
votes
2answers
418 views

A graph parameter possibly related to treewidth

I am interested in graphs on $n$ vertices which can be produced via the following process. Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused. Produce a ...
14
votes
2answers
2k views

Algorithm to sort pairs of numbers

I already asked this question on stackoverflow, but maybe it is better suited for this site. The problem is: I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs ...
14
votes
2answers
2k views

Space-time tradeoff and the best algorithm

Consider some language $L$ such that: $L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$ and so that $L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$ In other words, the fastest machine $M$ computes $L$ ...
14
votes
2answers
475 views

OR-circuit complexity of a dense linear operator

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
14
votes
1answer
428 views

Hitting odd cycles

Is there anything known about the following problem? Does it make sense at all? What is it called? Is it trivially equivalent to some other problem? What is the time-complexity? Given an undirected (...
14
votes
2answers
482 views

The existence of planar distance preserver?

Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property $$d_H(u,v) = d_G(u,v)$$ for all nodes ...
14
votes
1answer
928 views

Does zero integrality gap imply zero duality gap for certain problems?

We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation,...
14
votes
3answers
517 views

Is this optimum travelling problem under deadlines NP-hard on trees?

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it? Problem: There is a tree $T(V,E)$, each edge has symmetric ...

1
3 4
5
6 7
33