Questions tagged [counting]
The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.
166
questions
0
votes
0answers
23 views
Is there a reduction from 2sat to bpm?
Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
-1
votes
1answer
48 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
1answer
34 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 ...
0
votes
1answer
33 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
0answers
31 views
6
votes
2answers
271 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
0answers
25 views
Counting the number of comparisons in red black tree
I have an array with $N$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows:
for each element
if element not in tree
insert ...
0
votes
0answers
17 views
Counting distinct elements in array using hash table and measuring efficiency
I need to implement an algorithm to solve the Count-distinct problem given an array of $N$ elements using a hash table, and devise metrics with which to measure my algorithm efficiency. I was told I ...
0
votes
0answers
44 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
1answer
39 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$ ...
4
votes
2answers
103 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
1answer
71 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 ...
2
votes
1answer
149 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' ...
0
votes
1answer
48 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
23 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
60 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
41 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
332 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
31 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
73 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
39 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
173 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
79 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
220 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
99 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
67 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
78 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
38 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
2k 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
106 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
131 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
390 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
43 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
19 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
275 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
121 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 ...
3
votes
1answer
54 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
429 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
135 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
78 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
2k 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
132 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
63 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
147 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
240 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 ...
