Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
384
questions
0
votes
0answers
32 views
Show that this language is undecidable
Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$
I would like to know if ...
1
vote
1answer
55 views
How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show ...
0
votes
1answer
42 views
any one can prove following inequality?
are for every $\alpha \in N $ , $ \frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?
1
vote
1answer
36 views
Height of AVL tree with balance condition of 2
The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
0
votes
0answers
23 views
Question about graphs and Eulerian path
An almost complete graph of n vertices is obtained from the removal of two edges of the complete graph
of n vertices. For which values of n are there almost complete graphs that admit Eulerian paths?
...
-3
votes
0answers
14 views
Common neighbors of adjacent vertices on longest cycle
Let $G$ be a simple graph. Let $C$ be a cycle of maximum size in $G$, and let $u$ and $v$ be two neighboring vertices
in $C$. We define $\operatorname{NC} (u, v)$ as the number of neighbors common to $...
0
votes
1answer
62 views
How can I prove the correctness of this exponentiation algorithm using induction?
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
...
4
votes
2answers
112 views
Min path cover for a three-layer graph with all paths traversing all layers
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
2
votes
0answers
34 views
Line graphs of Powers of Cycles are powers of cycles
Are line graphs of powers of cycles again a power of cycle? I think yes, this is because the line graphs of cycles are cycles of the same order, and moreover, since powers of cycles consist of edge ...
-1
votes
3answers
44 views
Which topics of mathematics should I need to learn to be a good app developer?
I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
0
votes
0answers
27 views
Algorithm for specific load balancing/arbitration problem
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
3
votes
1answer
571 views
Arrange in increasing order of asymptotic complexity
I have the following functions that I need to rank in increasing order of Big-O complexity:
$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$...
2
votes
3answers
42 views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ā Ī£*, n ā„ 1} is regular?
I'm trying to prove the language L = {$0^n š„1^š$ | x ā Ī£*, n ā„ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
0answers
12 views
How do you prove that this tree path calculation function works, from first principles mathematically?
I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
1answer
33 views
Mathematical expression for the quantity that we are maximising in the stock buying and selling problem
Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many ...
-1
votes
1answer
55 views
2
votes
1answer
76 views
Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$
If I have a recurrence relationship like this:
$$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$
how would I analyze its rate of growth?
I believe I can't use the master theorem. I tried to draw a tree but ...
1
vote
1answer
12 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
0answers
41 views
Proof using tableau algorithm
I have spent an hour finding the answer to this problem but can't do it, this is the problem:
Determining whether the following semantic entailment holds or not by using the tableau algorithm
...
0
votes
1answer
23 views
Represent a DNF formula as a multivariate linear formula?
Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?
3
votes
0answers
56 views
Data structure to determine vertex membership after edge removal from a tree in sub-linear time?
Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$.
Is there a data structure that enables the immediate determination of ...
2
votes
0answers
23 views
How to linearly combine loss functions to preserve optimal substructure property?
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
49 views
An efficient way of calculating 𝜙(𝜙(p*q)) where p and q are prime
Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $...
0
votes
1answer
41 views
For an NFA, can we always find a RAM?
For an NFA, can we always find a RAM, which recognises the same language?
2
votes
1answer
15 views
Maximum Chromatic number of Cayley Graphs with large degree
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
1
vote
0answers
31 views
If factor isn't found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)
I have seen some implementations of Pollard's P-1 algorithm where the upper bound is only increased by 1 if no factor is found. Such an implementation is described here. Is it sort of missing the ...
1
vote
2answers
47 views
Implementing piecewise linear functions
I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the ...
2
votes
1answer
48 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
131 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
33 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
70 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
23 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
87 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
16 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
36 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
19 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
46 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
69 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
67 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
64 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
37 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
34 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
178 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
23 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
101 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
40 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?
1
vote
1answer
26 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
218 views
Turing reducible in natural numbers?
I'm confused about Turing reducible things.
I understanded Turing reducible like this
...
