Questions tagged [counting]
The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.
200
questions
0
votes
1
answer
169
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 ...
- 81.7k
1
vote
1
answer
361
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{#(...
- 7,455
2
votes
0
answers
301
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 ...
- 125
1
vote
1
answer
42
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 ...
CommunityBot
- 1
1
vote
0
answers
38
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 ...
- 1,428
2
votes
2
answers
475
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 ...
- 178
3
votes
1
answer
582
views
Find smallest enclosing circle
On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
CommunityBot
- 1
0
votes
0
answers
88
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} (...
- 7,455
1
vote
1
answer
319
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 ...
- 277k
0
votes
0
answers
183
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. ...
- 1,428
4
votes
2
answers
116
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 ...
- 1,585
2
votes
1
answer
85
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 ...
- 277k
-1
votes
1
answer
139
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 ...
- 21
2
votes
0
answers
314
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.
...
- 7,455
0
votes
2
answers
99
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$.
...
- 987
2
votes
3
answers
1k
views
Computing a histogram with the number of extant values not known in advance
(This may be more fitting for CSTheory, I'm not sure.)
I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
- 965
1
vote
2
answers
231
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) ...
- 1,096
3
votes
0
answers
39
views
Number of distinct single-assignment forms with $j$ binary function calls?
Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there?
The only assumption made about $g$ is that if $a = c \...
- 13.4k
1
vote
1
answer
333
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)$, ...
D.W.♦
- 159k
0
votes
1
answer
155
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 ...
D.W.♦
- 159k
9
votes
2
answers
1k
views
Counting islands in Boolean matrices
Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
- 101
3
votes
0
answers
164
views
How hard is APPROXIMATE-#SAT? [closed]
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
- 31
1
vote
0
answers
145
views
Is there a simple way to construct a Boolean formula that is true if and only if at most $k$ of the input variables are true? [duplicate]
I could of course construct a truth table for the function
$$f(x) = \left(\sum_i x_i\right) \leq k$$
Where $x$ is an assignment and I'm slightly abusing notation to count Booleans. And then I could ...
D.W.♦
- 159k
-1
votes
1
answer
35
views
Count points on same distance from set of points
Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
D.W.♦
- 159k
2
votes
1
answer
82
views
Counting number of permutations respecting partial order
Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
- 277k
1
vote
3
answers
2k
views
How many 3-SAT expressions with up to N variables are satisfiable?
TL;DR
There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
- 485
3
votes
1
answer
2k
views
Radix, merge, counting sort and when to use
Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places.
So, for example,
123.456,
343.645,
234.543,
863.238,
956....
CommunityBot
- 1
1
vote
2
answers
798
views
Count numbers less than $K$ in array
Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and ...
- 1,331
2
votes
1
answer
107
views
Proving or disproving a set of total functions is countable
Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for
all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. ...
- 3,572
0
votes
1
answer
77
views
Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays
$k = \Theta(n)$
The arrays consist only natural numbers $1$ to $n$
The sum of the length of all arrays = $\Theta(n)$
It should return the $k$ original arrays, each sorted on its own.
The running ...
- 3,572
2
votes
0
answers
62
views
Approximate count per element in list/stream via Counting Bloom+Morris
I've a large list A of elements. Given another list B of elements, I need B to be sorted by ...
- 91
1
vote
1
answer
736
views
Sorting an array in linear time
I need to find a method to sort an array in $O(n)$ time complexity.
I saw this link,
however I'm not sure how to apply it to the elements I need.
Input: an array $A$ of length $n$, containing values ...
CommunityBot
- 1
2
votes
1
answer
79
views
On lowness of $\oplus P$
$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$).
Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$?
Are there complexity classes $\mathcal C$ ...
- 277k
2
votes
1
answer
2k
views
How to count all contiguous subsequences with positive sum?
I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$.
I need to count how many contiguous subsequences have positive sum.
This pseudocode demonstrates ...
- 277k
5
votes
0
answers
397
views
Count Wildcard Parenthesizations of a String
Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
- 72.4k
0
votes
1
answer
511
views
Using Pascal's Triangle to implement queues and stacks using heaps
I have the following question as homework in an algorithms, analysis and data structures class:
And here's an answer I wrote up:
A queue is a first-in-first-out data structure. A heap is a data ...
- 30.6k
3
votes
1
answer
315
views
How many different trees can we form from given graph?
I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$
In this graph I want to count the sub-...
- 2,926
1
vote
3
answers
914
views
Are counting problems the same as problems involving listing all possible combinations?
I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of ...
- 30k
0
votes
1
answer
94
views
What's wrong with this [closed]
Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count).
I then write this code down:
table = new SimpleTable("baby-...
- 115
2
votes
3
answers
674
views
Count arrays with size n, sum k and largest element m
I'm trying to solve pretty complex problem with combinatorics.
Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K ...
- 277k
0
votes
1
answer
253
views
How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions
How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:
no or minimal redundancy
only use 1 integer variable or k independent integer variables with a ...
- 9
0
votes
1
answer
266
views
Proving $\#CYCLE \in \#P$
I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.
I saw this question:
...
- 277k
-1
votes
1
answer
69
views
Display Counting Algorithm
I am writing some firmware for a display that will take measurements and present them in real time on an LCD screen. I would like for the measurements to display as smoothly as possible... What I mean ...
- 13.4k
0
votes
0
answers
53
views
Number of possible balanced binary trees [duplicate]
A tree is balanced if the subtrees of each node differ in height by at most one.
How many balanced binary trees can we create from $n$ nodes?
- 277k
0
votes
0
answers
172
views
Finding all possible bottom-most overlapping rectangles on a table
Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for ...
5
votes
0
answers
760
views
Sorting in place & stable in linear time
Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics-
The algorithm runs in $O(n)$ time.
The algorithm is stable.
The algorithm sorts ...
- 280
5
votes
2
answers
2k
views
Counting substrings with a given number of different characters in O(N)
Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters.
The obvious solution takes $O(n^2)$ time ...
D.W.♦
- 159k
2
votes
1
answer
469
views
Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph
Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave ...
- 191
0
votes
1
answer
69
views
Finding alternative way of combinatorial counting
The question is related to databases:
There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are?
I thought if any one of the $(n-...
- 3,276
1
vote
0
answers
103
views
What are widely-used, practical applications to come from the study #P problems?
When, beyond theoretical exercises, do we care how many solutions we can find for something?
I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
CommunityBot
- 1