Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
8