All Questions
Tagged with discrete-mathematics computer-science
716
questions
0
votes
0
answers
30
views
Question on the karp reduction (many-one reduction)
I have encountered a question and breaking my head on it,
Prove or disprove:
For every two decision problems S_1,S_2∉{∅,{0,1}^*} if there is a karp reduction from S_1 to S_2 so there is a karp ...
- 1
0
votes
1
answer
132
views
Deterministic finite automata that accepts words with even number of zeros OR even number of ones
Dear Math Stack Exchange users!
I want to create a deterministic finite automata with max. 5 states, that accepts the language :
$$A:=\{u\in\{0,1\}^*\mid |u|_0\textrm{ mod } 2 \equiv 0\lor|u|_1\textrm{...
0
votes
2
answers
84
views
Binary sequences without optimal autocorrelation
A binary sequence of period $n$ is a sequence $\{s(t)\}$ with $t=0,1,\ldots,n-1$ and $s(t)\in \{0,1\}$. For these sequences define its autocorrelation function in the usual way. For instance, if $n$ ...
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
4
votes
0
answers
79
views
Prove that $A^{c}\subseteq B\cap C^{c}$ iff $(A\cup B)\cap(A\cup C^{c}) = U$ [closed]
Let $A$ and $B$ be subsets of the universal set $U$. Prove that
$$A^{c}\subseteq B\cap C^{c} \Longleftrightarrow (A\cup B)\cap(A\cup C^{c}) = U$$
We haven't learned any laws surrounding subsets in ...
- 85
0
votes
0
answers
32
views
What is the intersection of this relation?
If I have to find the intersection of a relation: which per my class’ notes is a family, then the intersection of a family is defined as such:
∩F= {x : for all A, A ∈ F → x ∈ A}
Now if I have to find ...
- 11
0
votes
2
answers
113
views
Solving the following recurrence equation $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5 $
Solve the following recurrence equation: $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5$.
I need to solve this equation but when I get to the particular solution with $n^2$ some of the terms I need ...
- 1
1
vote
2
answers
71
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 271
2
votes
0
answers
52
views
Fastest way to get from one permutation to another (with distances between elements)
Imagine that I have some rows of shelves. Some shelves have items on them. Some may be empty. Imagine also that I have computed the shortest paths between each location (using Dijkstra's algorithm, ...
- 241
0
votes
0
answers
54
views
Are books on mathematics related topics for computer science from 20+ years ago still relevant?
I am planning to take a computer science degree soon. I have found that topics such as discrete mathematics and probability & statistics are included in their syllabus. I wanted to read books on ...
- 109
1
vote
1
answer
193
views
Lambda Calculus: Proving exponent property by induction
Recently I have learned that given Church numerals $\bar n = \lambda fx.f^n x$ and $\bar m = \lambda fx.f^m x$, we can calculate $\overline{m^n}$ by applying $\exp=\lambda mn.nm$. I believe this means ...
- 23
0
votes
1
answer
51
views
Convert $k$ numbers into a single number with $\log_2{n_k + k \choose k}$ bits
Suppose we have $k$ natural numbers such as $n_1 \leq n_2 \leq n_3 \leq \ldots \leq n_k$. Is there any encoding algorithm that alllow to encode this numbers to one number with $\log_2{n_k + k \choose ...
- 13
0
votes
1
answer
24
views
What is the best-case number of array item comparisons in this algorithm, in terms of n?
The Smart Bubble Sort.
Preconditions: x1, x2, ... , xn is in U, a set that is totally ordered by <, and n ≥ 2.
Postconditions: x1 ≤ x2 ⋯ ≤ xn.
...
- 3
0
votes
1
answer
34
views
Condition for a Hamiltonian cycle existing proof question
Let $G$ be a graph. If there exists $X\subseteq V(G)$, $X\neq \emptyset$ s.t. $G\setminus X$ has more than $|X|$ components, then $G$ has no Hamiltonian cycle.
Proof.
Suppose for a contradiction that $...
- 2,971
0
votes
0
answers
303
views
Prove that MergeSort is stable for any input size n ∈ N using induction on n.
In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
