All Questions
14
questions
4
votes
1
answer
102
views
Lambda calculus novice seeking help with defining isempty for list representation
I'm exploring the concept of untyped lambda calculus and I'm facing a challenge with defining the isempty function. I have a few definitions that I'm working with, which are:
...
- 41
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
-1
votes
1
answer
44
views
Recursively Defined Functions for string [closed]
Let be a recursively defined language over the alphabet Σ = {0,1} as follows. Basis case: ε ∈ L, where ε denotes the empty string. Recursive step: if s ∈ L
Recursively Defined Functions
can any one ...
- 11
0
votes
1
answer
426
views
Finding surjective but non-injection mapping from integers to the positive integers
Find an example of a function of a set of all integers to the set of positive integers that is surjective, but not injective.
I also need to prove it. I have tried but had no success. Even if I do ...
user764644
0
votes
2
answers
167
views
Discrete math question about surjective, injective function and domain, range
I'm a first year computer science student and I'm learning discrete math by myself (teacher unavailable) due to the quarantine and I dont understand these two little questions :
1) Lets say we have ...
user764644
0
votes
1
answer
29
views
Creating Arbitrary Equation For Quality Metric
I am trying to come up with an equation for a quality metric based on 3 attributes:
Defect-proneness (Scored as a decimal between 0 and 1 -> lower value is better)
Maintainability (Scored as a ...
- 3
0
votes
2
answers
438
views
Using the definition of $O$(big O) show that $6n^2$ $\notin O(2n)$
the definition of Big $O$ is..
$$f(n) < c g(n) $$
$$6n^2 < c 2n$$
if $c = 1$ and $n = 10$, then...
$$6(10)^2 < 1 \cdot 2(10) $$
$$600 < 20 $$
the above is false
Did i show this ...
0
votes
1
answer
37
views
How to obatain the following one to one function?
$$ f(x,k) = y$$
$$x<=k$$
$$x,k \in R$$
$$y \in [0,1]$$
The domain of the function would be $x$ to $k$ and the range would be $0$ to $1$. such that for $x=x$ the $y=0.0$ and for $x=k$ , $y=1.0$, ...
- 105
1
vote
1
answer
237
views
Likelihood for a random hash function not to be surjective
Let us define a hash function $$\begin{align*}
H \colon A &\to B\\
a &\mapsto b
\end{align*}$$
$$|A| \geq |B|$$
Assuming it is perfectly random (Hyp 1), we estimate the probability that ...
- 267
3
votes
1
answer
447
views
Constructing a recursive definition.
I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of ...
- 101
0
votes
1
answer
3k
views
Discrete Math: Functions and Set Questions
1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$?
1) $11$
2) $11$, $-11$
3) $1$, $-1$
4) $1$
2) Let $D ...
- 443
-1
votes
1
answer
374
views
How to prove such program is uncomputable
We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
0
votes
1
answer
3k
views
Ceiling to Floor Function Conversion Proof
I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this:
\begin{aligned}
q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q &...
- 83
4
votes
3
answers
4k
views
calculating unique value from given numbers
let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
- 41