Questions tagged [counting]
The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.
153
questions
1
vote
1answer
42 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 ...
2
votes
1answer
21 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:
...
1
vote
1answer
54 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
0answers
33 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 ...
1
vote
1answer
38 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 ...
5
votes
2answers
286 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 ...
1
vote
1answer
29 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 ...
1
vote
1answer
44 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
1answer
22 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 ...
2
votes
2answers
114 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
0answers
58 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
2answers
105 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 ...
1
vote
1answer
70 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 ...
0
votes
2answers
65 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
0answers
72 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
1answer
37 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 ...
3
votes
1answer
949 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
2answers
101 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....
4
votes
1answer
67 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 ...
3
votes
0answers
34 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 ...
1
vote
1answer
84 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
2answers
182 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 ...
3
votes
1answer
39 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]]...
0
votes
0answers
17 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 ...
2
votes
1answer
182 views
Number of ways painting graph in two colors, such that two nodes of same color are linked by edge
We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
1
vote
2answers
115 views
Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems
I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an ...
2
votes
1answer
49 views
Estimation of the number of solutions by Counting
This is a question from a quantum computation textbook.
Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
1
vote
1answer
304 views
How to find the Big-O for finding combinations of balanced parentheses?
Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be:
...
2
votes
2answers
97 views
Prove that this language is NP-Hard
Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$
prove that $\mathrm{\#3SAT}$ is NP-Hard.
I am currently stuck with ...
3
votes
1answer
64 views
Why does not valiant's reduction show NP=RP?
Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$.
We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in ...
1
vote
1answer
2k views
How many ways to express N as sum of 2, 3 and 5?
I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:
N = 5 + 2
N = 2 + 5
N = 2 + 2 + 3
N = 2 + 3 + 2
N = 3 + 2 + 2
But most of I found on the Internet that the ...
3
votes
1answer
70 views
The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$
where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
1answer
1k views
Limitations of DFA [duplicate]
In this link it is mentioned:
A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.
But counting is not enough -- consider a language of ...
0
votes
1answer
117 views
Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0
votes
1answer
55 views
Can someone give me the definition of #Monotone-2SAT?
In the decision problem, I set all variables to true and see if the formula is satisfiable.
My question is because I do not understand how there can be multiple solutions, though all variables are ...
1
vote
1answer
131 views
Find total count of all paths starting from a fixed vertex to all other vertexes of the graph
Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.
$$
\text{#(paths from 1 to 2)}+\text{#(...
2
votes
0answers
202 views
Min no.of operations required to convert an array to which it should contain elements of equal frequency
I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
1
vote
1answer
27 views
Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
1
vote
0answers
37 views
Count paths in matrix that visit each number exactly once [duplicate]
Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.
We want to count the number of paths that start ...
2
votes
2answers
374 views
Count-min sketch
I don't understand the use case of count min sketch.
Based on Count–min sketch, it says "serves as a frequency table of events in a stream of data.".
If I know there are N types of events, why can't ...
0
votes
0answers
74 views
Find xor sum of all pairs raised to power of 3
We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
3
votes
0answers
42 views
Does $P=PP$ or $P=PSPACE$ have consequences for algebraic class problem $VP=VNP$?
Deciding majority of counting problem is $PP$ class.
Is there any relation between $PP$ and $VNP$ and is there consequence of $P=PP$ or $P=PSPACE$ to $VP=VNP$?
Is there a way to show $\#P$ is in $FP^...
3
votes
1answer
196 views
Counting on a matrix
I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.
If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
1
vote
1answer
80 views
Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the ...
0
votes
0answers
165 views
Count submatrices with only zeros for each element of the matrix
Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...
4
votes
3answers
224 views
Sum of unique elements in all sub-arrays of an array
Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.
Subarrays:
...
4
votes
2answers
77 views
Count numbers less than $x$ co-prime to $p$
We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.
I know that we can solve the problem in $O(x\log x)$ with iterating over all ...
2
votes
2answers
767 views
How to find all topological sortings of a special DAG in O(N^2)
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
...
2
votes
1answer
42 views
Count number of the ways to fill a N-lengthed binary string
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
0answers
150 views
Counting subarrays where each number either doesn't occur or occurs odd number of times
We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times.
...
