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
1 answer
46 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
32 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 ...
1 vote
4 answers
633 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 ...
0 votes
0 answers
34 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 ...
2 votes
1 answer
150 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. ...
0 votes
1 answer
34 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,393
1 vote
1 answer
46 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
64 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
2 answers
38 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 ...
2 votes
1 answer
378 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
93 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$...
  • 163
0 votes
1 answer
28 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 ...
  • 459
1 vote
0 answers
80 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
37 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'...
  • 293
1 vote
1 answer
69 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
40 views

Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
  • 2,824
-1 votes
1 answer
94 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 ...
1 vote
1 answer
42 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
72 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
33 views

CountDistinct on a range

I have a dataset with and ID and a date looking like: ...
6 votes
2 answers
1k 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
139 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
43 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
181 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 ...
2 votes
1 answer
90 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 ...
  • 28.2k
2 votes
1 answer
265 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
56 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 ...
  • 591
2 votes
1 answer
42 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
69 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: ...
2 votes
0 answers
36 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
60 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
403 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
1 vote
1 answer
49 views

Polynomial time counter of solutions of 2SAT expression with pure literals

As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when ...
2 votes
1 answer
165 views

Count number of ways in which atomic operation(s) of n different processes can be interleaved

PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion. Suppose there are a total of n different ...
2 votes
1 answer
71 views

Enumerating every "partnering" without repeating partners

I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
  • 3,738
2 votes
2 answers
464 views

Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
1 vote
0 answers
96 views

Prove that $\#k-colouring$ graph problem is $\#P-complete$

I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting ...
1 vote
2 answers
347 views

Fastest algorithm for finding the number of primes in a range

Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M ...
  • 43
1 vote
1 answer
147 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
  • 315
0 votes
2 answers
69 views

To calculate how many times a certain year repeats itself in the calendar within a given year range

Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $[A, B]$. Is there any method to it ...
2 votes
0 answers
81 views

Counting triplets from three arrays satisfying the equation x^2 = yz

Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
0 votes
1 answer
47 views

Number of permutations of set {1, 2, ..., n} for which insertion sort will perform exactly n permutations

I have had the following problem at my last exam: For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons. My thinking ...
  • 13
3 votes
1 answer
3k views

Count total number of k length paths in a tree

This is a question from a competitive programming competition. Given a tree with n nodes and a number k, find the total number of paths of length k in that tree. I know for a fact that a solution can ...
0 votes
2 answers
134 views

How is the set of functions from ${\{a,b\}}$ to $N$ countable?

Assume a set of functions from ${\{a,b\}}$ to $N$ Where $N$ is the set of Natural numbers. Let us assume that the size of $N$ is $n$. i.e $|N|=n$ The first element $a$ have $n$ choices for mapping....
  • 271
4 votes
1 answer
70 views

Counting big enough elements

Let $v$ be a vector of positive integers of length $n$. I want to find the highest $k$ such as there are at least $k$ elements of $v$ that are greater or equal to $k$. What would be the best ...
  • 143
3 votes
0 answers
35 views

Estimating number of points in 1D space

There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
  • 31
2 votes
1 answer
275 views

Build a histogram from a very large data sample

I want to calculate a histogram from an array of size N. N is very large. I know 2 ways to do so: The naive approach is to ...
3 votes
2 answers
754 views

Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph. My solution is to do a modification of breadth first search from the ...
  • 1,263
3 votes
1 answer
124 views

Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$

Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$. I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
  • 177
0 votes
0 answers
21 views

Calculating Time Complexity of Algorithm Using Incrementor Variable [duplicate]

I am trying to calculate the time complexity of an algorithm using n in the code below. I have a working solution to a coding challenge to sort a stack using only ...