All Questions
Tagged with discrete-mathematics computer-science
716
questions
-1
votes
0
answers
32
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 ...
-5
votes
1
answer
49
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
49
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 ...
0
votes
1
answer
49
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 ...
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
57
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
64
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 ...
2
votes
2
answers
224
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
76
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 ...
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 ...
0
votes
1
answer
84
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 ...
0
votes
0
answers
25
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$).
...
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
votes
1
answer
59
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 ...
5
votes
2
answers
144
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 ...
3
votes
1
answer
50
views
Finding a bound for existential quantification
Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set.
$$
L = \left\{ (x, \alpha, \beta) \in \omega \...
1
vote
1
answer
45
views
Why this configuration is not possible for the Tower of Hanoi?
I am studying the Tower of Hanoi, and as I read through some posts on here about the proof of optimality for the optimal solution, I found a comment that said there cannot be deadlocks in the TH game. ...
0
votes
0
answers
39
views
What is the asymptotically best algorithm for the euclidean Steiner tree problem?
So I would like to know what the fastest (asymptotically, worst case runtime) exact algorithm for the Euclidean Steiner tree problem is. (More precisely, I would like to know the best known algorithm ...
3
votes
0
answers
49
views
Inequalities for sum of $k$ smallest degrees of a graph
As part of a homework assignment, I am doing a proof for a generalised variant of Karger's algorithm and am stuck at a particular step. I have proven that for a graph $G=(V,E)$ [writing $n=|V|$] with ...
0
votes
0
answers
22
views
Minimum Number of Functions for a Universal Hash Family Mapping {a, b, c, d} to {0, 1}
Determining the Minimum Size of a Universal Hash Family
I'm working on understanding universal hash families and encountered a problem that I'm struggling to solve. The problem is as follows:
Consider ...
0
votes
1
answer
38
views
Formula for making maximum number of rational numbers with two integers
Imagine we have a formula that is supposed to create a rational number out of two given numbers:
uint8_t x;
uint8_t y;
Here x ...
-2
votes
2
answers
102
views
i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$. [closed]
Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ?
Hint there’s something related also with combination and ...
2
votes
3
answers
82
views
Generalization of independent set to distance at least 3
We know that in graph theory, an independent set is a set of vertices, such that no two of which are adjacent. There is rich theory about independent set, including approximation algorithm for finding ...
0
votes
0
answers
18
views
Do we try to prevent cycles in temporal logic (CTL)?
When looking at the formulas for the rules in CTL, it is said that we save the states we have already been in a in list/ set. Does that mean that we are trying to preven endless loops?
For example ...
1
vote
0
answers
32
views
How to find values that generate a particular boolean expression
On question 1 of our homework we are asked to find which values of the boolean variables equate to the resulting boolean expression. I tried finding resources on how to complete this but I came up ...
0
votes
1
answer
95
views
Natural deduction with $(A→B)→C, A∧B ⊢C$
$(A → B) → C, A ∧ B \vdash C$
1.$\hspace{1cm}(A → B) → C \hspace{1cm}$premise
2.$\hspace{1cm}A ∧ B \hspace{2.5cm}$ premise
$\hspace{2cm}$ 3. $\hspace{1cm} A \to B \hspace{1cm}$ Assumption
$\hspace{2cm}...
0
votes
0
answers
74
views
Is this natural deduction proof of $\exists x \neg Px \vdash \neg \forall x Px$ correct?
When it comes to proofs there is no way to tell whether I have done correct or not. In the solution they did in another way which makes me wonder if this correct? For future question, how can I verify ...
1
vote
1
answer
217
views
Complexity of a list problem
I have two lists $L_1$ and $L_2$ of real numbers which are of equal length $n$ and I would like to analyze the complexity of the following problem:
Select an index set $I\subseteq \{1,...,n\}$ with ...
0
votes
2
answers
232
views
How to prove with natural deduction?
Given this question, I tried solving in the first picture as you can see, but I didn't know how to continue and the second image is the right way to solve it. My question is have I done right so far? ...
0
votes
0
answers
54
views
Propositional logic: Natural deduction
Is the first solution valid? If not, can someone explain to me why the first solution is not valid but the second one is? Both claim that p and not p is true though?
$\lnot p \to p \vdash p$
$1 \...