All Questions
Tagged with discrete-mathematics computer-science
716
questions
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 \...
- 3,468
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. ...
- 1,426
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 ...
- 131
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 ...
- 55
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 ...
- 161
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 ...
- 176
-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 ...
- 11
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 ...
- 166
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,237
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 ...
- 11
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}...
- 1,237
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,237
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 ...
- 19
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? ...
- 1,237
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 \...
- 1,237