Questions tagged [counting]

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

Filter by
Sorted by
Tagged with
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 $...
chausies's user avatar
  • 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?
Abhishek's user avatar
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 ...
arshiamoeini's user avatar
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 $...
bihariforces's user avatar
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 $...
SagarM's user avatar
  • 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 ...
Anuj's user avatar
  • 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 ...
Anuj's user avatar
  • 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 ...
ShyPerson's user avatar
  • 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 ...
abcd's user avatar
  • 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 ...
Ten's user avatar
  • 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,...
DrownedSuccess's user avatar
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?
Mirco Paul's user avatar
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 ...
prototycoon2's user avatar
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 ...
Aishgadol's user avatar
  • 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^...
Abcd Dcba's user avatar
-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 ...
Max's user avatar
  • 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 ...
tonik's user avatar
  • 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 $...
J. Schmidt's user avatar
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{...
kostrykin's user avatar
  • 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 ...
Mascarpone's user avatar
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 ...
TheGuyMain's user avatar
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 ...
Tarik 's user avatar
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. ...
Matthieu Latapy's user avatar
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 ...
rus9384's user avatar
  • 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 ...
qc6518's user avatar
  • 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 ...
qc6518's user avatar
  • 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 ...
Newbieee's user avatar
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. ...
yarchik's user avatar
  • 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$...
SagarM's user avatar
  • 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 ...
Avv's user avatar
  • 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 ...
Joppy's user avatar
  • 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'...
Addem's user avatar
  • 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 $...
Skyris's user avatar
  • 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?
Turbo's user avatar
  • 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 ...
MathCurious's user avatar
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 ...
John D's user avatar
  • 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 ...
Aaryan BHAGAT's user avatar
1 vote
0 answers
35 views

CountDistinct on a range

I have a dataset with and ID and a date looking like: ...
Nicolas M.'s user avatar
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 ...
Christopher Miller's user avatar
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 ...
David Ambokadze's user avatar
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$ ...
boka's user avatar
  • 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 ...
Rohit Pandey's user avatar
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 ...
Hendrik Jan's user avatar
  • 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' ...
nihar's user avatar
  • 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 ...
Blanco's user avatar
  • 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: ...
bingo_b's user avatar
  • 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: ...
Ashkan Khademian's user avatar
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 ...
Joppy's user avatar
  • 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 ...
thephpdev's user avatar
  • 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 ...
InigoM's user avatar
  • 53