Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
398
questions
0
votes
1answer
28 views
Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$
Define a sequence $c_1,c_2,\dots$ by the equations
$$ c_1=0, \quad c_n = 4c_{\lfloor n/2 \rfloor} + n \text{ for all } n > 1. $$
Prove that $\frac{(n+1)^2}{8} < c_n$ for all $n \geq 2$.
Hint: $\...
0
votes
3answers
30 views
0
votes
0answers
15 views
Why can't I evaluate this L-Attributed SDD with a pre-order traversal?
My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
0
votes
2answers
58 views
Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?
I don’t have specific topic that I care more about ...
2
votes
1answer
32 views
Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?
1
vote
2answers
63 views
What mathematical guarantees gives alpha-beta pruning?
In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a ...
0
votes
3answers
89 views
Computing square vs computing square-root? Time complexity
I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest ...
1
vote
2answers
39 views
How can I show mathematically the time complexity of this function is O(N)?
int foo(N){
if(N <= 1){
return 0
}else{
return 1 + foo(N-1)
}
}
I can tell that the time complexity of this program is O(N) but I am ...
0
votes
0answers
39 views
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute
I will state the complete question now, since it did not fit in the title.
Is the statement given below correct?
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-...
1
vote
2answers
37 views
Compute average case with best case
is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (...
1
vote
1answer
31 views
Given an undirected graph, find an orientation such that every vertex has out-degree at least 3
Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.
I know how to check if a vertex $v$ has at least $k$ ...
1
vote
1answer
56 views
facts on tree and MST
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following ...
1
vote
1answer
22 views
Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
2
votes
1answer
98 views
Number of nodes at given depth in binary tree
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
1
vote
1answer
68 views
Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$
I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.
However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence ...
0
votes
1answer
36 views
What is the exponent of 0.00000072
And how do I solve this?
I know this is a decimal and we have to convert it to an exponent. I want to know how I would solve this and the steps as well so I will be able to solve questions similar to ...
0
votes
0answers
38 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
65 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
46 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
40 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
25 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?
...
0
votes
1answer
63 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
131 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
28 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
764 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
53 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
14 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
34 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
56 views
2
votes
1answer
296 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
14 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
26 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
57 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
45 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
16 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
52 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 ...
1
vote
1answer
53 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
136 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
38 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
74 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
31 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)] = -\...
0
votes
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
94 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
17 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{...
