Questions tagged [counting]
The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.
197
questions
2
votes
0
answers
18
views
Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
- 532
-2
votes
2
answers
38
views
Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
- 1
0
votes
0
answers
50
views
formalization of partial function for counting
I need assistance in defining axioms for partial functions in total function theory that is available in Coq.
Specifically, I'm looking for a constructive definition of a partial function that ...
1
vote
4
answers
125
views
XOR pair frequency queries
We are given an array of length $N$ and $Q$ queries (offline) where each query is a value $K$, for each query we need to count number of pairs in array with XOR $K$.
If $N$ and $Q$ can both be upto $...
- 105
1
vote
0
answers
41
views
Is there a known FPRAS for this simple partition function?
I Let $G$ be the set of simple graphs on $n$ nodes. Given a $g \in G$, we denote the number of triangles in $g$ with $n(g)$. Given some positive real-valued parameter $w$, we define the the function $...
- 173
0
votes
1
answer
77
views
Complexity of this variant of #Positive 2-SAT #P-complete?
In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this :
A = [ab ,ac ,ad ,.... ]
B =[bc ,bd ,be ,....]
C=[cd ,de ,....]
D=[de ,....]
....
In this variant ,we are allowed ...
- 33
0
votes
1
answer
489
views
Complexity of a variant of #Positive-2-SAT
#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable.
The ...
- 33
2
votes
2
answers
77
views
Counting States in the trim automaton for $L\circ L'$
Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
- 923
-2
votes
1
answer
104
views
Find Number of subsequences such that bitwise OR is same as sum
Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
- 1
1
vote
1
answer
83
views
fastest algorithm to count leaf nodes (i.e. terminal nodes)
With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time?
Python code - (mag(P) = number of leaf nodes of tree ...
- 119
0
votes
2
answers
53
views
Finding a 2SAT instance that has a specific solution set
Is there a 2SAT instance of variables $(a,b,c,d,e,f,g)$ that has exactly the solution set $S=\{ (1,0,0,0,0,0,0),(0,1,0,0,0,0,0),(0,0,1,0,0,0,0),(1,1,0,1,0,0,0),(1,0,1,0,1,0,0),(0,1,1,0,0,1,0),(1,1,1,1,...
1
vote
1
answer
166
views
Counting independent sets
I know the Independent set problem is NP-complete. But could there be a more efficient way to count the exact number of different independent sets in an arbitrary, given graph?
- 23
0
votes
1
answer
51
views
BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.
We could try an ...
2
votes
2
answers
654
views
Count number of non-contiguous occurrences in string
Given strings $S,T$ such that $n=|T|>|S|$ , I'd like an algorithm to count number of occurrences of $S$ in $T$ (as a subsequence), not necessarily contiguous.
Example:
if $T=aababc, S=abc$, the ...
- 315
-3
votes
1
answer
97
views
how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000
how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000
for example for n=3, there is 15 solutions
1^1=1^1
1^1=1^2
1^1=1^3
1^2=1^1
1^2=1^2
1^2=1^3
1^3=1^1
1^3=1^2
1^...
-4
votes
2
answers
58
views
Let F be a function defined for all nonnegative integers by the following recursive definition
Let F be a function defined for all nonnegative integers by the following recursive
definition.
F(0) = 0, F(1)= 1
F(n + 2) = 2F(n) + F(n +1), n>0
Compute the first six values of F; that is, write ...
- 1
0
votes
1
answer
144
views
Why solving #2SAT in polynomial time implies P = NP?
The wikipedia article for #P states that if we have a polynomial-time algorithm for a #P-complete problem, P = NP is true.
As #2SAT is #P-complete, this would mean that providing a polynomial-time ...
- 195
0
votes
2
answers
40
views
What are the definitions of countable and measurable colourings of a graph?
In this paper, the author discusses colourings of the plane, or in other words, of the underlying graph. I suppose a finite colouring is a colouring using at most $k$ colours for some natural number $...
- 737
2
votes
1
answer
227
views
What is the (intuitive) relation of NP-hard and #P-complete problems?
From Wikipedia on $\mathrm{NP}$-completenes: "a [decision] problem is NP-complete if it is both in NP and NP-hard." [link] I think we can paraphrase this as the first statement:
An $\mathrm{...
- 123
0
votes
1
answer
51
views
Efficiently count distinct in large range
I have a pubsub channel where an event is fired every time a user logs in, and I want to be able to query the unique users in a date range.
Solutions I thought:
Put the data in bigquery, and then use ...
- 113
1
vote
4
answers
672
views
Algorithm to find number of occurrences in mutually exclusive sets
Given multiple sets of three items, how can I find the most-commonly occurring item among the sets using only one item from each set. The sets don't have duplicates, but if I'm thinking about this ...
- 11
0
votes
0
answers
47
views
DJNZ command in Universal Register Machine
How do I represent DJNZ command of counting machine via commands of Universal Register Machine, those commands are CLR JNE INC and TR, via this commands i have to represent DJNZ command, any help ...
- 1
2
votes
1
answer
261
views
Sorted list of counters in constant time
Summary.
A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements.
...
- 625
0
votes
1
answer
53
views
Universal quantification and the number of solutions
How would one count the amount of solutions to quantified formulas that have universal quantifiers? For example, for a boolean formula $\Phi(X)$ with a number of solutions $\#\Phi(X)$ let's construct ...
- 1,429
1
vote
1
answer
74
views
Can we show that #3CNF is in FPTAS
If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
- 33
1
vote
0
answers
71
views
Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?
If you have an $\alpha$-approximation algorithm $A$ for some problem $f \in \#P$, such that (for $0 < \alpha \leq 1$)
$$
\alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha},
$$
does that automatically ...
- 33
1
vote
3
answers
69
views
How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?
I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation
so that I can get ...
- 23
2
votes
1
answer
1k
views
Applications of the DGIM algorithm
In the field of mining of data streams the algorithm of Datar-Gionis-Indyk-Motwani (DGIM, M. Datar, A. Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics over sliding windows,” SIAM J. ...
- 125
2
votes
1
answer
99
views
Why can’t we use FPRAS for #DNF to estimate #CNF?
Why cant we approximate the number of satisfying assignments of a CNF formula $g$ by first counting the solutions to $\neg g$ (which is in DNF) using the FPRAS for $\#DNF$ and then estimating the $\#g$...
- 173
0
votes
1
answer
35
views
Counting all subsequences constrained to a condition
I was trying to find all subsequences constrained to the following conditions:
remove element from the end.
remove element from the beginning.
remove element from both sides.
For example, given the ...
- 493
1
vote
0
answers
168
views
Determining the number of reachable vertices from every vertex in a directed acyclic graph
Let $G = (V, E)$ be a directed acyclic graph, which is quite sparse (in the examples I have in mind, $|E| \approx 10|V|$ or so). For each vertex $v \in V$, let $f(v)$ be the number of vertices ...
- 266
1
vote
1
answer
41
views
How many functions require precisely $n^2$ gates?
I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\{0,1\}$ output, and requires precisely $n^2$ NAND gates. I'...
- 315
1
vote
1
answer
121
views
Proving that deterministic approximate counting uses log(n) space
We just saw the Morris algorithm in class and we were asked the following:
In class, we saw a constant factor approximate randomized counting
algorithm with space complexity $O(\log \log n)$, where $...
- 143
0
votes
0
answers
60
views
Is there a reduction from 2sat to bpm?
Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
- 2,881
-1
votes
1
answer
116
views
Sorting elements into k subarrays
Given are $n$ integer numbers in the range $0$ to $5n$.
A SubSort algorithm organizes the numbers into $k=n/100$ sets,
$s_{1}$, …, $s_{k}$ , each containing $100$ numbers, such that the
following ...
- 231
1
vote
1
answer
45
views
Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain
Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any
$L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why.
I think the claim is incorrect, and I'm trying ...
- 125
0
votes
1
answer
104
views
Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string
This was an algorithm problem but I am having problems in formulating it.
I have a certain approach but I do not know how to fully execute:
Given
26 letters in total
All possible strings of length n
...
1
vote
0
answers
35
views
4
votes
2
answers
3k
views
How can we count the number of pairs of coprime integers in an array of integers? (CSES)
For reference, I am trying to solve this CSES Problem.
The problem basically states that given up to $10^5$ positive integers in the range $[1, 10^6]$, find the number of pairs of those positive ...
0
votes
0
answers
263
views
Count of different ways to express N as the sum of given numbers
I'm working on a case and I need some help :)
I need to find number of ways and solutions itself to express N as the sum of given numbers.
So, Sum (N) = 600 and the numbers from which I need to get ...
4
votes
1
answer
44
views
Model Counting for Sum of Conjunctive Formulas
Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ ...
- 41
4
votes
2
answers
330
views
Why does my code work: bijecting binary trees to Dyck paths
The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
- 305
2
votes
1
answer
119
views
Counting substrings that belong to a regular language
Given a regular language $L$ and a string $x$ give an efficient algorithm to count the occurrences of substrings $x[i,j] \in L$.
More in particular, I am looking for a linear time algorithm in the ...
- 29.8k
2
votes
1
answer
493
views
Number of substrings possible with even characters
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' ...
- 57
0
votes
1
answer
62
views
Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?
I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property:
For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct ...
- 623
2
votes
1
answer
75
views
#perfectMatchings is self-reducible
How can one show that the counting problem:
Given a graph, output the number of perfect matchings
Is self reducible?
I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:
...
- 23
1
vote
1
answer
75
views
What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a
I'm given the following python function:
...
- 250
2
votes
0
answers
37
views
Counting paths by their type
An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values ...
- 266
1
vote
1
answer
150
views
Iterate unique sets of integers
I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have ...
- 113
5
votes
2
answers
457
views
Efficient Algorithm to Find the n-th Odious Number
An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script ...
- 53