All Questions
Tagged with discrete-mathematics computer-science
716
questions
0
votes
0
answers
21
views
Fixed quantities in Big O notation
Consider the following description of a random graph generation algorithm with parameters $n$ (number of vertices) and $m$ (number of edges).
All iterations add an edge except those where a ...
- 3,408
-5
votes
1
answer
48
views
Question about concrete mathematics double summation derivation [closed]
How did the author in the image convert the summation into a double summation? I can see how the double summation turns into the sum of squared integers but how would you go about converting the sum ...
0
votes
1
answer
48
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,408
0
votes
1
answer
47
views
Proof that if a graph has edge connectivity 3, then the girth is bounded by the number of nodes divided by two + 1, g(G) <= |V(G)| / 2 + 1
I've not been able to solve this problem for a week now. My idea was that I start with a circle with n nodes and because the edge connectivity is 3, every node must have at least 3 neighbours, so to ...
- 11
0
votes
1
answer
87
views
What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?
Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
-1
votes
2
answers
56
views
Why $d^*(q, \epsilon)$ has definition when $d(q, \varepsilon)$ does not in DFA?
I'm reading an online book about DFA and NFA but it confuses me.
Given a DFA say $D=(Q,\Sigma, q_0, \delta, F_Q)$, its transition function is a total function defined on every symbol from a given ...
1
vote
2
answers
62
views
XOR sum of array
When you are given an array of even number of elements:
[$a_1$ $a_2$ $a_3$ ….. $a_n$] ($n$ is even)
Assume the $a_i$ are not all zero
Let $S$ = the XOR sum of all these original elements
You will ...
- 41
2
votes
2
answers
220
views
What does it mean when the transition function of a NFA returns an empty set?
Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
2
votes
0
answers
74
views
the Ackermann function must be total and unique based on one specific list of rules
This is one following question based on one question I asked before.
In mcs.pdf, it has Problem 7.25 in p251(#259).
One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
- 416
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541
0
votes
1
answer
83
views
partial function version of the Ackermann function must be total
In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
- 416
0
votes
0
answers
24
views
Computing transitive closure for relation via other relation
The closure of a relation $R$ over a set $S$ is denoted $R[S]$ and calculated via $\bigcup_{i\in\mathbb{N}}Y_i$ where $Y_0=S$ and $Y_{n+1}=Y_n\cup R(Y_n)$. ($R(Y_n)$ is the image of $Y_n$ under $R$).
...
- 9
1
vote
1
answer
39
views
Constructing Truth Tables for Formulas with Variable Valuations
I was solving a problem from old exams and got stuck here. I'd appreciate the help.
We have the three variables p, q, and r. There are 8 valuations of the variables. If F is a propositional logic ...
- 1,237
-1
votes
1
answer
55
views
Hoare Logic: If-statement
Can someone explain the first assignment and implied? We prove bottom to up and I don't follor after the $(1=x+1)$ if-Statement. This is what my book says about the assignment rule:
, if we wish to ...
- 1,237
5
votes
2
answers
137
views
"Encode" all $n$-permutations with the fewest number of swaps
The goal is to find $m$ swaps $s_1, s_2, \dots, s_m$ such that any $n$-permutation can be encoded as a binary sequence of length $m$, $x_1, x_2, \dots, x_m$, where $x_i$ indicates whether to perform ...
- 51