Questions tagged [counting]
The term Counting in Computer Science is usually used to refer counting objects in certain arrangements or with certain properties.
145
questions
0
votes
0answers
5 views
Is counting the number of occurences in NC¹?
Let $c ∈ ℕ₊$ be constant and $p∈\{0,1\}^c$ a fixed bitpattern of width $c$.
Let us assume that the input length is structured as a list of blocks $b_1 … b_n$, each block having width $c$; is it ...
0
votes
0answers
11 views
algorithm for a #SAT oracle (#SAT algorithm)
i tried to look for an algorithm that decides whether an input x is in #SAT or not.
$\#SAT$ is defined, at least in this case to be: $<\phi ,k>=\left\{\phi \:is\:a\:boolean\:formula\:with\:at\:...
0
votes
2answers
43 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
56 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
27 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 ...
2
votes
1answer
88 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
0answers
14 views
Count to infinity problem (routing) between unsynchronized stations(tricky)
i was wondering, will count to infinity can occur in the following cases? if so, will it necessarily occur or can the routing tables stabilize themselves?
Distances:
From A to B - 3
from B to C - 4
...
0
votes
2answers
88 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
65 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
33 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
22 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
110 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
25 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
49 views
Counting number of apples in an apple tree with given number of layers
This problem comes from a competitive programming question, and it seems to require dynamic programming.
There are several layers of apples arranged in a formation with each apple having a value ...
0
votes
0answers
15 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
86 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
97 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
41 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
116 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
66 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
44 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
719 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
52 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
370 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
88 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
0answers
11 views
List maximum number of three-sets
Suppose i'm given with pairs component-quantity. I need to list maximum number of possible three-sets.
{AA}, {BB}, {C}, {D} => {ABC},{ABD}.
To list two-sets ...
0
votes
1answer
42 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
98 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
121 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
26 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
34 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
282 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
37 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
36 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^...
1
vote
0answers
33 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
64 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
58 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
168 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
75 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
1answer
479 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
36 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
84 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.
...
0
votes
2answers
65 views
Why it is not $O(m)$ but $O(\log m)$?
I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.
Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.
...
0
votes
2answers
120 views
Defining decision-problem complexity classes by counting branches of a polynomial-time NTM
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
0
votes
1answer
170 views
Can I make last part of counting sort become to be starting from lowest index?
Counting sort is originally like below code.
...
0
votes
1answer
137 views
How to count number of 1s of the first k positions in a bitset (bitmap)?
Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.
Output: the total number of 1s in the first $k$ position of $b$.
Obviously it can be done in $...
-1
votes
1answer
79 views
Counting (enumerating) minimal solutions of a dual horn formula
Is there an efficient algorithm ("does not necessarily have to be a polynomial time algorithm") to compute all "minimal" solutions for a Dual Horn formula (conjunction of clauses where each clause ...
0
votes
1answer
58 views
On FPTAS and many one parsimonious reductions
We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.
If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an ...
1
vote
1answer
159 views
Counting solutions of a particular type in HORN SAT
I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same.
Suppose we have a HORN SAT -: $(x_1) \land (x_2 \implies x_1)$, ...
0
votes
1answer
78 views
Modified Counting Inversions problem using divide and conquer
Given an array $A$, find the number of pairs $(i, j)$, such that $ i > j$ and $A[i] \ge A[j]$.
This is a modified version of the famous problem of Counting Inversions, only in this version it ...
