Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
-1
votes
0answers
19 views
Formula for maximum matching in bipartite graph
Let $G = (U, W, E)$ be a bipartite graph. Show that $\alpha'(G) = \min(|U| - |S| + |N(S)|)$, where $S$ ranges over all subsets of $U$,
$\alpha'(G$) is the size of maximum matching of $G$, and $N(S)$ ...
5
votes
2answers
70 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
119 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
92 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 ...
3
votes
2answers
105 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
23 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
29 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
65 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
54 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
44 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
36 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
7 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
13 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
14 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
36 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
37 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
440 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
74 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
52 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
36 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
19 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
27 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
17 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
22 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
61 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
49 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
41 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
51 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
59 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
42 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
45 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
56 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
267 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
58 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
41 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$, ...
2
votes
1answer
31 views
Minimum number of strings to cover entire space within Hamming distance
Given $(n, k)$:
What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
Is there an asymptotic expansion or lower ...
8
votes
2answers
1k views
Double exponentials vs single exponentials
Here are four tenets I cannot reconcile:
Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant
Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
5
votes
2answers
94 views
Definition of “properly partial” versus “total” value types
In the Foundations chapter of Elements of Programming (Stepanov and McJones, 2009), this paragraph appears:
A value type is properly partial if its values represent a proper subset of the abstract ...
3
votes
1answer
26 views
Detecting isthmuses on digital curves
Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them.
I want to find the isthmuses, i.e. sections of the curve that are close to each ...
2
votes
1answer
58 views
Centre, diameter, and radius of graph
I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.
Ques1. ...
3
votes
1answer
56 views
Is k -rainbow coloring of a hypergraph NP-complete or not?
**A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The ...
-2
votes
1answer
61 views
Symmetric difference of a set with an empty set [closed]
The definition of symmetric difference of two sets $\alpha $ and $\beta$, $\alpha
\oplus \beta$ is defined as the set of all $x$ such that, $x \in (\alpha \cup \beta) - (\alpha \cap \beta)$.
If, $\...
0
votes
0answers
25 views
Classify manifolds with neural networks
Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
0answers
64 views
Best way to make the jump from programming to computer science
I have decent enough experience with programming to be able to tackle most things but I want to know how you recommend making the jump from just programming to computer science. I still have a couple ...
-1
votes
1answer
20 views
Independence groups and fully connected groups
Let G be a connected graph, knowing that it has more than 9 vertex, Show that either its independence number is bigger-equal than 4 or its click number (the size of the biggest fully connected group) ...
0
votes
1answer
312 views
Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components
Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.
0
votes
1answer
48 views
Can anyone find a mapping from the set of all possible string to the natural numbers?
Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?
$$h : S^* \rightarrow \mathbb{N} $$
Assume $S$ is finite. I would prefer an ...
