Questions tagged [counting]

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

172 questions
Filter by
Sorted by
Tagged with
25 views

How do I sort this sequence of numbers 3, j, j, 4, 3, 4, 2, 4, 4, j using the counting sort method?

How do I sort this sequence of numbers 3, j, j, 4, 3, 4, 2, 4, 4, j by the counting sort method?
43 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 ...
21 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 ...
2k views

Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
1k views

Count of distinct substrings in string inside range

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
80 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 ...
84 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$...
304 views

Can I make last part of counting sort become to be starting from lowest index?

Counting sort is originally like below code. ...
98 views

72 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 ...
35 views

Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
40 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 ...
31 views

CountDistinct on a range

I have a dataset with and ID and a date looking like: ...
669 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 ...
32 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 ...
18 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 ...
52 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 ...
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$ ...
83 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}$?
142 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 ...
176 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' ...
79 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 ...
5k views

Number of binary trees with given height

I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $\lfloor{lg (n)}\rfloor$). Edit: I forgot to add the ...
1k 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 ...
53 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 ...
33 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: ...
63 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: ...
35 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 ...
1k views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
46 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 ...
366 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 ...
37 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 ...
106 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 ...
266 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 ...
49 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 ...
280 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\}$.
88 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 ...
114 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 ...
494 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: ...
776 views

Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties: optimal substructure overlapping subproblems I stumbled upon an article which ...
265 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 ...
41 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 ...
68 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 ...
80 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 ...
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....