# Questions tagged [ds.algorithms]

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

1,646 questions
Filter by
Sorted by
Tagged with
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 ...
576 views

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} ... 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 ... 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, \pi, \cdots, \pi[n]. The output should be the parity of ... 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 ... 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... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 - ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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}... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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' ... 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/... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 (... 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 ...
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 ...