# Questions tagged [ds.algorithms]

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

1,654 questions
Filter by
Sorted by
Tagged with
10 views

### Maximum subarray problem with weights

The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j ...
77 views

### On solving Planar Circuit SAT

This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
42 views

### How can I calculate nonstandard binary representations quickly?

I'm looking to convert standard unsigned binary numbers (machine integers) to each of several similar nonstandard binary representations. First representation Each digit is 1, 2, or 3. Second ...
100 views

### Polynomial evaluation at all different points

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
729 views

### Approximation algorithms used in exact algorithms

Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms. However, constant factors are ignored in time complexity. So I wonder if ...
139 views
+50

### Complexity of finding the most likely edge

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...
8 views

### No 13 in the sequence [migrated]

There are "n" number of box's each box we can place 0-9 numbers .. condition is that 13 is not occurred at any place in sequence.. I take n = 3; and so total possiblities is 101010 = 1000 ,...
148 views

### Match a string agains a set of regexes

There are several algorithms to match a (simple) string against a regular expression (see here). But if we have a lot of regexes, can we find one of them that matches the given string faster than ...
837 views

### Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

I'm seeking an efficient algorithm for the problem: Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$. Output: The number $n$. Question: Can we compute $n$ from the bits ...
47 views

### The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
867 views

270 views

### 3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
452 views

### Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
433 views

### Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
143 views

### What is the complexity of this submatrix selection problem?

We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks. We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
76 views

### Minimizing the gaps with incremental capacity

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
96 views

509 views

### Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
42 views

### understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
12k views

### How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...
1k views

### Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
2k views

### Positive topological ordering

Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
2k views

### Testing/Identifying a Topological Sorting

You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...
906 views

### Minimum cost topological ordering

We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ...
57 views

Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{... 0answers 84 views ### NP-Hard or PTIME? I am working on my research problem that essentially boils down to the following question. Consider an$N \times N$matrix. There is a man at given a starting point$(x,y)$. In each unit of time, the ... 1answer 881 views ### Knapsack with dependent profits (pairs of items) I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items$e_i$and$e_j$have profit$p_i$and$p_j$respectively. However, if both items are present in ... 1answer 72 views ### Interval partitioning with restrictions: NP-complete or efficiently solvable? The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ... 0answers 23 views ### Are the intermediary sets in maximum cardinality search optimal in some way? The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph$G = (V, E)$where$w(u, v)$denotes the weight of the edge$\{u, v\}$, we select a start node$a \in V$and do ... 9answers 8k views ### Best Upper Bounds on SAT In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ... 1answer 111 views ### What is the complexity of this weighted b-edge matching problem? I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem: Input: An undirected multigraph$G = (V, E)$without loops, an edge partition$(E_1,...
I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...