# Questions tagged [counting]

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

160 questions
Filter by
Sorted by
Tagged with
0answers
21 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 ...
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 ...
0answers
39 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 ...
1answer
30 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$ ...
2answers
95 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 ...
1answer
61 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 ...
1answer
99 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' ...
1answer
47 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 ...
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: ...
1answer
59 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: ...
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 ...
1answer
40 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 ...
2answers
317 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 ...
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 ...
1answer
64 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 ...
1answer
27 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 ...
2answers
168 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\}$.
0answers
73 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 ...
2answers
180 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 ...
1answer
95 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 ...
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 ...
0answers
75 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 ...
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 ...
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 ...
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....
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 ...
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 ...
1answer
117 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 ...
2answers
336 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 ...
1answer
41 views

1answer
79 views

### $P=PP$ or $P=PSPACE$ vs $VP=VNP$

We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$? Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$? Is there a way to show $\#P$ is in $FP^{PP}$?
1answer
212 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 ...