Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
361
questions
2
votes
0answers
21 views
Tighter bound for the total number of possible $m$-ary tree with $n$ nodes and maximum height $h$?
I know that the total number of possible $m$-ary tree with $n$ nodes is
\begin{align}
C_n&=\frac{1}{(m-1)n+1}{mn \choose n},
\end{align}
which is the Catalan number. I want to know if I can get a ...
2
votes
1answer
28 views
Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should follow to prove
that the language is not regular?
Assume that the language is ...
3
votes
2answers
101 views
Check for common element in two arrays using FFT
My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that ...
2
votes
1answer
27 views
Confusion about the Hiring Problem
I'm confused about where the probability from the hiring problem comes from.
For background:
We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). ...
1
vote
1answer
59 views
Lexicographic permutation
Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now ...
1
vote
1answer
21 views
How is expected value in entropy derived?
I was self learning about entropy and came across this equation.
$$
H = - \sum p(x) \log p(x)
$$
The equation for entropy in expected value,
$$
H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
1
vote
0answers
13 views
Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”
I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
-2
votes
2answers
78 views
Is a 'discrete language' well-defined?
Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ?
An argument w is a member of L under the following rules...
Example1:
If more than half of w's digits are 1's --...
0
votes
0answers
14 views
Total weight of Huffman Code
We are given the following letters with the respective frequencies:
\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
1
vote
1answer
35 views
computationally efficient linear index to index pair mapping
Consider two index sets $S = \{0, 1, 2, 3, 4, ..., N - 1\}$ and $Q = \{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\}$. Let $R = \{(a, b)\space |\space a, b \in S, a \ge b\} = \{(0, 0), (1, 0), (1, 1), (2, 0),...
2
votes
1answer
17 views
Enumerating every “partnering” without repeating partners
I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
1
vote
2answers
39 views
Master Theorem applicable here?
Let
$T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\
1 & \text{if }n=1
\end{cases}$
I need to prove that $t(n) \in ...
0
votes
1answer
46 views
Same notation/terminology for union of sets and concatenation (Kleene star)?
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
0
votes
0answers
44 views
Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph
This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
1
vote
1answer
65 views
Turing reducibility of 2 versions of the satisfiability problem
I need help with this problem.
There are 2 versions of the satisfiability problem:
[1] decision version: determine whether an arbitrary formula f is
satisfiable or not
[2] search ...
1
vote
1answer
62 views
Reducibility of 2 boolean satisfiability problems
I beg some help with this problem.
There are 2 boolean satisfiability problems.
Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$.
Problem $B$: Determining ...
0
votes
1answer
36 views
About computable sets
Let TOT be the set of all Turing Machines that halt
on all inputs.
Find a computable set B of ordered triples such that:
TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]
This definition means ...
1
vote
1answer
23 views
Is there a way to hash a turing machine?
If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
1
vote
0answers
40 views
Recursive Algorithm to compute Square numbers
I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this ...
0
votes
0answers
22 views
Stable matching with dynamic preference lists
I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
1answer
80 views
Prove or Disprove, 3SAT ā¤p 2SAT, then P = NP
I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
0
votes
0answers
38 views
If a problem A ā¤p B, then that B ā¤p A, prove or disprove
I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?
0
votes
0answers
23 views
How to determinne the loop invariant?
The following code returns the number of trailing zeros of an integer x (number of 0s at the end of the decimal number representation of x). I had to find its loop invariant, which is ...
1
vote
1answer
25 views
How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]
I need help how to interpret the following notation for $f$:
Zeroes and ones form a binary number which can be converted to
decimal notation. Thus, we may think of the computer as calculating a ...
1
vote
1answer
213 views
Turing reducible in natural numbers?
I'm confused about Turing reducible things.
I understanded Turing reducible like this
...
1
vote
1answer
23 views
Hoare Logic for Factorial
I came across this hoare logic for factorials but I don't quite understand it. We multiply F and X but we're not adding up all values of F so how do we get the sum/factorial at the end?
Precondition: ...
1
vote
0answers
21 views
Determining Range of Current Node in Segment Tree
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
2
votes
1answer
32 views
Recurrence Relations
I am starting to learn recurrence relations in class and I am having issue with this example:
T(N) = 2N - 1 + T(N-1)
I am bit confused as to get the base case.
I'm sorry if this seems elementary, ...
1
vote
1answer
38 views
Amount of k-partitions of a number
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
...
1
vote
1answer
30 views
How many snakes there can be in the “snakes and ladders” game?
How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?
UPD: My thoughts are simple, ...
2
votes
1answer
22 views
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):
"More ...
1
vote
0answers
71 views
Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?
My textbook states:
Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in generalāa CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
0
votes
1answer
35 views
Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations
I have had the following problem at my last exam:
For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.
My thinking ...
2
votes
1answer
47 views
Set which is easy to sample, but difficult to sample from its complement
Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
4
votes
1answer
86 views
Separating the snakes
In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal ...
2
votes
1answer
34 views
Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]
I'm pracitcing exams towards finals,
Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$.
Prove :
for every 2 ...
2
votes
1answer
62 views
Encoding set of At-Most-One constraints as a MAX-SAT problem
Assume a set of variable $V$ = $\{v_1,...,v_m\}$.
Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$,
$$ ...
0
votes
2answers
97 views
How is the set of functions from ${\{a,b\}}$ to $N$ countable?
Assume a set of functions from ${\{a,b\}}$ to $N$
Where $N$ is the set of Natural numbers.
Let us assume that the size of $N$ is $n$.
i.e $|N|=n$
The first element $a$ have $n$ choices for mapping....
0
votes
0answers
20 views
How to model most optimized encoding of string data
Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation.
I ...
3
votes
2answers
492 views
Proof of the inclusion-exclusion principle
The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:
THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION Let $A_1,...
0
votes
1answer
45 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
3
votes
1answer
57 views
Triangulation of disjoint line segments
Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, ...
3
votes
2answers
58 views
Joining line segments to make tree
Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
3
votes
1answer
39 views
Prove vertices of polygon are endpoints of disjoint line segments
If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the ...
5
votes
1answer
91 views
Near Triangulation Planar Graph
This is the problem I am dealing with:
Given a set P of n points in general position, let a graph G be defined as follows:
The vertex set is P. Two vertices, a and b, are joined by an edge provided ...
6
votes
2answers
76 views
Voronoi Diagram Drawing Variations and Charateristics
I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.
Similarly how can we draw the Voronoi diagram for the ...
6
votes
1answer
107 views
Voronoi Cell and Voronoi Diagram
Consider a set R of n red points and B of n blue points in the plane. Let xāR and yāB be the shortest edge xy. Let P = R āŖ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x ...
6
votes
0answers
104 views
Placing a tripod in a plane such that it partition a given set of points (with pic)
I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
2
votes
1answer
152 views
Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:
Set of finite languages over a finite alphabet is countable.
Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to ...
0
votes
1answer
27 views
$O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions
Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $. You can't use the ...
