All Questions
Tagged with discrete-mathematics computer-science
716
questions
0
votes
0
answers
43
views
Question On Function Growth rate
Assume we have the grow rate of $log(n^{2n})$, $log(n!)$, $n(log(n))^3$, $n(2^n)$, $n^{(1.5)}$,$n^{(log(log(n)))}$,$\sqrt{2^{log(n)}}$,$2^{(\sqrt{log(n)})}$,$2^{(log\sqrt{n})}$,$2^{(2n)}$, $(log(n))!$ ...
- 1
2
votes
1
answer
136
views
An undirected graph is partitioned. For every partition $V_1 \cup V_2 = V$, $v_1 \in V_1$ is connected to some $v_2 \in V_2$. Show it is connected.
We have an undirected graph $G = (V, E)$ partitioned into two non-empty subsets $V_1 \cup V_2 = V$. For this graph it holds that $(V_1 \cup V_2 = V) \implies (\exists v_1, v_2 : v_1 \in V_1 \land v_2 \...
- 1,211
1
vote
1
answer
45
views
Converting base of probability
I have a probability distribution $\frac{(p_0,p_1,...,p_s)}{a}$ where $\sum_s \frac{p_s}{a} = 1$ and $p_s \in \mathbb{N}$ that I want to convert to another distribution $\frac{(q_0,q_1,...,q_s)}{b}$ ...
- 11
1
vote
1
answer
304
views
Time Complexity of Modular Multiplication
I was reading a paper about the Miller-Rabin primality test and I came across the statement that the time-complexity of a modular multiplication is equivalent to $\mathcal{O}((logN)^2)$ using the ...
- 33
4
votes
0
answers
61
views
How many dice rolls would it take, for an N-sided die, to guess with 99% probability that the number of sides is N?
Thought of this question today when I was looking at the dungeons and dragons dice.
- 61
2
votes
1
answer
84
views
A confusion on $\beta\eta$-reduction
Recently I've started exploring lambda calculus, and currently I'm tackling the next exercise:
Prove that if $M =_{\beta\eta} N$, then $FV(M) = FV(N)$,
Where $FV(P)$ stands for free variables in the ...
- 432
2
votes
1
answer
726
views
Lambda Calculus Xor
How do you prove $\mathsf{xor} \, \mathsf{True}\, \mathsf{True}$ is false in lambda calculus using call-by-value reduction.
This is the approach I tried but it is not working:
$$\mathsf{xor} \equiv \...
2
votes
2
answers
741
views
What is a tuple?
In theory of computation, DFA's, NFA's, etc. are represented as a "tuple". Probability spaces are tuples. I am confused on what the notion of a tuple is and how it differs from a set?
1
vote
0
answers
50
views
Lambda Calculus Beta Reduction - How do I do this?
I'm trying to figure out a Lambda Calculus 𝛽-reduction, but I can't seem to get my head around whether I'm doing this correctly.
Beta reduction problem
I'm trying to beta reduce ...
- 11
0
votes
1
answer
709
views
converting binary fractions with a recurring expansion to decimal (denary) system
suppose the binary numbers 0.1010…. or I mean 0.(10) ̅ a recurring binary fraction
And 0.1(0101) ̅ a recurring binary fraction but with 1 digit before the period starts
can these numbers be ...
1
vote
1
answer
68
views
Combinatorics Question Relating to "At least"
Your help is greatly appreciated, rather simple question but not quite sure how to go about it.
Determine how many different possible combinations of computer science classes numbered 300 or above ...
3
votes
2
answers
145
views
Characterising functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying special equations
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ be a function.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(x+a)}= 0,
$$...
- 25.3k
4
votes
1
answer
183
views
Every boolean function is multiplicative with probability greater than $1/2$
Let $f:\left\{-1,1\right\}^n\to\left\{-1,1\right\}$.
How to show that
$$
P_{{x,y,z}} \{f(xyz)=f(x)f(y)f(z)\} \ge 1/2?
$$
where $x,y,z$ are distributed uniformly and independently on $\left\{-1,1\right\...
- 25.3k
3
votes
4
answers
79
views
how to prove $A+A'B+A'B'C+A'B'C'D=A+B+C+D$
Prove the above relationship by using the Boolean definition. I tried $A+A'B=A+B$, but end up with $A+B+A'B'(C+D)$, how can I go next?
- 61
1
vote
3
answers
372
views
finding and proving a greedy algorithm to maximize total energy
Find a function $f:\mathbb{R}^2\to \mathbb{Z}$ that satisfies the following properties, or show that no such function exists:
$f$ is increasing with respect to its first coordinate (i.e. $f(x, a) \...
- 1,166