Questions tagged [counting]

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

Filter by
Sorted by
Tagged with
-2
votes
1answer
638 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?
1
vote
1answer
93 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 ...
5
votes
2answers
290 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 ...
2
votes
0answers
66 views

Complexity class of a counting problem

Consider the following inequalities: $\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$ $\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$ $x_{ij} \ge 0 \;\;\; i,j=1,...,n$ $y_i \in \{0,1,2\} \,\,\,\, i=1,...,...
3
votes
1answer
248 views

The most efficient algorithm for computing cardinality of sumset

Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A ...
1
vote
1answer
913 views

How do I find the number of inversions using a red black tree?

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node ...
1
vote
1answer
5k views

Seating arrangement problem

$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$ Each professor has people they like to sit next to and people they do not want to sit next ...
2
votes
1answer
706 views

Count the number of Euler PATHs in directed graph?

I would like to find all Euler PATHs in a directed graph. Counting (instead of finding) all the Euler PATHs is sufficient. Circuits are not good for me, only Paths. I am doing a problem, that I have ...
1
vote
2answers
153 views

Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum: Given a set of integers, $S$, and a target number, $n$, what is the ...
3
votes
1answer
124 views

Counting words that satisfy SAT-like constraints with BDDs

I have the following #P-complete problem: Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with ...
0
votes
0answers
353 views

Number of paths between two nodes in mesh topology

Is there any way to find generalized formula to calculate the number of paths of different length between two nodes of the network connected in mesh topology, given that the network contains n nodes?
1
vote
1answer
137 views

fastest counting of nested loops

I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example ...
-1
votes
2answers
2k views

number of subsets where GCD equals to X

The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD ...
3
votes
2answers
235 views

Counting the number of tree when the set of the subtrees is given

There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the ...
2
votes
1answer
125 views

Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$? ...
4
votes
1answer
247 views

Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
-1
votes
1answer
897 views

count number of different DFS tree of specific graph - ladder

It is given graph. It isn't ordinary graph, it is ladder. We say that our ladder has order $n$, because of number of nodes. Look at picture: My problem is: Let's start DFS on node number $1$. How ...
2
votes
1answer
1k views

counting binary, with moving position (turing machine)

I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It ...
0
votes
0answers
329 views

Possible paths in pipe network, without loops and with some one-way valves

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit I have to ...
2
votes
1answer
88 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
-1
votes
1answer
1k views

Can a computer count to infinity? [closed]

So, could a computer count to infinity assuming it was a super computer and had near unlimited amounts of ram and hard drive/solid state drive storage? I am being serious when I ask this. [This is ...
4
votes
1answer
413 views

Proof of $P^{\text{#}P} = P^{PP}$

I was reading this article on the complexity class $PP$. In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please ...
2
votes
2answers
463 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...
0
votes
0answers
570 views

Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
2
votes
1answer
1k views

Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes ...
5
votes
1answer
290 views

Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
-1
votes
3answers
74 views

Can approximation help find the exact answer?

Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in ...
7
votes
1answer
111 views

Applications of model counting

I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, ...
2
votes
0answers
40 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
2
votes
3answers
6k views

Counting inversions in a list of integers using divide and conquer techniques

This is a homework. It looks easy, but not really. A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and ...
7
votes
1answer
263 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is $\#W$[...
11
votes
2answers
150 views

Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
8
votes
2answers
911 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
3
votes
2answers
141 views

What's the value of this game (rebalancing counters)?

Suppose you have the following game: There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0. In each step, you may choose a counter $c_i$ and increase it's value by 1. ...
8
votes
1answer
523 views

Algorithm to find all acyclic orientations of a graph

I am working on acyclic orientations of undirected graphs and have the following questions: Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ? What ...
0
votes
4answers
2k views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, d)...
3
votes
1answer
125 views

When does the IEEE-754 64-bit float break as a counter

As a matter of curiosity I've been trying to determine at what point a 64-bit float no longer reflects the addition of 1 as expected; that is, at what point the digits as printed do not correspond to ...
1
vote
2answers
1k views

Calculate number of ways to color matrix using inclusion-exclusion principle

This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same ...
2
votes
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 ...
2
votes
1answer
577 views

Counting the number of N-dimensional coprime integer vectors

I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors. The vectors in my set are $N$-dimensional integer vectors whose components are ...
2
votes
1answer
45 views

Counting involving equivalence classes and languages

Let $\Sigma$ be the alphabet $\{a, b, c, d\}$ and let $R$ be the following relation on $\Sigma^*$: $R(x, y)$ is true if every letter in string $x$ also occurs in $y$, and every letter in string $y$ ...
1
vote
1answer
176 views

Count elements of a sorted matrix that fall into a given interval

I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$. Each row and each column of M is sorted in the increasing order. I would like to know if there is way I can count the ...
3
votes
2answers
3k views

Number of binary trees with given height

I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$). Edit: I forgot to add the ...
1
vote
1answer
239 views

Preventing oversell, allocation of limited resources with overlapping properties

I am trying to solve problem of preventing oversell of limited resources. Consider resources (people) who are described by set of properties where each property belongs to different category (example ...
7
votes
2answers
126 views

numerical integral vs counting roots

I have a problem that can be viewed in two different ways: Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$. Count (just ...

1 2 3