All Questions
Tagged with discrete-mathematics computer-science
58
questions
2
votes
4
answers
285
views
Evaluate $6^{433} \pmod {21}$ and a proving question
Question 1:
Denote $a \mod b$ as $a \% b$, where $a$ and $b$ are some integers
Evaluate 12^32475 % 21
The following is what I tried:
...
- 145
1
vote
4
answers
46k
views
Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.
Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then
$$
$$
(i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$)
$$
$$
(ii) if $a$ | $b$ then $a$|$bc$ for all integers $c$;
$$
$$
(iii) if $a$ |$b$ ...
- 1,641
1
vote
1
answer
784
views
Give Lambda Calculus Term for Haskell Function
I am working on a larger project translating Haskell to Lambda calculus. I would like to give a lambda term to specific Haskell functions. I am not quite sure how to approach two of them. I went ahead ...
- 11
-1
votes
1
answer
1k
views
Lambda Calculus Beta reductions
I have two questions about $\beta$-reduction in the $\lambda$-calculus. Please find them below. I have also included some background information about how lists (i.e. finite sequences) can be encoded ...
user867914
12
votes
4
answers
21k
views
How many bit strings of length 8 start with "1" or end with "01"?
A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have?
I ...
- 263
10
votes
5
answers
2k
views
convert ceil to floor
Mathematically, why is this true?
$$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$
Assume $a$ and $b$ are positive integers.
Is this also true if $a$ and $b$ are ...
- 203
6
votes
1
answer
4k
views
Why in RSA, the public exponent $e$ must be coprime with $\phi (n)$
I'm trying to understand the RSA cryptosystem, and that's what I know so far:
If we think about some number $m$ as the message, then we are searching a $e$ and $d$ such that
$$m^{ed} \equiv m \ \ (\...
- 6,756
4
votes
6
answers
483
views
Number of bit strings of length $n$ with no $k_1+1$ consecutive 0s and no $k_2+1$ consecutive 1s.
Just as the question asks. I am trying to calculate the number of bit strings of length $n$ with a maximum of $k_1$ consecutive $0s$ and $k_2$ consecutive 1s. Of course we assume $k_1+k_2\leq n$. I am ...
- 2,457
4
votes
1
answer
1k
views
Infinite lists in Lambda calculus....
I have been learning Haskell for a number of months now and am now trying to understand the underpinning $\lambda$-calculus, but I have run into a bit of a mental block! How would I go about writing ...
user156182
4
votes
1
answer
590
views
The disease problem
Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion.
At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
- 213
3
votes
2
answers
16k
views
Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations
I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
3
votes
2
answers
6k
views
How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps? [duplicate]
Problem:
a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps.
b) Prove your answers to a using strong induction.
My work:
(I am only working on part a for ...
- 1,884
3
votes
2
answers
784
views
How to find a function that is the upper bound of this sum?
The Problem
Consider the recurrence
$ T(n) =
\begin{cases}
c & \text{if $n$ is 1} \\
T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1}
\end{cases}$
A. Express ...
- 1,884
1
vote
2
answers
6k
views
How to prove Big Theta on polynomial function?
Im working on the Big-O notation and struggle to understand whether I have done enough to prove the following:
$5n^3+4n^2+4 \in \Theta (n^3)$
So based on the definition of $Θ(g(n)):$
Step $1$: $0 ≤ ...
- 355
1
vote
1
answer
138
views
Graph and one Sequence challenge
We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
- 11