Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
372
questions
0
votes
0answers
11 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
0answers
20 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
53 views
2
votes
1answer
35 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
11 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
22 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
55 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
22 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
47 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
40 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
46 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
41 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
127 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
30 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
22 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
81 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
15 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
18 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
42 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
49 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
26 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
117 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
92 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
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
214 views
Turing reducible in natural numbers?
I'm confused about Turing reducible things.
I understanded Turing reducible like this
...
1
vote
1answer
26 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
33 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
78 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
37 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
48 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
89 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
35 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
64 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
99 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....
