The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
3
votes
2answers
230 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
118 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
239 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
833 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
321 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
87 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 ...
3
votes
1answer
383 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
549 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
277 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
73 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
110 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
254 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
148 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
859 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
495 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
122 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
571 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
175 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
124 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 ...