Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
0
votes
0answers
21 views
Solving a modular equation programmatically
Consider that I've a mathematical equation of the form:
$$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$
How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
1
vote
1answer
19 views
How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length
If I have the following system, I am wondering how to calculate the number of valid strings it contains.
The system is something like this, which can have arbitrary variations.
Only consists of an ...
1
vote
1answer
37 views
Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle
Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$.
Although ...
4
votes
1answer
62 views
Prove the probability of which a hash function is collision-free
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
38 views
Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$
Consider the recurrence
$$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$
I tried to solve this as follows. First, I found the homogeneous solution:
$$
a_n^{(h)} = r^2 - 3r + 2r \\
(r-2)(r-1) = 0 \\
...
0
votes
1answer
26 views
Recursive definition for the length of a string?
I found a couple of answers online but I don't quite understand why the answer is right:
The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the ...
0
votes
0answers
15 views
Can we apply master theorem on this? [duplicate]
I'm very confused. It's my first time here . Idk how to ask question here . Sorry if I made some mistake or anything .
T(n) = 2T(n/2)+ n/logn
1
vote
0answers
45 views
The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix
Let us define a $n \times 2$ matrix M consisting of integer sets, such
that the first column consists of the so-called intersecting sets,
and the second column ...
0
votes
0answers
12 views
How to understand DFA's and how to understand how to construct them based on a given regular language? [duplicate]
I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question : Construct a deterministic finite state automata ...
4
votes
1answer
264 views
Irregularity of language of prefixes of decimal expansion of pi
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the ...
1
vote
1answer
23 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-1
votes
1answer
38 views
Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?
Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
1
vote
0answers
55 views
Inductive proof on Quicksort with Explicit Stacking
Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
5
votes
2answers
82 views
Finding the cheapest buy order with fixed inflation for each product
Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.
Each ...
5
votes
1answer
127 views
How does treewidth behave under graph minor operations?
It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.
Minors of a graph are created through the ...
0
votes
1answer
210 views
Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:
For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
2
votes
2answers
190 views
Finding the maximum of a bitonic sequence
Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
25 views
Is it possible to denote “any single alphabet symbol” in an FSA state diagram?
This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA
My professor is asking for a finite automata state ...
-1
votes
1answer
34 views
Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
3
votes
0answers
78 views
Polynomial time algorithms for rank 1 elliptic curves over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
-4
votes
1answer
57 views
Is ∅ ∈ {{∅}} true? [closed]
I learned that the empty set is not an element of every set unless the empty set is explicitly included in the set like {∅}, so I believe it is false because it is not ∅ ∈ {∅}.
3
votes
1answer
59 views
Matrix Representation for logical gates?
I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
0
votes
1answer
43 views
How to “logically” solve boolean logic
I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.
...
0
votes
0answers
9 views
Most probable inputs assignment in Gaussian process
Given
A Guassian process $w(\mu^*,\Sigma^*)$
$n$ observations of the output
And $n$ potential inputs.
But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
0
votes
0answers
15 views
Possible Network Flow “Cuts”?
The possibilities are:
always full and always crossing. (True, per chart)
always full and sometimes crossing. (True, per chart)
always full and never crossing. (False?)
sometimes full and always ...
1
vote
0answers
18 views
Relation between deficiency and color class parity of graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
39 views
invite 12 person from 24 that we have 6 men and 6 womens [closed]
i had a question and its
"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
2
votes
1answer
44 views
Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process
The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(
Problem:
We implement a merge sort algorithm to sort $n$ items. The ...
1
vote
1answer
980 views
Define a DFA that accepts all even length binary strings that don't contain the substring “111”?
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
1
vote
1answer
254 views
How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?
Like in the title the following equation:
F(n)=F(n-1)+F(n-2)+f(n) F(0)=0, F(1)=1
...
2
votes
2answers
105 views
Prove that the number of edges is at least twice the number of vertices
I need to prove that
In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices.
I already know that $\deg(n) = ...
2
votes
1answer
47 views
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
0
votes
0answers
22 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
29 views
How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time
To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...
2
votes
1answer
26 views
What's the connection between the two “Fast Walsh Transform”?
First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
2
votes
1answer
23 views
Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)
Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are ...
1
vote
2answers
99 views
How do you go from $\log P = \log N$ to the next step?
Let
\begin{align*}
&P=2^{\log_2 N}\\
&\Rightarrow \log_2 P = \log_2 N\\
&\Rightarrow P=N\\
&\Rightarrow 2^{\log_2 N}=N\,.
\end{align*}
I don't understand how can ...
1
vote
1answer
34 views
Number of ways to choose same number of elements from two different sets
Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p,...
2
votes
1answer
51 views
Coin flipping problem on an $n \times m$ grid
There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly:
Flipping a row of coins;
Flipping a colomn ...
1
vote
1answer
43 views
Is every graph with minimum degree $n/2$ connected?
Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
Decide whether the above claim is true or false, and ...
1
vote
1answer
60 views
What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?
I am a master computer science student, and I am interested in both geometry and complexity theory.
So I would like to know what is the relations between discrete geometry, computer graphics, and ...
1
vote
1answer
39 views
Maximizing entropy under constraint
How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
1
vote
1answer
57 views
Discrete Mathematics Proofs for ∃ and ∀
Premises or Givens:
$∃x(A(x) → B(x))$
$∀x (B(x) → K(x))$
To Prove:
$∃x(A(x) → K(x))$
My Solution:
$A(z) → B(z)$ From premise and Existential instantiation $x$ for $z$
$B(z) → K(z)$ From ...
1
vote
1answer
76 views
Possible ways to have cross and full edges in a mincut maxflow
I am trying to solve the following problem about maxflow mincut
it seems like my conclusion is incorrect and I am wonder where.
There is no graph just following question.
An edge e can be (x) ...
4
votes
1answer
43 views
Probability of randomly designated subsets cover the universe
Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.
Is there a polynomial ...
0
votes
1answer
47 views
Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p
Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.
Could you explain ...
1
vote
0answers
58 views
Can somebody suggest what is wrong with these constraint? [closed]
I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances.
For example, the washing machine is appliance indicated ...
2
votes
1answer
531 views
Average height of a BST with n Nodes
I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
4
votes
2answers
66 views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
1
vote
0answers
42 views
For a minimum cut $(S, T)$, why do edges entering $S$ have a flow value of $0$?
I'm studying for an exam and I'm having trouble with a specific question:
Let there be a flow network $G = (V, E)$ with a maximum flow $f$ and capacity $c$, a source $s \in V$ and a sink $t \in V$, ...
