# Questions tagged [counting]

The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.

156 questions
Filter by
Sorted by
Tagged with
3answers
2k views

### Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
0answers
81 views

### Count all possible 2-3-monotone sequences

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as: $s_i < s_{i+2}$, for $1 \leq i \leq N-2$ $s_i < s_{i+3}$, for $1 \leq i \leq N-3$ $s_i \in \{1,\dots, N\}$ Given $N$...
3answers
71 views

### Count elements in the real world in constant time by weighing them

I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out ...
1answer
1k views

### DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk. My question is that, say we have a DAG (...
2answers
696 views

### Count all numbers up to X that are divisible by at least two of their digits

I want to count how may numbers are there in range [1,X] which are divisible by at least two of their digits, different and >1. I found a sequence on OEIS, but this will take lot of time to generate ...
1answer
74 views

### Counting specific subgraphs

For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions: H.V = G.V (The subgraph will containt all the original graph nodes) H is connected (Note: ...
0answers
34 views

### Complexity of Self avoiding walks in unary

In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and ...
1answer
5k views

### How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
5answers
6k views

### Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...
1answer
142 views

### Number of states in an AND-OR DAG

Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
1answer
549 views

### Why is the counting variant of a hard decision problem not automatically hard?

It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a ...
1answer
872 views

### Count number of automata with 3 states and alphabet of size 2

How many different finite automata are there that have 3 states $q_0$, $q_1$ and $q_3$, have an alphabet of size 2, and where $q_0$ is starting state?
1answer
95 views

### Count all pairs of x,y such as x + y = c && x XOR y = d

Given two decimals $c$ and $d$; $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements: $$x+y = c\\ x \text{ XOR } y = d$$ Killed already a day still can't ...
2answers
320 views

### Finding the number of square prefixes of a string in linear time

Let square denote a concatenation of two identical, nonempty strings. Given a string $w$, devise an $O(|w|)$ algorithm that counts the number of prefixes of $w$ that are squares. My initial idea ...
0answers
69 views

3answers
1k views

### Computing a histogram with the number of extant values not known in advance

(This may be more fitting for CSTheory, I'm not sure.) I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...